Minimierungsproblem mit Nebenbedingung

15.01.2024, 14:59

Wesley2010

Minimierungsproblem mit Nebenbedingung

Meine Frage:
Sei $\begin{eqnarray*} A\in R^{mxn} m>n \end{eqnarray*}$ und $\begin{eqnarray*} A \end{eqnarray*}$ hat vollen Rang. $\begin{eqnarray*} b \in R^m \end{eqnarray*}$ und $\begin{eqnarray*} c \in R^n \end{eqnarray*}$ mit $\begin{eqnarray*} A^T*y = c \end{eqnarray*}$
Folgendes minimierungs Problem habe ich nun :
$\begin{eqnarray*} \min_{x\in\mathbb{R}^n} \frac{1}{2} \| Ax-b\|_2^2+c^Tx \end{eqnarray*}$
und soll zeigen das es dafür eine eindeutige lösung gibt.

Meine Ideen:
Für die Existenz der Lösung habe ich mir überlegt, dass die euklidische Norm ja stetig ist, ebenso wie natürlich die lineare Abbildung dort selbst. Damit sollte das gesamte Problem stetig in x sein. (Wenn ich das Minimum auf ein kompaktes Intervall eingrenzen könnte, dann wäre ich fertig. Das funktioniert aber mEn nicht).

LaTeX-Tags eingefügt. Steffen

27.01.2024, 10:49

Romaxx

Auf diesen Beitrag antworten »

Definiere $\begin{eqnarray*} F(x)=\frac{1}{2} \| Ax-b\|_2^2+c^Tx \end{eqnarray*}$ .

Schreibe die Norm als Skalarprodukt um, ersetze $\begin{eqnarray*} c \end{eqnarray*}$ und bilde und berechne den Gradienten $\begin{eqnarray*} \nabla_x F(x) \end{eqnarray*}$ . Setze $\begin{eqnarray*} \nabla_x F(x)=0 \end{eqnarray*}$ . Löse nach $\begin{eqnarray*} x \end{eqnarray*}$ auf und argumentiere mit den Voraussetzungen, dass diese Lösung eindeutig ist. Argumentiere außerdem, warum bei einem quadratischen Problem dieses Minimum das globale Mininum ist und damit die gemeinte Lösung. Hier hilft auch wieder die Form der Ableitung zu betrachten.

27.01.2024, 11:48

IfindU

Auf diesen Beitrag antworten »

Zitat:

Original von Romaxx
[...] Argumentiere außerdem, warum bei einem quadratischen Problem dieses Minimum das globale Mininum ist [...].

An der Stelle ist vorsicht geboten. Hier benötigt man, dass $\begin{eqnarray*} A \end{eqnarray*}$ einen kleinen Defekt besitzt (kleiner als der von $\begin{eqnarray*} c^T \end{eqnarray*}$ ). Ansonsten könnte es $\begin{eqnarray*} x_k \end{eqnarray*}$ geben mit $\begin{eqnarray*} Ax_k = 0 \end{eqnarray*}$ aber $\begin{eqnarray*} c^Tx_k \to -\infty \end{eqnarray*}$ . In dem Fall hat man dann entlang der Folge kein quadratisches Wachstum und es würde kein globales Minimum existieren.

31.01.2024, 12:44

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Ansonsten könnte es $\begin{eqnarray*} x_k \end{eqnarray*}$ geben mit $\begin{eqnarray*} Ax_k = 0 \end{eqnarray*}$ aber $\begin{eqnarray*} c^Tx_k \to -\infty \end{eqnarray*}$ .

Wie das angesichts des vollen Ranges $\begin{eqnarray*} n \end{eqnarray*}$ von $\begin{eqnarray*} A \end{eqnarray*}$ ? verwirrt

EDIT: Autor richtiggestellt.

31.01.2024, 17:12

Romaxx

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von Romaxx
Ansonsten könnte es $\begin{eqnarray*} x_k \end{eqnarray*}$ geben mit $\begin{eqnarray*} Ax_k = 0 \end{eqnarray*}$ aber $\begin{eqnarray*} c^Tx_k \to -\infty \end{eqnarray*}$ .

Wie das angesichts des vollen Ranges $\begin{eqnarray*} n \end{eqnarray*}$ von $\begin{eqnarray*} A \end{eqnarray*}$ ? verwirrt

Wie leicht einem unterstellt wird etwas gesagt zu haben. Augenzwinkern

31.01.2024, 18:00

HAL 9000

Auf diesen Beitrag antworten »

Ja, mit Unterstellungen kennst du dich ja bestens aus. Aber zumindest hier hattest du Recht.

Neue Frage »

Antworten »

Minimierungsproblem mit Nebenbedingung

Verwandte Themen