Método predictor-corrector de Mehrotra

Un programa lineal siempre puede formularse en la forma estándar.

${\displaystyle {\begin{aligned}&{\underset {x}{\min }}&q(x)&=c^{T}x,\\&{\text{st}}&Ax&=b,\\&\;&x&\geq 0,\end{aligned}}}$

dónde${\displaystyle c\in \mathbb {R} ^{n\times 1},\;A\in \mathbb {R} ^{m\times n}}$y${\displaystyle b\in \mathbb {R} ^{m\times 1}}$definir el problema con${\displaystyle m}$restricciones y${\displaystyle n}$ecuaciones mientras${\displaystyle x\in \mathbb {R} ^{n\times 1}}$es un vector de variables.

Las condiciones de Karush-Kuhn-Tucker (KKT) para el problema son:

${\displaystyle {\begin{aligned}A^{T}\lambda +s&=c,\;\;\;{\text{(Condición de gradiente de Lagrange)}}\\Ax&=b,\;\;\;{\text{(Condición de factibilidad)}}\\XSe&=0,\;\;\;{\text{(Condición de complementariedad)}}\\(x,s)&\geq 0,\end{aligned}}}$

dónde${\displaystyle X={\text{diag}}(x)}$y${\displaystyle S={\text{diag}}(s)}$De dónde${\displaystyle e=(1,1,\dots ,1)^{T}\in \mathbb {R} ^{n\times 1}}$.

Estas condiciones pueden reformularse como un mapeo${\displaystyle F:\mathbb {R} ^{2n+m}\rightarrow \mathbb {R} ^{2n+m}}$como sigue

${\displaystyle {\begin{aligned}F(x,\lambda ,s)={\begin{bmatrix}A^{T}\lambda +sc\\Ax-b\\XSe\end{bmatrix}}&=0\\(x,s)&\geq 0\end{aligned}}}$

El método predictor-corrector funciona entonces utilizando el método de Newton para obtener la dirección de escalamiento afín . Esto se logra resolviendo el siguiente sistema de ecuaciones lineales:

${\displaystyle J(x,\lambda ,s){\begin{bmatrix}\Delta x^{\text{aff}}\\\Delta \lambda ^{\text{aff}}\\\Delta s^{\text{aff}}\end{bmatrix}}=-F(x,\lambda ,s)}$

dónde${\displaystyle J}$, definido como

${\displaystyle J(x,\lambda ,s)={\begin{bmatrix}\nabla _{x}F&\nabla _{\lambda }F&\nabla _{s}F\end{bmatrix}},}$

es el jacobiano de F.

De esta forma, el sistema se convierte en

${\displaystyle {\begin{bmatrix}0&A^{T}&I\\A&0&0\\S&0&X\end{bmatrix}}{\begin{bmatrix}\Delta x^{\text{aff}}\\\Delta \lambda ^{\text{aff}}\\\Delta s^{\text{aff}}\end{bmatrix}}={\begin{bmatrix}-r_{c}\\-r_{b}\\-XSe\end{bmatrix}},\;\;\;r_{c}=A^{T}\lambda +sc,\;\;\;r_{b}=Ax-b}$

El valor promedio de los productos${\displaystyle x_{i}s_{i},\;i=1,2,\dots ,n}$constituyen una medida importante de la deseabilidad de un determinado conjunto.${\displaystyle (x^{k},s^{k})}$(los superíndices denotan el valor del número de iteración,${\displaystyle k}$, del método). Esto se denomina medida de dualidad y se define por

${\displaystyle \mu ={\frac {1}{n}}\sum _{i=1}^{n}x_{i}s_{i}={\frac {x^{T}s}{n}}.}$

Para un valor del parámetro de centrado,${\displaystyle \sigma \in [0,1],}$El paso de centrado se puede calcular como la solución a

${\displaystyle {\begin{bmatrix}0&A^{T}&I\\A&0&0\\S&0&X\end{bmatrix}}{\begin{bmatrix}\Delta x^{\text{cen}}\\\Delta \lambda ^{\text{cen}}\\\Delta s^{\text{cen}}\end{bmatrix}}={\begin{bmatrix}-r_{c}\\-r_{b}\\-XSe+\sigma \mu e\end{bmatrix}}}$

Considerando el sistema utilizado para calcular la dirección de escalamiento afín definida anteriormente, se puede observar que dar un paso completo en la dirección de escalamiento afín da como resultado que no se satisfaga la condición de complementariedad:

${\displaystyle \left(x_{i}+\Delta x_{i}^{\text{aff}}\right)\left(s_{i}+\Delta s_{i}^{\text{aff}}\right)=x_{i}s_{i}+x_{i}\Delta s_{i}^{\text{aff}}+s_{i}\Delta x_{i}^{\text{aff}}+\Delta x_{i}^{\text{aff}}\Delta s_{i}^{\text{aff}}=\Delta x_{i}^{\text{aff}}\Delta s_{i}^{\text{aff}}\neq 0.}$

Por lo tanto, se puede definir un sistema para calcular un paso que intente corregir este error. Este sistema se basa en el cálculo previo de la dirección de escalado afín.

${\displaystyle {\begin{bmatrix}0&A^{T}&I\\A&0&0\\S&0&X\end{bmatrix}}{\begin{bmatrix}\Delta x^{\text{cor}}\\\Delta \lambda ^{\text{cor}}\\\Delta s^{\text{cor}}\end{bmatrix}}={\begin{bmatrix}0\\0\\-\Delta X^{\text{aff}}\Delta S^{\text{aff}}e\end{bmatrix}}}$

Las contribuciones del predictor, el corrector y el centrado al lado derecho del sistema pueden agregarse en un único sistema. Este sistema dependerá del cálculo previo de la dirección de escalado afín; sin embargo, la matriz del sistema será idéntica a la del paso predictor, de modo que su factorización pueda reutilizarse.

El sistema agregado es

${\displaystyle {\begin{bmatrix}0&A^{T}&I\\A&0&0\\S&0&X\end{bmatrix}}{\begin{bmatrix}\Delta x\\\Delta \lambda \\\Delta s\end{bmatrix}}={\begin{bmatrix}-r_{c}\\-r_{b}\\-XSe-\Delta X^{\text{aff}}\Delta S^{\text{aff}}e+\sigma \mu e\end{bmatrix}}}$

El algoritmo predictor-corrector calcula primero la dirección de escalado afín. En segundo lugar, resuelve el sistema agregado para obtener la dirección de búsqueda de la iteración actual.