Ottimizzazione Non Vincolata e Ordine Di Convergenza

[AttraversamiIlCuore]

Ciao a tutti!
Siccome il prof non ha dato dispense su cui seguire, sto cercando di risolvere un esercizio... solo che lo sto facendo "meccanicamente" seguendo un esercizio svolto.. quindi per prima cosa vorrei chiedervi se avete dispense (siti, o qualsiasi cosa) dove venga trattato questo argomento...
Secondo vi ricopio il mio svolgimento dell'esercizio (quello che sono riuscito a fare), se qualcuno può aiutarmi!
Allora... il testo è :
Data la funzione \( \displaystyle {f{{\left({x}_{{1}},{x}_{{2}}\right)}}}={{x}_{{1}}^{{2}}}+{{x}_{{2}}^{{4}}}+{3} \) costruire una successione di direzione di discesa che convergano al minimo a partire da \( \displaystyle {{x}}^{{{\left({0}\right)}}}={{\left(\frac{{1}}{{2}},\frac{{1}}{{2}}\right)}}^{{T}} \), fornire i primi tre valori della successione dei punti ottenuti da questa e controllare l'errore (in norma infinito, ovvero componente di massimo modulo del vettore) e discutere l'ordine di convergenza del minimo.Allora il mio primo dubbio è sul controllare l'errore... come si fa? E il secondo... come discuto l'ordine?
Per il resto vi copio i miei passaggi :

\( \displaystyle {f{{\left({x}_{{1}},{x}_{{2}}\right)}}}={{x}_{{1}}^{{2}}}+{{x}_{{2}}^{{4}}}+{3} \) con \( \displaystyle {{x}}^{{{\left({0}\right)}}}={{\left(\frac{{1}}{{2}},\frac{{1}}{{2}}\right)}}^{{T}} \)
\( \displaystyle \nabla{f{{\left({x}_{{1}},{x}_{{2}}\right)}}}={\left({2}{x}_{{1}},{4}{{x}_{{2}}^{{3}}}\right)} \)
\( \displaystyle {\nabla}^{{2}}{f{{\left({x}_{{1}},{x}_{{2}}\right)}}}={\left|\matrix{{2}&{0}\\{0}&{12}{{x}_{{2}}^{{2}}}}\right|} \) e chiamo questa matrice come H.
1 Iterazione. Imposto il sistema \( \displaystyle {H}\partial=-{b} \)
\( \displaystyle {\left|\matrix{{2}&{0}\\{0}&{12}{{x}_{{2}}^{{2}}}}\right|}\cdot{\left|\matrix{{\partial_{{1}}^{{{\left({0}\right)}}}}\\{\partial_{{2}}^{{{\left({0}\right)}}}}}\right|}={\left|\matrix{-{2}{x}_{{1}}\\-{4}{{x}_{{2}}^{{3}}}}\right|} \)
Sostituisco il punto \( \displaystyle {{x}}^{{{\left({0}\right)}}} \) :
\( \displaystyle {\left|\matrix{{2}&{0}\\{0}&{3}}\right|}\cdot{\left|\matrix{{\partial_{{1}}^{{{\left({0}\right)}}}}\\{\partial_{{2}}^{{{\left({0}\right)}}}}}\right|}={\left|\matrix{-{1}\\-\frac{{1}}{{2}}}\right|} \)
E trovo come soluzione
\( \displaystyle {\partial_{{1}}^{{{\left({0}\right)}}}}=-\frac{{1}}{{2}};{\partial_{{2}}^{{{\left({0}\right)}}}}=-\frac{{1}}{{6}} \)
\( \displaystyle {{x}}^{{{\left({1}\right)}}}={{x}}^{{{\left({0}\right)}}}+{\partial}^{{{\left({0}\right)}}}={\left|\matrix{{0}\\\frac{{1}}{{3}}}\right|} \)

