Interior-point method

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

File:Karmarkar.png

Example solution

The interior point method was invented by John von Neumann. Von Neumann suggested a new method of linear programming, using the homogeneous linear system of Gordan (1873) which was later popularized by Karmarkar's algorithm, developed by Narendra Karmarkar in 1984 for linear programming. The method consists of a self-concordant barrier function used to encode the convex set. Contrary to the simplex method, it reaches an optimal solution by traversing the interior of the feasible region.

Any convex optimization problem can be transformed into minimizing (or maximizing) a linear function over a convex set. The idea of encoding the feasible set using a barrier and designing barrier methods was studied in the early 1960s by, amongst others, Anthony V. Fiacco and Garth P. McCormick. These ideas were mainly developed for general nonlinear programming, but they were later abandoned due to the presence of more competitive methods for this class of problems (e.g. sequential quadratic programming).

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.

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, in practice 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.

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 $f(x)$ subject to $c(x)\geq 0~~x\in \mathbb {R} ^{n},c(x)\in \mathbb {R} ^{m}~~~~~~(1)$.

The logarithmic barrier function associated with (1) is

$B(x,\mu )=f(x)-\mu ~\sum _{i=1}^{m}\ln(c_{i}(x))~~~~~(2)$

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

The barrier function gradient is

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

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

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

$\forall _{i=1}^{m}c_{i}(x)\lambda _{i}=\mu ~~~~~~~(4)$

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

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

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

$g-A^{T}\lambda =0~~~~~~(5)$

where the matrix $A$ is the constraint $c(x)$ Jacobian.

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

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

${\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 $W$ is the Hessian matrix of $f(x)$ and $\Lambda$ is a diagonal matrix of $\lambda$.

Because of (1), (4) the condition

$\lambda \geq 0$

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

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

See also

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

Bibliography

• 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 3-540-35445-X. MR 2265882.
• Karmarkar, N. (1984). "Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84" (PDF): 302. doi:10.1145/800057.808695. ISBN 0-89791-133-4. {{cite journal}}: |chapter= ignored (help); Cite journal requires |journal= (help)
• Mehrotra, Sanjay (1992). "On the Implementation of a Primal-Dual Interior Point Method". SIAM Journal on Optimization. 2 (4): 575. doi:10.1137/0802028.
• Nocedal, Jorge (1999). Numerical Optimization. New York, NY: Springer. ISBN 0-387-98793-2. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
• 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 0-89871-382-X.
• Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press.