Namespaces
Variants
Actions

Difference between revisions of "Interior-point methods in mathematical programming"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
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]]].
 
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
 
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>
+
$$
 +
\min  _ { x } \left \{ {g _ {0} ( x ) } : {g _ {i} ( x ) \leq  0,  i = 1 \dots m } \right \} ,
 +
$$
  
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
+
where $  {g _ {i} } : {\mathbf R  ^ {n} } \rightarrow \mathbf R $
 +
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>
+
$$
 +
L ( x; \mu ) = g _ {0} ( x ) - \mu \sum _ {i = 1 } ^ { m }  { \mathop{\rm ln} } ( - g _ {i} ( x ) ) ,
 +
$$
  
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
+
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
  
<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>
+
$$
 +
\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 <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.
+
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 <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]]].
+
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, <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]].
+
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====
 
====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>
 
<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>

Latest revision as of 22:13, 5 June 2020


A class of theoretically and practically efficient techniques for solving certain structured convex programming problems, including 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 [a6].

Interior-point methods originate from K.R. Frisch (1955), [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) 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), 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 [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 [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 [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, [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.

References

[a1] K.R. Frisch, "The logarithmic potential method for convex programming" Institute of Economics, Univ. Oslo (1955)
[a2] A.V. Fiacco, G.P. McCormick, "Nonlinear programming: sequential unconstrained minimization techniques" , Classics in Applied Math. , 4 , SIAM (1990) (reprint)
[a3] N.K. Karmarkar, "A new polynomial-time algorithm for linear programming" Combinatorica , 4 (1984) pp. 373–395
[a4] 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
[a5] Yu. Nesterov, A.S. Nemirovskii, "Interior point polynomial algorithms in convex programming" , Studies in Applied Mathematics , 13 , SIAM (1994) (In Russian)
[a6] "Interior point view of mathematical programming" T. Terlaky (ed.) , Kluwer Acad. Publ. (1996)
[a7] D. den Hertog, "Interior point approach to linear, quadratic and convex programming" , Kluwer Acad. Publ. (1994)
How to Cite This Entry:
Interior-point methods in mathematical programming. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Interior-point_methods_in_mathematical_programming&oldid=47387
This article was adapted from an original article by B. Jansen (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article