Primal-Duale Verfahren

Unterklasse der Innere-Punkte-Verfahren.

Lineares Programm in Standardform mit vollem Zeilenrang.

Duales Programm mit Schlupfvariablen:

$$\begin{array}{ll}\max & b^{\top }\lambda \\ \text{ u.d.N. }& A^{\top }\lambda +s=c\\ & s\ge 0\end{array}$$

mit KKT:

$$\begin{array}{rl}& Ax=b,\\ & A^{\top }\lambda +s=c,\\ & x_i{s}_i=0,i=1,\dots n\\ & x,s\ge 0\end{array}$$

Da wir wissen, dass die Zielfunktion konvex ist und die Nebenbedingungen affin-linear sind, ist ein Punkt, der die KKT Bedingungen erfüllt direkt ein globales Optimum.

Deswegen definieren wir eine Funktion über alle zulässigen Punkte und Lagrange-Multiplikatoren um genau diese KKT-Punkte zu finden:

$$F(x,\lambda ,s):=\left(\begin{array}{c}{A}^{\top }\lambda +s-c\\ Ax-b\\ XSe\end{array}\right)$$

mit $X=\mathrm{diag}\left(x_1,\dots ,x_n\right),S=\mathrm{diag}\left(s_1,\dots ,s_n\right)\text{ und }e=(1,\dots ,1{)}^{\top }$

Damit folgt für die KKT:

$$\begin{array}{rl}& F(x,\lambda ,s)=0\\ & x,s\ge 0\end{array}$$

Allgemeines Vorgehen

1. Suchrichtung bestimmen → mit Newton Verfahren
2. Maß für den wünschenswertesten Punkt entlang der Suchrichtung → Dualitätsmaß

Neue Suchrichtung erhalten wir mit Jacobi Matrix basierend auf dem Newton Verfahren:

$$J_F(x,\lambda ,s)\left(\begin{array}{c}\Delta x\\ \Delta \lambda \\ \Delta s\end{array}\right)=-F(x,\lambda ,s)$$

Wir verwenden $r_b=Ax-b,r_c=A^{\top }\lambda +s-c$ und schreiben somit:

$$\left(\begin{array}{ccc}0& A^{\top }& I\\ A& 0& 0\\ S& 0& X\end{array}\right)\left(\begin{array}{c}\Delta x\\ \Delta \lambda \\ \Delta s\end{array}\right)=\left(\begin{array}{c}-r_c\\ -r_b\\ -XSe\end{array}\right)$$

Wobei die erste Matrix die Jacobi Matrix von $F$ ist.

Üblicherweise würde ein solcher Schritt $x,s\ge 0$ verletzen weswegen wir $(x,\lambda ,s)+\alpha (\Delta x,\Delta \lambda ,\Delta s)$ für einen Liniensuchparameter $\alpha \in [0,1)$ mit sehr kleinem $\alpha$ verwenden. Da man so aber nur sehr langsam voran kommt wählen wir $x_i{s}_i=\sigma \mu$ wobei $\mu$ das Dualitätsmaß ist und $\sigma \in [0,1]$ der Zentrierungsparameter. Damit gilt

$$\left(\begin{array}{ccc}0& A^{\top }& I\\ A& 0& 0\\ S& 0& X\end{array}\right)\left(\begin{array}{c}\Delta x\\ \Delta \lambda \\ \Delta s\end{array}\right)=\left(\begin{array}{c}-r_c\\ -r_b\\ -XSe+\sigma \mu e\end{array}\right)$$

Algorithmus

Primal-duales pfadfolgendes Innere-Punkte-Verfahren