View source for Interior-point methods in mathematical programming

<!--
i1101001.png
$#A+1 = 17 n = 0
$#C+1 = 17 : ~/encyclopedia/old_files/data/I110/I.1100100 Interior\AAhpoint methods in mathematical programming
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

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

$$ 
 \min  _ { x } \left \{ {g _ {0} ( x ) } : {g _ {i} ( x ) \leq  0,  i = 1 \dots m } \right \} ,
$$

where  $  {g _ {i} } : {\mathbf R  ^ {n} } \rightarrow \mathbf R $
are convex functions, he introduced the logarithmic barrier function

$$ 
L ( x; \mu ) = g _ {0} ( x ) - \mu \sum _ {i = 1 } ^ { m }  { \mathop{\rm ln} } ( - g _ {i} ( x ) ) ,
$$

parametrized by  $  \mu \geq  0 $. 
Under certain conditions, concerning the existence of a Slater point (i.e. a point that satisfies the Slater regularity condition  $  g _ {i} < 0 $, 
$  i = 1 \dots m $; 
cf. also [[Mathematical programming|Mathematical programming]]) and boundedness of level-sets, this function has a minimizer  $  x ( \mu ) $
for fixed  $  \mu $; 
for  $  \mu $
converging to zero, it has been shown that  $  x ( \mu ) $
converges to an optimal solution. The set

$$ 
\left \{ {x ( \mu ) } : {\mu > 0 } \right \}
$$

is called the central path of the optimization problem. The generic interior-point method, or path-following method, works as follows. Given a value  $  \mu $, 
compute an approximate minimizer of  $  L ( x; \mu ) $; 
reduce  $  \mu $
and proceed. Different methods are obtained by: using different barrier functions, varying the updating scheme for  $  \mu $, 
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  $  L ( x; \mu ) $
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,  $  {\mathcal l} _ {p} $-
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>