Interior-point method

The primal-dual method's idea is easy to demonstrate for constrained nonlinear optimization. For simplicity, consider the following nonlinear optimization problem with inequality constraints:

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

This inequality-constrained optimization problem is solved by converting it into an unconstrained objective function whose minimum we hope to find efficiently. Specifically, 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 gradient of a differentiable function ${\displaystyle h:\mathbb {R} ^{n}\to \mathbb {R} }$ is denoted ${\displaystyle \nabla h}$. The gradient of the barrier function is

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

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 ,\quad \forall i=1,\ldots ,m.\quad (4)}$

Equation (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.

Substituting ${\displaystyle 1/c_{i}(x)=\lambda _{i}/\mu }$ from (4) into (3), we get an equation for the gradient:

${\displaystyle \nabla B(x_{\mu },\lambda _{\mu })=\nabla f(x_{\mu })-J(x_{\mu })^{T}\lambda _{\mu }=0,\quad (5)}$

where the matrix ${\displaystyle J}$ 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 \nabla f}$ on the constraint component ${\displaystyle c_{i}(x)}$ normal should be almost zero.

Let ${\displaystyle (p_{x},p_{\lambda })}$ be the search direction for iteratively updating ${\displaystyle (x,\lambda )}$. Applying Newton's method to (4) and (5), we get an equation for ${\displaystyle (p_{x},p_{\lambda })}$:

${\displaystyle {\begin{pmatrix}H(x,\lambda )&-J(x)^{T}\\\operatorname {diag} (\lambda )J(x)&\operatorname {diag} (c(x))\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}-\nabla f(x)+J(x)^{T}\lambda \\\mu 1-\operatorname {diag} (c(x))\lambda \end{pmatrix}},}$

where ${\displaystyle H}$ is the Hessian matrix of ${\displaystyle B(x,\mu )}$, ${\displaystyle \operatorname {diag} (\lambda )}$ is a diagonal matrix of ${\displaystyle \lambda }$, and ${\displaystyle \operatorname {diag} (c(x))}$ is the diagonal matrix of ${\displaystyle c(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
• Chambolle-Pock algorithm
• Karush–Kuhn–Tucker conditions
• Penalty method

• 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.