Interior-point method

The primal-dual method's idea is easy to demonstrate for constrained nonlinear optimization. For simplicity, consider the all-inequality version of a nonlinear optimization problem:

minimize ${\displaystyle f(x)}$ subject to ${\displaystyle c_{i}(x)\geq 0~{\text{for}}~i=1,\ldots ,m,~x\in \mathbb {R} ^{n},}$ where ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} ,c_{i}:\mathbb {R} ^{n}\rightarrow \mathbb {R} \quad (1).}$

The logarithmic barrier function associated with (1) is

${\displaystyle B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\log(c_{i}(x)).\quad (2)}$

Here ${\displaystyle \mu }$ is a small positive scalar, sometimes called the "barrier parameter". As ${\displaystyle \mu }$ converges to zero the minimum of ${\displaystyle B(x,\mu )}$ should converge to a solution of (1).

The barrier function gradient is

${\displaystyle g_{b}=g-\mu \sum _{i=1}^{m}{\frac {1}{c_{i}(x)}}\nabla c_{i}(x),\quad (3)}$

where ${\displaystyle g}$ is the gradient of the original function ${\displaystyle f(x)}$, and ${\displaystyle \nabla c_{i}}$ is the gradient of ${\displaystyle c_{i}}$.

In addition to the original ("primal") variable ${\displaystyle x}$ we introduce a Lagrange multiplier inspired dual variable ${\displaystyle \lambda \in \mathbb {R} ^{m}}$

${\displaystyle c_{i}(x)\lambda _{i}=\mu ,\forall i=1,\ldots ,m.\quad (4)}$

(4) is sometimes called the "perturbed complementarity" condition, for its resemblance to "complementary slackness" in KKT conditions.

We try to find those ${\displaystyle (x_{\mu },\lambda _{\mu })}$ for which the gradient of the barrier function is zero.

Applying (4) to (3), we get an equation for the gradient:

${\displaystyle g-A^{T}\lambda =0,\quad (5)}$

where the matrix ${\displaystyle A}$ is the Jacobian of the constraints ${\displaystyle c(x)}$.

The intuition behind (5) is that the gradient of ${\displaystyle f(x)}$ should lie in the subspace spanned by the constraints' gradients. The "perturbed complementarity" with small ${\displaystyle \mu }$ (4) can be understood as the condition that the solution should either lie near the boundary ${\displaystyle c_{i}(x)=0}$, or that the projection of the gradient ${\displaystyle g}$ on the constraint component ${\displaystyle c_{i}(x)}$ normal should be almost zero.

Applying Newton's method to (4) and (5), we get an equation for ${\displaystyle (x,\lambda )}$ update ${\displaystyle (p_{x},p_{\lambda })}$:

${\displaystyle {\begin{pmatrix}W&-A^{T}\\\Lambda A&C\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}-g+A^{T}\lambda \\\mu 1-C\lambda \end{pmatrix}},}$

where ${\displaystyle W}$ is the Hessian matrix of ${\displaystyle B(x,\mu )}$, ${\displaystyle \Lambda }$ is a diagonal matrix of ${\displaystyle \lambda }$, and ${\displaystyle C}$ is a diagonal matrix with ${\displaystyle C_{ii}=c_{i}(x)}$.

Because of (1), (4) the condition

${\displaystyle \lambda \geq 0}$

should be enforced at each step. This can be done by choosing appropriate ${\displaystyle \alpha }$:

${\displaystyle (x,\lambda )\to (x+\alpha p_{x},\lambda +\alpha p_{\lambda }).}$

• Affine scaling
• Augmented Lagrangian method
• Penalty method
• Karush–Kuhn–Tucker conditions

• Dikin, I.I. (1967). "Iterative solution of problems of linear and quadratic programming". Dokl. Akad. Nauk SSSR. 174 (1): 747–748.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 978-3-540-35445-1. MR 2265882.
• Karmarkar, N. (1984). "A new polynomial-time algorithm for linear programming" (PDF). Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84. p. 302. doi:10.1145/800057.808695. ISBN 0-89791-133-4. Archived from the original (PDF) on 28 December 2013.
• Mehrotra, Sanjay (1992). "On the Implementation of a Primal-Dual Interior Point Method". SIAM Journal on Optimization. 2 (4): 575–601. doi:10.1137/0802028.
• Nocedal, Jorge; Stephen Wright (1999). Numerical Optimization. New York, NY: Springer. ISBN 978-0-387-98793-4.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 10.11. Linear Programming: Interior-Point Methods". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Wright, Stephen (1997). Primal-Dual Interior-Point Methods. Philadelphia, PA: SIAM. ISBN 978-0-89871-382-4.
• Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press.