[Artikel] Optimierung: Quadratische Programme

22.01.2011, 17:46

tigerbine

[Artikel] Optimierung: Quadratische Programme

Dieser Artikel beschäftigt sich mit quadratischen Programmen. Wichtig ist hierbei, dass die Nebenbedingungen wieder linear sind. Man unterscheidet:

Zitat:

(i) quad. NLP mit Gleichheitsrestriktionen

Gegeben sei $\begin{eqnarray*} Q \in \mathbb R^{n \times n} \end{eqnarray*}$ symmetrisch, $\begin{eqnarray*} c, b_j \in \mathbb R^{n } \end{eqnarray*}$ und $\begin{eqnarray*} \gamma, \beta_j \in \mathbb R \end{eqnarray*}$ . Betrachtet wird das Problem:

$\begin{eqnarray*} \min ~f(x):=\frac{1}{2}x^TQx + c^Tx+\gamma \end{eqnarray*}$

$\begin{eqnarray*} \text{u.d.N. } \quad b_j^Tx=\beta_j~(j=1,...,p) \end{eqnarray*}$

(ii) quad. NLP mit Gleichheits- und Ungleichheitsrestriktionen

Gegeben sei $\begin{eqnarray*} Q \in \mathbb R^{n \times n} \end{eqnarray*}$ symmetrisch, $\begin{eqnarray*} c, b_j,a_i \in \mathbb R^{n } \end{eqnarray*}$ und $\begin{eqnarray*} \gamma, \beta_j , \alpha_i\in \mathbb R \end{eqnarray*}$ . Betrachtet wird das Problem:

$\begin{eqnarray*} \min ~f(x):=\frac{1}{2}x^TQx + c^Tx+\gamma \end{eqnarray*}$

$\begin{eqnarray*} \text{u.d.N. } \quad b_j^Tx=\beta_j~(j=1,...,p),~a_i^Tx \leq \alpha_i \end{eqnarray*}$

PDF zur Lösungsstrategie - aktive Menge.

Es sei betont, dass zur Wohldefiniertheit (Regularität des LGS in Schritt 2) nötig ist, dass die Matrix Q positiv definit (auf einem bestimmten Tangentialkegel == hinreichende. Bed. 2ter Ordnung) ist, sowie die lineare Unabhängigkeit in den Nebenbedingungen. Dies garantiert die eindeutig Lösung der Lagrange-Newton-Gleichung (siehe PDF).

In der Lösung von (ii) sind gewisse Ungleichheitsrestriktionen aktiv. Die Strategie der aktiven Menge stellt eine Schätzung für die zug. Indexmenge auf und löst das entstehende Problem von der Form (i). Je nach Ergebnis, nimmt man einen Index heraus, läßt die Menge gleich oder nimmt einen Index hinzu.

Der gelinkte PDf enthält auch ein sehr schönes Rechnenbeispiel im $\begin{eqnarray*} \mathbb R^2 \end{eqnarray*}$

Neue Frage »

Antworten »

[Artikel] Optimierung: Quadratische Programme

Verwandte Themen