Interior-point method: Difference between revisions

Revision as of 12:04, 30 November 2023

Revision as of 08:55, 1 December 2023

Line 2:

{{Use dmy dates|date=September 2021}}

[[File:karmarkar.svg|thumb|400x400px|Example search for a solution. Blue lines show constraints, red points show iterated solutions.|alt=]]

'''Interior-point methods''' (also referred to as '''barrier methods''' or '''IPMs''') are [[algorithm]]s for solving [[convexLinear optimizationprogramming|linear]] problems, both linear and [[nonlinear programming|non-linear]] [[convex optimization]] problems. TheyIPMs combine two advantages of previously-known algorithms:

* Theoretically, their run-time is [[Polynomial time|polynomial]] - in—in contrast to the [[simplex method]], whosewhich has exponential run-time may be exponential in the worst case.

* Practically, they run as fast as the simplex method - inmethod—in contrast to the [[ellipsoid method]], which ishas polynomial run-time in theory but is very slow in practice.

In contrast to the simplex method which traverses the ''boundary'' of the feasible region, and the ellipsoid method which bounds the feasible region from ''outside'', an IPM reaches a best solution by traversing the ''interior'' of the [[feasible region]] - hence—hence the name.

== History ==

Line 18:

== Definitions ==

We are given a [[convex program]] of the form: <blockquote>minimize ''f''(''x'')

<math display="block>

such that ''g_i''(''x'') ≤ 0 for ''i'' in 1,...,''m'',

\begin{aligned}

\underset{x \in \mathbb{R}^n}{\text{minimize}}\quad & f(x) \\

and ''x'' in ''G''.</blockquote>where f and the ''g_i'' are [[convex function]]<nowiki/>s and G is a [[convex set]]. Without loss of generality, [[Convex optimization#linear|we can assume that the objective ''f'' is a linear function]]. We assume that the constraint functions belong to some family (e.g. quadratic functions), so that the program can be represented by a finite ''vector of coefficients'' (e.g. the coefficients to the quadratic functions). The dimension of this coefficient vector is called the ''size'' of the program. A ''numerical solver'' for a given family of programs is an algorithm that, given the coefficient vector, generates a sequence of approximate solutions ''x_t'' for ''t''=1,2,..., using finitely many arithmetic operations. A numerical solver is called ''convergent'' if, for any progarm from the family and any positive ''ε''>0, there is some ''T'' (which may depend on the program and on ''ε'') such that, for any ''t''>''T'', the approximate solution ''x_t'' is ''ε-approximate,'' that is:<blockquote>''f''(''x'') - f^* ≤ ''ε''

\text{subject to}\quad & g_i(x) \leq 0 \text{ for } i = 1, \dots, m, \\

& x \in G.

\end{aligned}

</math>

and ''x'' in ''G''.</blockquote>where f and the ''g_i'' are [[convex function]]<nowiki/>s and G is a [[convex set]]. Without loss of generality, [[Convex optimization#linear|we can assume that the objective ''f'' is a linear function]]. We assume that the constraint functions belong to some family (e.g. quadratic functions), so that the program can be represented by a finite ''vector of coefficients'' (e.g. the coefficients to the quadratic functions). The dimension of this coefficient vector is called the ''size'' of the program. A ''numerical solver'' for a given family of programs is an algorithm that, given the coefficient vector, generates a sequence of approximate solutions ''x_t'' for ''t''=1,2,..., using finitely many arithmetic operations. A numerical solver is called ''convergent'' if, for any progarm from the family and any positive ''ε''>0, there is some ''T'' (which may depend on the program and on ''ε'') such that, for any ''t''>''T'', the approximate solution ''x_t'' is ''ε-approximate,'' that is:<blockquote>''f''(''x'') - f^* ≤ ''ε''

''g_i''(''x'') ≤ ''ε'' for ''i'' in 1,...,''m'',