Maximierung einer Norm

18.06.2011, 13:23

Lisa86

Maximierung einer Norm

Meine Frage:
Hallo, ich soll die Norm ||A x|| unter der Einschränkung ||x||=1 maximieren. Dabei ist A eine n x m-Matrix und x ein Vektor in m.

Meine Ideen:
Ich versuche die Lagrangemultiplikatormethode zu verwenden, der Gradient von ||x||^2 - 1 = 2 * ||x||.
Doch wie ist der Gradient von ||Ax||^2 ? Müsste es nicht sowas wie 2*||Ax||*A sein? Doch dann habe ich ja einen Vektor mal eine Matrix, das geht doch nicht...

18.06.2011, 13:28

Mazze

Auf diesen Beitrag antworten »

Bevor Du anfängst wie wild irgendwie abzuleiten (und das noch falsch) solltest Du das Problem erstmal ordentlich formulieren. Zudem solltest Du uns sagen welche Norm verwendet wird (oder ob Du eine bel. Norm auf dem R^n hast).

18.06.2011, 13:29

Lisa86

Auf diesen Beitrag antworten »

srry, ich verwende die standardnorm auf dem R^n

18.06.2011, 13:31

Mazze

Auf diesen Beitrag antworten »

Was ist die Standardnorm ? Die euklidische Norm?

18.06.2011, 13:39

Lisa86

Auf diesen Beitrag antworten »

ja, die euklidische norm
Also ||x||^2 abgeleitet gibt 2x und nicht 2*||x||.
Doch wie leite ich ||Ax||^2 ab? Wenn ich die Matrixmultiplikation in Summenform aufschreibe komme ich nicht weiter:
$\begin{eqnarray*} ||Ax||^2 = \sum\limits_{i=1}^n ((\sum\limits_{j=1}^n a_{ij}x_{j} ) (\sum\limits_{kj=1}^n a_{ij}x_{j} )) \end{eqnarray*}$

18.06.2011, 13:48

Mazze

Auf diesen Beitrag antworten »

Beispiel :

Wir haben die Funktion (euklidische Norm).

$\begin{eqnarray*} \| \cdot \| : \mathbb{R}^n \to \mathbb{R} \end{eqnarray*}$

mit

$\begin{eqnarray*} x \mapsto \|x\| \end{eqnarray*}$

Dann ist

$\begin{eqnarray*} \|x\| = \sqrt{\sum_{i=1}^n x_i^2} \end{eqnarray*}$

Dann ist (mit der Kettenregel)

$\begin{eqnarray*} \frac{\partial \|x\|}{\partial x_k} = \frac{x_k}{\|x\|} \end{eqnarray*}$

Der Gradient ist dann also $\begin{eqnarray*} \frac{1}{\|x\|}x \end{eqnarray*}$

Muss jetzt leider weg , daher :

Es ist :

$\begin{eqnarray*} \|Ax\| = \sqrt{\sum_{i=1}\left(\sum_{k=1}A_{ik}x_k\right)^2} \end{eqnarray*}$

Das mit der Kettenregel ableiten!

18.06.2011, 13:51

Lisa86

Auf diesen Beitrag antworten »

Danke, nur genau das hab ich ja oben stehen und komme nicht weiter...

18.06.2011, 13:55

Lisa86

Auf diesen Beitrag antworten »

Bzw. wenn ich zeigen könnte, dass grad||Ax|| = $\begin{eqnarray*} A^\perp * A *x^2 \end{eqnarray*}$
wäre das Problem gelöst, weil dann $\begin{eqnarray*} A^\perp * A *x = 2ax \end{eqnarray*}$ , wobei a der Parameter der Lagrangemethode ist...

19.06.2011, 10:32

Mazze

Auf diesen Beitrag antworten »

Zitat:

Bzw. wenn ich zeigen könnte, dass grad||Ax|| = $\begin{eqnarray*} A^\perp * A *x^2 \end{eqnarray*}$

Was soll denn $\begin{eqnarray*} x^2 \end{eqnarray*}$ sein, wenn x ein Vektor ist ?

Zur Lösung :

Es gilt allgemein (aus der Schule bekannt )

$\begin{eqnarray*} \frac{\partial }{\partial x_i}\sum_{k=1}^nf_k(x) = \sum_{k=1}^n\frac{\partial }{\partial x_i}f_k(x) \end{eqnarray*}$

Das kennt man als Summenregel , die Ableitung der Summe ist gleich der Summe der Ableitungen.

Mit der Kettenregel erhält man dann :

$\begin{eqnarray*} \frac{\partial \|Ax\|}{\partial x_k} = \frac{1}{2\|Ax\|} \cdot \sum_{i=1}^n \frac{\partial}{\partial x_k}\left(\sum_{j=1}^n A_{ij}x_j\right)^2 \end{eqnarray*}$

Und die Ableitung des quadratischen Terms nach x_k kriegst Du sicher hin!

19.06.2011, 14:01

Lisa86

Auf diesen Beitrag antworten »

Ja nur wie komm ich dabei auf $\begin{eqnarray*} A^\perp *A * x \end{eqnarray*}$ ? Soweit mit dem Ableiten war ich nämlich auch schon... Nur das ich die Norm zum Quadrat abgeleitet habe...

19.06.2011, 14:20

Mazze

Auf diesen Beitrag antworten »

Zitat:

Ja nur wie komm ich dabei auf $\begin{eqnarray*} A^\perp *A * x \end{eqnarray*}$ ?

Was ist $\begin{eqnarray*} A^\perp \end{eqnarray*}$ ?

Ansonsten ist

$\begin{eqnarray*} \frac{\partial}{\partial x_k}\left(\sum_{j=1}^n A_{ij}x_j\right)^2 = 2\left(\sum_{j=1}^n A_{ij}x_j\right)A_{ik} \end{eqnarray*}$

also insgesamt :

$\begin{eqnarray*} \frac{\partial \|Ax\|}{x_k} = \frac{1}{\|Ax\|}\sum_{i=1}^n\sum_{j=1}^n A_{ij}A_{ik}x_j \end{eqnarray*}$

Der Gradient von ||Ax|| ist dann

$\begin{eqnarray*} \frac{1}{\|Ax\|}A^TAx \end{eqnarray*}$

meinst Du mit $\begin{eqnarray*} A^\perp \end{eqnarray*}$ vielleicht $\begin{eqnarray*} A^T \end{eqnarray*}$ ?

19.06.2011, 19:43

Lisa86

Auf diesen Beitrag antworten »

Vielen Dank! Ja, ich meinte A transponiert, ich seh jetzt erst dass ich wohl das falsche Symbol im Formeleditor verwendet habe... Ich sehe jetzt auch warum ich nicht weiterkomme, ich habe nämlich nicht zwischen j und k unterschieden, so macht das Sinn. Danke!

Neue Frage »

Antworten »

Maximierung einer Norm

Verwandte Themen