Ricette numeriche/Ricerca radice multidimensionale (utilizzando newt): Come minimizzare l'errore massimo

Question

Questa domanda è correlata al libro "ricette numeriche in C++", quindi sarà riservata alle persone che ne conoscono un po 'oltre a ottimizzazione multidimensionale.

Sto scrivendo un programma che ha bisogno di cercare una radice multidimensionale e, per risolverlo, sto usando il metodo di ricerca della radice di newton multidimensionale, ovvero la procedura "newt".

Per chi è interessato ai dettagli, sto cercando di adattare un modello 3D deformabile a una vista steresocica di un oggetto, basata su alcuni punti funzione (punti funzione visti da due telecamere).

Per questo, sto usando la procedura di Newt con il seguente:

• 11 Parametri di ingresso: mio modello deformabile può essere modellata con 11 parametri (composto da 5 parametri geometrici e 6 deegres di libertà per la posizione dell'oggetto 3D):
• 14 Parametri di uscita per cui ho bisogno di trovare la radice: in base ai punti funzione identificati dalla telecamera e dato un set su "parametri di input", posso calcolare un set di distanze tra i punti caratteristica visti dalla fotocamera e il loro lo teorico cazione. Ho 7 di questi punti, quindi mi danno 14 parametri (7 distanze 2, poiché calcolo le distanze su entrambe le fotocamere)

Il mio problema è che ho più parametri di output (14) rispetto ai parametri di input (11): ogni volta che chiamo "newt", l'algoritmo converge sempre, tuttavia troverà una soluzione che minimizza quasi perfettamente gli 11 parametri di prima uscita, ma che ha molti errori sui 3 parametri rimanenti.

Tuttavia, desidero che gli errori siano suddivisi uniformemente tra i parametri di uscita.

Ho già provato gli approcci descritti di seguito:

1. provare a combinare i parametri di uscita 14 in 11 parametri (per esempio, si prende la media di alcune distanze, invece di utilizzare entrambe le distanze). Tuttavia non sono soddisfatto al 100% con questo approccio
2. Mix diverse soluzioni con il seguente principio:
   • chiamata mnewt e memorizzare i trovato radice
   • Modificare l'ordine del parametro 14 uscita
   • Calling mnewt ancora e memorizzare il trovato radice
   • calcolare una soluzione è la media delle due radici trovati

Qualcuno sa di un approccio più generico, in cui l'algoritmo di individuazione delle radici favorirebbe un errore suddiviso uniformemente tra i parametri di output, invece di favorire i primi parametri?

Answer 1

Si tenta di ridurre al minimo F(x) risolvendo f(x)=0 dove x è un vettore m-dimensionale e f lo associa a un vettore n-dimensionale.Il tuo problema di ottimizzazione è sottodeterminato se m < n (nel tuo caso 11 < 14).

Per tali sistemi, il modo più generico per risolverli è ridurre al minimo la norma su x. È possibile eseguire questa operazione riducendo al minimo il sistema x^T A x + c f(x)^T f(x) in relazione sia a x sia al moltiplicatore di Lagrange Lagrangec. Senza ulteriori informazioni, è possibile utilizzare A come nxn matrice identità. Questo troverà il x che risolve f(x)=0 pur avendo la più piccola norma.

Per ulteriori dettagli su come farlo con il metodo di Newton, vedere ad es. questo paper.