Interior-point method: Difference between revisions

Revision as of 14:49, 10 September 2024

Revision as of 14:51, 10 September 2024

Line 30:

</math>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 program 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:<math display="block">

\begin{aligned}

& f(x_{t}) - f^{*} \leq \epsilon\,, \\

& g_{i}(x_{t}) \leq \epsilon \quad \text{for} \quad i = 1, \dots, m\,, \\

& x \in G\,,

\end{aligned}

where </math> </blockquote>where f<sup>^{*}</supmath> 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'' is some data-dependent constant, e.g., the difference between the largest and smallest value in the feasible set. 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 ==