bestimmen sie ein lokales Minimum f mit der Methode des konjugierten Gradienten, startend bei (x_1, y_1) = (0,0)

Question

Aufgabe:

Sei $$f(x,y) := x^2 + y^2 -xy - x -2y$$

bestimmen sie ein lokales Minimum f mit der Methode des konjugierten Gradienten, startend bei $$(x_1, y_1) = (0,0)$$

Dafür soll f zuerst in die Form $$f(x) = \frac{1}{2}x^\intercal Qx-bx^\intercal$$ gebracht werden.

Problem/Ansatz:

Leider wurde vom Professor nicht erklärt, wie man die Funktion nun umwandelt. Kann mir jemand bitte weiter helfen?

Answer 1

Eigentlich ist da auch nichts zu erklären.

Verwende eine sym. Matrix $Q=\begin{pmatrix}q_{11} & q_{12}\\ q_{12} & q_{22}\end{pmatrix}$ und $b=(b_1\; b_2)$ und rechne

$\frac12(x\; y)Q\binom{x}y + b \binom{x}y$ aus. Dann Koeffizientenvergleich.

Comments

Also kommt man dann auf:

$$\frac{1}{2}q_{11}x^2 + \frac{1}{2}q_{22}y^2 + q_{12}xy + b_1x + b_2y$$

woraus man schließen kann $$f(x,y) = \frac{1}{2}\begin{pmatrix}x & y \end{pmatrix}\begin{pmatrix}2 & -1 \\-1 & 2 \end{pmatrix}\begin{pmatrix}x \\y \end{pmatrix} +\begin{pmatrix}-1 & -2 \end{pmatrix}\begin{pmatrix}x \\y \end{pmatrix}$$

Stimmt das so?

---

Ja, genau so ist es.

Answer 2

Aloha :)

In $(\vec x^T\cdot Q\cdot\vec x)$ sind alle quadratischen Terme enhalten, in $\vec b^T\cdot\vec x$ sind alle linearen Terme enthalten. Das führt zu der Zerlegung:$$f(x;y)=(x^2+y^2-xy)-(x+2y)$$

Die Matrix $Q$ wollen wir gerne symmetrisch haben, d.h. $Q=Q^T$ ist erwünscht. Daher machen wir den Term in der ersten Klammer symmetrisch:$$f(x;y)=\left(x^2+y^2-\frac12xy-\frac12yx\right)-(x+2y)$$$$\phantom{f(x;y)}=\frac12\cdot\left(\red 2\cdot x\cdot x+\green 2\cdot y\cdot y\blue{-1}\cdot x\cdot y\;{\color{brown}-1}\cdot y\cdot x\right)-(x+2y)$$

Daraus können wir die quadratische Form ablesen:$$f(x;y)=\frac12\cdot\left(\begin{array}{rr}x & y\end{array}\right)\cdot\left(\begin{array}{rr}\red2 & {\color{brown}-1}\\\blue{-1} & \green2\end{array}\right)\cdot\binom{x}{y}-\begin{pmatrix}1 & 2\end{pmatrix}\cdot\binom{x}{y}$$