Ottimizzazione quadratica

[Marco]

Ciao. Questo è un problema di lavoro di ieri. Si tratta di un vecchio classico, ma magari a qualcuno può interessare...

--------------------

Sia R una matrice reale simmetrica [semi]definita positiva e sia r(-) la forma quadratica associata. Sia $ \Lambda = (\lambda_i)_i $ un vettore di pesi.

Vogliamo trovare

$ \min r(\Lambda) $

soggetto al vincolo

$ $ \sum_i \lambda_i = 1 $.

--------------------

Ciao. M.

[EvaristeG]

Sarò brutale ... moltiplicatori di Lagrange ? (sto preparando Analisi II, quindi...)

[elianto84]

Se la matrice è definita positiva la diagonalizziamo tramite cambio di coordinate
ed applichiamo tale cambio anche al piano con equazione originaria
sum( lambda ) = 1

Alchè il problema è ricondotto a trovare la distanza quadra tra un punto (l'origine)
e un piano (il trasformato del piano sum( lambda ) = 1 )

Questa distanza quadra sarà pari al modulo quadro del vettore di giacitura
del piano trasformato.
Ma in che relazione sono i vettori di giacitura del piano originario (v)
e di quello trasformato (w) ?

v = (1, 1, 1, ..., 1)

Il cambio di coordinate ruota v, ne dilata le componenti secondo rapporti
pari agli autovalori della matrice di partenza, quindi applica la rotazione inversa.
Segue che la distanza quadra che cerchiamo è pari alla somma dei quadrati
degli autovalori della matrice di partenza.

Consideriamo ora l'applicazione lineare associata alla matrice di partenza.
Questa applicazione manda sistemi di riferimento ortogonali in
sistemi di riferimento ortogonali; per determinare la somma dei quadrati
degli autovalori possiamo dunque sommare le lunghezze quadre dei vettori
che risultano essere immagine dei vettori della base canonica secondo la
nostra applicazione lineare. Le immagini dei vettori della base canonica
corrispondono alle colonne della matrice di partenza, dunque la quantità che
cerchiamo è pari alla somma dei quadrati degli elementi della matrice di partenza.

--------------------
Alternativamente.
--------------------

Tramite diagonalizzazione e trasformazione affine il problema si riduce a

min (x^2 + y^2 + z^2) sotto la condizione (ax + by + cz)=1

che si sa risolvere in mille modi.

[Marco]

@Elianto:

...mmmm... Sono d'accordo che il problemino si possa risolvere in mille modi. Però c'è qualcosa che non mi torna nel tuo primo metodo.

Non sono sicuro di aver capito bene, perciò potrei avere equivocato, ma mi pare che se prendi banalmente

$ R= \left( \begin{array}{cc} 1 & \rho \\ \rho & 1\end{array} \right) $.

Il minimo, per simmetria, è in (1/2, 1/2) e, facendo il conto, vale $ $\frac{1+\rho}{2} $, mentre la somma dei quadrati degli elementi è $ 2 \left( 1 + \rho^2 \right) $.

Torna, o ho frainteso?

[elianto84]

Hai ragione Marco, ho cannato il meccanismo secondo il quale si
trasforma il vettore di giacitura del piano.

Sia R una base di autovettori per la nostra matrice simmetrica.

Se v[1]...v[n] sono le colonne di R, ° è l'usuale prodotto scalare
e w = sum v, il problema ridotto si può scrivere come

min(xT A x) su sum x=1
min(xT RT D R x) Rx=y RTy = x
min( yT D y ) su x[1]+....+x[n]=1 cioè su w°y=1

y=z/sqrt(lambda)
W=(w[1]/sqrt(lambda[1]),...,w[n]/sqrt(lambda[n]))

min sum z^2 su W°z = 1

che è risolto da z=W/(|W|^2)
il minimo è pari al quadrato della norma di z dunque a 1/|W|^2