2 Iterazione. Imposto il sistema \( \displaystyle {H}\partial=-{b} \)
\( \displaystyle {\left|\matrix{{2}&{0}\\{0}&{12}{{x}_{{2}}^{{2}}}}\right|}\cdot{\left|\matrix{{\partial_{{1}}^{{{\left({1}\right)}}}}\\{\partial_{{2}}^{{{\left({1}\right)}}}}}\right|}={\left|\matrix{-{2}{x}_{{1}}\\-{4}{{x}_{{2}}^{{3}}}}\right|} \)
Sostituisco il punto \( \displaystyle {{x}}^{{{\left({1}\right)}}} \) :
\( \displaystyle {\left|\matrix{{2}&{0}\\{0}&\frac{{4}}{{3}}}\right|}\cdot{\left|\matrix{{\partial_{{1}}^{{{\left({1}\right)}}}}\\{\partial_{{2}}^{{{\left({1}\right)}}}}}\right|}={\left|\matrix{{0}\\-\frac{{4}}{{27}}}\right|} \)
E trovo come soluzione
\( \displaystyle {\partial_{{1}}^{{{\left({1}\right)}}}}={0};{\partial_{{2}}^{{{\left({1}\right)}}}}=-\frac{{1}}{{9}} \)
\( \displaystyle {{x}}^{{{\left({2}\right)}}}={{x}}^{{{\left({1}\right)}}}+{\partial}^{{{\left({1}\right)}}}={\left|\matrix{{0}\\\frac{{2}}{{9}}}\right|} \)

3 Iterazione. Imposto il sistema \( \displaystyle {H}\partial=-{b} \)
\( \displaystyle {\left|\matrix{{2}&{0}\\{0}&{12}{{x}_{{2}}^{{2}}}}\right|}\cdot{\left|\matrix{{\partial_{{1}}^{{{\left({2}\right)}}}}\\{\partial_{{2}}^{{{\left({2}\right)}}}}}\right|}={\left|\matrix{-{2}{x}_{{1}}\\-{4}{{x}_{{2}}^{{3}}}}\right|} \)
Sostituisco il punto \( \displaystyle {{x}}^{{{\left({2}\right)}}} \) :
\( \displaystyle {\left|\matrix{{2}&{0}\\{0}&\frac{{16}}{{27}}}\right|}\cdot{\left|\matrix{{\partial_{{1}}^{{{\left({2}\right)}}}}\\{\partial_{{2}}^{{{\left({2}\right)}}}}}\right|}={\left|\matrix{{0}\\-\frac{{32}}{{729}}}\right|} \)
E trovo come soluzione
\( \displaystyle {\partial_{{1}}^{{{\left({2}\right)}}}}={0};{\partial_{{2}}^{{{\left({2}\right)}}}}=-\frac{{2}}{{27}} \)
\( \displaystyle {{x}}^{{{\left({3}\right)}}}={{x}}^{{{\left({2}\right)}}}+{\partial}^{{{\left({2}\right)}}}={\left|\matrix{{0}\\\frac{{4}}{{27}}}\right|} \)

[AttraversamiIlCuore]

Ciao a tutti!
Sono riuscito a risolvere l'esercizio (se a qualcuno interessa potrei copiarlo qui)... gli unici due punti rimasti in sospeso sono l'ordine di convergenza e l'errore di norma infinito... chi mi sa aiutare?
Grazie

[canemacchina]

mmm, sei sicuro di aver risolto l'esercizio considerando cosa hai scritto prima? perché c'è qualcosa che non mi torna, a partire dal calcolo del gradiente.

Comunque, cerca in rete (purtroppo non posso passarti ciò che ho perché ho un libro stampato!!) qualcosa in merito a "Metodo di newton per sistemi non lineari" e leggi un po'.

In pratica si tratta di trasformare il metodo di Newton per trovare le radici di funzioni unidimensionali al caso multidimensionale. Questo perché la ricerca di minimi (o massimi, in realtà) per funzioni multidimensionali passa per la ricerca dei punti stazionari, ovvero delle radici del gradiente.

Allora, in soldoni:
calcoli il gradiente, dal gradiente calcoli la matrice Jacobiana. A questo punto la direzione è determinata dal fatto che la Jacobiana sia definita positiva o meno, ma nel tuo caso essendo la funzione convessa, sei sicuro che la direzione sia di discesa verso il minimo.

Il metodo lo definisci come:

\( \displaystyle \left\lbrace
\begin{array}{l}
J_f(x^{k})d_k = -\nabla f(x^{k})\\
\\
x^{k+1} = x^{k} + d_k\\
\end{array}
\right. \)

Per quanto riguarda l'ordine di convergenza, i risultati sono noti e questo metodo converge quadraticamente.
In alternativa a questo, puoi sostituire all'interno dell'iterazione \( \displaystyle J_f(x^{k}) \) con \( \displaystyle J_f(x^{0}) \) , ovvero fare qualcosa di simile al metodo delle corde. In pratica approssimi la Jacobiana di ogni passo con la Jacobiana calcolata sulla prima approssimazione della soluzione, in modo tale da effettuare i calcoli una volta sola (ovvero, supponendo che stai lavorando su un calcolatore, puoi fattorizzare una volta sola ka \( \displaystyle J_f \) ).
In questo caso però la convergenza scende da quadratica a lineare.

