Interior-point method: Difference between revisions

Revision as of 08:55, 1 December 2023

Revision as of 08:57, 10 December 2023

Line 31:

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

''x'' in ''G'',</blockquote>where f^* is the optimal solution. A solver is called ''polynomial'' if the total number of arithmetic operations in the first ''T'' steps is at most<blockquote>poly(problem-size) * log(''V''/''ε''),</blockquote>where ''V'' representsis some data-dependent constant, e.g., the difference between the largest and smallest value in the coefficientfeasible vectorset. In other words, ''V''/''ε'' is the "relative accuracy" of the solution - the accuracy w.r.t. the largest coefficient. log(''V''/''ε'') represents the number of "accuracy digits". Therefore, a solver is 'polynomial' if each additional digit of accuracy requires a number of operations that is polynomial in the problem size.

== Types ==

Line 43:

=== Idea ===

Given a convex optimization program (P) with constraints, we can convert it to an ''unconstrained'' program by adding a [[barrier function]]. Specifically, let ''b'' be a smooth convex function, defined in the interior of the feasible region ''G'', such that for any sequence {''x_j'' in interior(G)} whose limit is on the boundary of ''G'': <math>\lim_{j\to \infty} b(x_j)=\infty</math>. We also assume that ''b'' is non-degenerate, that is: <math>b''(x)</math> is [[Positive-definite function|positive definite]] for all x in interior(G). Now, consider the family of programs:<blockquote>(''P_t'') minimize t * f(x) + b(x)</blockquote>Technically the program is restricted, since ''b'' is defined only in the interior of ''G''. But practically, it is possible to solve it as an unconstrained program, since any solver trying to minimize the function will not approach the boundary, where ''b'' approaches infinity. Therefore, (''P_t'') has a unique solution - denote it by ''x''*(''t''). The function ''x''* is a continuous function of ''t'', which is called the ''central path''. All limit points of ''x''*, as ''t'' approaches infinity, are optimal solutions of the original program (P).

A '''path-following method''' is a method of tracking the function ''x''* along a certain increasing sequence t₁,t₂,..., that is: computing a good-enough approximation ''x_i'' to the point ''x''*(''t_i''), such that the difference ''x_i'' - ''x''*(''t_i'') approaches 0 as ''i'' approaches infinity; then the sequence ''x_i'' approaches the optimal solution of (P). This requires to specify three things:

* The barrier function b(x).