Interior-point method

Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems.

Example solution

John von Neumann[1] suggested an interior-point method of linear programming, which was neither a polynomial-time method nor an efficient method in practice. In fact, it turned out to be slower than the commonly used simplex method.

An interior point method, discovered by Soviet mathematician I. I. Dikin in 1967 and reinvented in the U.S. in the mid-1980s. In 1984, Narendra Karmarkar developed a method for linear programming called Karmarkar's algorithm, which runs in provably polynomial time and is also very efficient in practice. It enabled solutions of linear programming problems that were beyond the capabilities of the simplex method. Contrary to the simplex method, it reaches a best solution by traversing the interior of the feasible region. The method can be generalized to convex programming based on a self-concordant barrier function used to encode the convex set.

Any convex optimization problem can be transformed into minimizing (or maximizing) a linear function over a convex set by converting to the epigraph form.[2] The idea of encoding the feasible set using a barrier and designing barrier methods was studied by Anthony V. Yurii Nesterov and Arkadi Nemirovski came up with a special class of such barriers that can be used to encode any convex set. They guarantee that the number of iterations of the algorithm is bounded by a polynomial in the dimension and accuracy of the solution.[3]

Karmarkar's breakthrough revitalized the study of interior-point methods and barrier problems, showing that it was possible to create an algorithm for linear programming characterized by polynomial complexity and, moreover, that was competitive with the simplex method. Already Khachiyan's ellipsoid method was a polynomial-time algorithm; however, it was too slow to be of practical interest.

The class of primal-dual path-following interior-point methods is considered the most successful. Mehrotra's predictor–corrector algorithm provides the basis for most implementations of this class of methods.[4]

Primal-dual interior-point method for nonlinear optimization

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 }).}$

See also

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

References

1. Dantzig, George B.; Thapa, Mukund N. (2003). Linear Programming 2: Theory and Extensions. Springer-Verlag.
2. Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge: Cambridge University Press. p. 143. ISBN 978-0-521-83378-3. MR 2061575.
3. Wright, Margaret H. (2004). "The interior-point revolution in optimization: History, recent developments, and lasting consequences". Bulletin of the American Mathematical Society. 42: 39–57. doi:10.1090/S0273-0979-04-01040-7. MR 2115066.
4. Potra, Florian A.; Stephen J. Wright (2000). "Interior-point methods". Journal of Computational and Applied Mathematics. 124 (1–2): 281–302. doi:10.1016/S0377-0427(00)00433-7.

Bibliography

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