View source for Interior-point methods in mathematical programming

A class of theoretically and practically efficient techniques for solving certain structured [[Convex programming|convex programming]] problems, including [[Linear programming|linear programming]] problems. Besides, ideas arising from research on interior-point methods have influenced the areas of non-convex programming, combinatorial optimization and decomposition methods. A recent survey is given in [[#References|[a6]]].

Interior-point methods originate from K.R. Frisch (1955), [[#References|[a1]]]. To solve a convex programming problem

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i1101001.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i1101002.png" /> are convex functions, he introduced the logarithmic barrier function

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i1101003.png" /></td> </tr></table>

parametrized by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i1101004.png" />. Under certain conditions, concerning the existence of a Slater point (i.e. a point that satisfies the Slater regularity condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i1101005.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i1101006.png" />; cf. also [[Mathematical programming|Mathematical programming]]) and boundedness of level-sets, this function has a minimizer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i1101007.png" /> for fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i1101008.png" />; for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i1101009.png" /> converging to zero, it has been shown that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i11010010.png" /> converges to an optimal solution. The set

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i11010011.png" /></td> </tr></table>

is called the central path of the optimization problem. The generic interior-point method, or path-following method, works as follows. Given a value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i11010012.png" />, compute an approximate minimizer of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i11010013.png" />; reduce <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i11010014.png" /> and proceed. Different methods are obtained by: using different barrier functions, varying the updating scheme for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i11010015.png" />, the method used for minimizing the barrier function (mainly a variant of the [[Newton method|Newton method]]), and the criterion that judges approximation to the exact minimizer. The latter aspect is related to the use of neighbourhoods of the central path.

Interior-point techniques were extensively investigated in the 1960{}s (see [[#References|[a2]]]) and early 1970{}s. Computational difficulties with minimizing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i11010016.png" /> efficiently caused these methods to get out of sight. In 1984, N.K. Karmarkar [[#References|[a3]]] proved a variant of an interior-point method to have polynomial worst-case complexity when applied to the linear programming problem. Thereafter, many new variants have been theoretically analyzed as well as implemented. Especially, primal-dual interior-point algorithms (i.e., methods generating primal and dual solutions in each iteration) proved to be extremely efficient to solve large-scale linear programming problems, see [[#References|[a4]]].

The analysis that shows which properties make it possible to prove polynomial convergence of interior-point methods for classes of convex programming problems should mainly be attributed to Yu. Nesterov and A.S. Nemirovskii, [[#References|[a5]]]. These classes include: convex quadratic programming with linear and/or quadratic constraints, geometric programming, entropy optimization, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110100/i11010017.png" />-optimization, and semi-definite optimization. The self-concordance condition they introduced for convex (barrier) functions essentially shows when such a function can be efficiently (i.e., with quadratic convergence) minimized using the [[Newton method|Newton method]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  K.R. Frisch,   "The logarithmic potential method for convex programming"  ''Institute of Economics, Univ. Oslo''  (1955)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  A.V. Fiacco,   G.P. McCormick,   "Nonlinear programming: sequential unconstrained minimization techniques" , ''Classics in Applied Math.'' , '''4''' , SIAM  (1990)  (reprint)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  N.K. Karmarkar,   "A new polynomial-time algorithm for linear programming"  ''Combinatorica'' , '''4'''  (1984)  pp. 373–395</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  I.J. Lustig,   R.E. Marsten,   D.F. Shanno,   "Interior point methods: computational state of the art"  ''ORSA J. Computing'' , '''6'''  (1994)  pp. 1–15</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  Yu. Nesterov,   A.S. Nemirovskii,   "Interior point polynomial algorithms in convex programming" , ''Studies in Applied Mathematics'' , '''13''' , SIAM  (1994)  (In Russian)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  "Interior point view of mathematical programming"  T. Terlaky (ed.) , Kluwer Acad. Publ.  (1996)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  D. den Hertog,   "Interior point approach to linear, quadratic and convex programming" , Kluwer Acad. Publ.  (1994)</TD></TR></table>