Mehrotra predictor–corrector method: Difference between revisions

Revision as of 14:11, 9 May 2017

Revision as of 20:19, 9 May 2017

Line 12:

== Derivation ==

The derivation of this section follows the outline by Nocedal and Wright .<ref name=":0">{{Cite book|title=Numerical Optimisation|last=Nocedal|first=Jorge|last2=Wright|first2=Stephen J.|publisher=Springer|year=2006|isbn=978-0387-30303-1|___location=United States of America|pages=392-417392–417, 448-496448–496}}</ref>.

=== Predictor step - Affine scaling direction ===

Line 51:

<math>J(x,\lambda,s) = \begin{bmatrix} \nabla_x F & \nabla_\lambda F & \nabla_s F\end{bmatrix},</math>

is the Jacobian of F.

Thus, the system becomes

Line 62:

<math>\mu=\frac{1}{n}\sum_{i=1}^n x_is_i = \frac{x^Ts}{n}.</math>

For a value of the centering parameter, <math>\sigma\in[0,1],</math> the centering step can be computed as the solution to

<math>\begin{bmatrix} 0 & A^T & I \\ A & 0 & 0 \\ S & 0 & X \end{bmatrix}

Line 71:

Considering the system used to compute the affine scaling direction defined in the above, one can note that taking a full step in the affine scaling direction does results in the complementarity condition not being satisfied:

<math>\left(x_i+\Delta x_i^\text{aff}\right)\left(s_i+\Delta s_i^\text{aff}\right) = x_is_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} \ne 0.</math>

As such, a system can be defined to compute a step that attempts to correct for this error. This system relies on the previous computation of the affine scaling direction.

Line 80:

=== Aggregated system - Center-corrector direction ===

The predictor, corrector and centering contributions to the system right hand side can be aggregated into a single system. This system will depend on the previous computation of the affine scaling direction, however, the system matrix will be identical to that of the predictor step such that its factorization can be reused.

The aggregated system is

Line 103:

\end{align}</math>

Here, <math>\mu_\text{aff}</math> is the duality measure of the affine step and <math>\mu</math> is the duality measure of the previous iteration .<ref name=":0" />.

== Step lengths ==

In practical implementations, a version of line search is performed to obtain the maximal step length that can be taken in the search direction without violating nonnegativity, <math>(x,s) \geq 0</math> .<ref name=":0" />.

== Adaptation to Quadratic Programming ==

Although the modifications presented by Mehrotra were intended for interior point algorithms for linear programming, the ideas have been extended and successfully applied to [[quadratic programming]] as well .<ref name=":0" />.

==References==

Line 117:

{{DEFAULTSORT:Mehrotra predictor-corrector method}}

[[Category:Optimization algorithms and methods]]

{{mathapplied-stub}}