Primal-Duale Verfahren

Unterklasse der Innere-Punkte-Verfahren.

Lineares Programm in Standardform mit vollem Zeilenrang.

Duales Programm mit Schlupfvariablen:

max⁡b⊤λ u.d.N. A⊤λ+s=cs≥0\begin{array}{ll} \max & b^{\top} \lambda \\ \text { u.d.N. } & A^{\top} \lambda+s=c \\ & s \geq 0 \end{array}

mit KKT:

Ax=b,A⊤λ+s=c,xisi=0,i=1,…nx,s≥0\begin{aligned} &A x=b, \\ &A^{\top} \lambda+s=c, \\ &x_{i} s_{i}=0, \quad i=1, \ldots n \\ &x, s \geq 0 \end{aligned}

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,λ,s):=(A⊤λ+s−cAx−bXSe)F(x, \lambda, s):=\left(\begin{array}{c} A^{\top} \lambda+s-c \\ A x-b \\ X S e \end{array}\right)

mit X=diag⁡(x1,…,xn),S=diag⁡(s1,…,sn) und e=(1,…,1)⊤X=\operatorname{diag}\left(x_{1}, \ldots, x_{n}\right), S=\operatorname{diag}\left(s_{1}, \ldots, s_{n}\right) \text { und } e=(1, \ldots, 1)^{\top}

Damit folgt für die KKT:

F(x,λ,s)=0x,s≥0\begin{aligned} &F(x, \lambda, s)=0 \\ &x, s \geq 0 \end{aligned}

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:

JF(x,λ,s)(ΔxΔλΔs)=−F(x,λ,s)J_{F}(x, \lambda, s)\left(\begin{array}{c} \Delta x \\ \Delta \lambda \\ \Delta s \end{array}\right)=-F(x, \lambda, s)

Wir verwenden rb=Ax−b,rc=A⊤λ+s−cr_{b}=A x-b, \quad r_{c}=A^{\top} \lambda+s-c und schreiben somit:

(0A⊤IA00S0X)(ΔxΔλΔs)=(−rc−rb−XSe)\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} \\ -X S e \end{array}\right)

Wobei die erste Matrix die Jacobi Matrix von FF ist.

Üblicherweise würde ein solcher Schritt x,s≥0x,s\ge0 verletzen weswegen wir

(x,λ,s)+α(Δx,Δλ,Δs)(x, \lambda, s)+\alpha(\Delta x, \Delta \lambda, \Delta s)

für einen Liniensuchparameter α∈[0,1)\alpha\in[0,1) mit sehr kleinem α\alpha verwenden. Da man so aber nur sehr langsam voran kommt wählen wir xisi=σμx_{i} s_{i}=\sigma \mu wobei μ\mu das Dualitätsmaß ist und σ∈[0,1]\sigma\in[0,1] der Zentrierungsparameter. Damit gilt

(0A⊤IA00S0X)(ΔxΔλΔs)=(−rc−rb−XSe+σμe)\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} \\ -X S e+\sigma \mu e \end{array}\right)

Algorithmus

Primal-duales pfadfolgendes Innere-Punkte-Verfahren