Per quanto riguarda gli errori, io credo tu debba calcolare l'errore sulla soluzione, un po' come si fa quando si parla di errori nel caso della ricerca di radici di funzioni.
In questo caso però la tua soluzione è rappresentata da un vettore e non da uno scalare, percui al posto del calcolo sui valori assoluti usi le norme, ovvero (supponendo che \( \displaystyle \overline{x} \) sia la soluzione esatta), potresti dire che:
\( \displaystyle \Delta_x = ||\overline{x} - x||_\infty \)
\( \displaystyle \varepsilon_x = \dfrac{\Delta_x}{||\overline{x}||_\infty} \)

[AttraversamiIlCuore]

Ciao! Intanto grazie per la risposta... hai ragione l'esercizio non era corretto eho provveduto a riscriverlo con tutti i passaggi...
Ti ringrazio per la risposta e le formule ma non ho capito molto :S
PRATICAMENTE come dovrei fare? Ad ogni iterazione devo controllare l'errore o è solo un passaggio finale?
Anche se praticamente non saprei come farlo... ti ringrazio ancora

[canemacchina]

Allora, premesso che parlare senza che tu abbia chiaro tutto il concetto diventa un po' complicato (ti ripeto, cerca qualcosa in rete e documentati un po' visto che non hai dispense), sul controllo dell'errore c'è tutta una trattazione particolare.

In primo luogo, quelle "formule" che ti ho dato sono in sostanza la definizione degli errori, da intendere (scusa se sono stato poco chiaro, non sapevo fino a che punto tu avessi studiato certi metodi) come l'errore assoluto commesso (la prima) e l'errore relativo (la seconda).

Il calcolo degli errori passa per la determinazione della soluzione esatta del problema: come ti ho scritto prima \( \displaystyle \overline{x} \) è la soluzione esatta. Quindi non è sempre facilmente calcolabile l'errore commesso (anche perché, fosse facile, non avremmo il problema di approssimare le soluzioni!!!)
Quindi, dipende un po' da cosa intende l'esercizio e da cosa devi fare tu.
Nel senso: se ti viene proposta anche la soluzione esatta (o se te la sai calcolare analiticamente) puoi calcolare direttamente l'errore commesso alla fine del terzo passo di iterazione, in modo da quantificare, dopo appunto 3 passi, quanto "vicino" tu sia alla soluzione del problema.

Nella pratica però non si fa questo (ripeto, proprio perché il calcolo dell'errore passa per il calcolo della soluzione esatta). Se ti metti a leggere qualcosa in merito (evito di scriverlo io anche solo per la lunghezza della trattazione) quello che si fa è fare alcune considerazioni sul metodo usato (nel caso specifico quello di Newton, quindi nulla da inventare) e si vede in che modo è possibile ottenere una soluzione approssimata con una certa precisione decisa a priori.

Cerco di spiegarmi meglio:
in generale i metodi iterativi (qualsiasi, non solo quelli per cercare le radici di funzioni) trovano la soluzione finale per approssimazioni successive. Va da se quindi che la soluzione esatta viene definita come il risultato di infinite iterazioni. Ovviamente nessuno può permettersi di eseguire infiniti passi di un qualsiasi algoritmo, quindi è necessario decidere in qualche modo quando è il momento di fermarsi.
In generale quindi si cerca di stimare in che misura l'errore diminuisce ad ogni passo di iterazione (mettiamola in questi termini, non è proprio corretto) e quindi si esegue l'algoritmo fino a che non si raggiunge un errore che rientra nella precisione richiesta.

Ora, in merito al tuo esercizio: per essere più preciso, perché non mi fai vedere un esempio di un esercizio svolto (visto che hai detto che ce l'hai)? Così capisco bene cosa ti viene richiesto.

Ciao!

[AttraversamiIlCuore]

Ciao!
Intanto ancora grazie per la disponibilità e spiegazioni...
Si intanto sto cercando delle cose in internet, anche perchè fare le cose meccanicamente non è che mi entusiasmi molto... anzi...
Per quanto riguarda l'errore, non mi viene data la soluzione precisa a priori (il testo è precisamente quello che ho copiato)...
E per l'esercizio, purtroppo, ho solamente svolta la parte riguardante le iterazioni... per questo mi sono trovato in difficolta sull'errore e sull'ordine... uff!
Grazie ancora per la disponibilità io continuo a cercare... speriamo!