Interior-point method: Difference between revisions

Revision as of 04:12, 20 March 2024

Revision as of 19:05, 30 March 2024

Line 50:

* The barrier function b(x).

* A policy for determining the penalty parameters ''t_i''.

* The unconstrained-optimization solver used to solve (''P_i'') and find ''x_i'', such as [[Newton's method]]. Note that we can use each ''x_i'' as a starting-point for solving the next problem (''P_i+1'').

The main challenge in proving that the method is polytime is that, as the penalty parameter grows, the solution gets near the boundary, and the function becomes steeper. The run-time of solvers such as [[Newton's method]] becomes longer, and it is hard to prove that the total runtime is polynomial.

Line 58:

* The constraints (and the objective) are linear functions;

* The barrier function is [[Logarithmic barrier function|logarithmic]]: b(x) := - sum''_j'' log(''-g_j''(''x'')).

* The penalty parameter ''t'' is updated geometrically, that is, <math>t_{i+1} := \mu \cdot t_i</math>, where ''μ'' is a constant (they took <math>\mu = 1+0.001\cdot \sqrt{m}</math>, where ''m'' is the number of inequality constraints);

* The solver is Newton's method, and a ''single'' step of Newton is done for each single step in ''t''.

Line 66:

=== Details ===

We are given a convex optimization problem (P) in "standard form":<blockquote>'''minimize ''c''^T''x'' s.t. ''x'' in ''G''''', </blockquote>where ''G'' is convex and closed. We can also assume that ''G'' is bounded (we can easily make it bounded by adding a constraint |''x''|≤''R'' for some sufficiently large ''R'').<ref name=":0" />{{Rp|___location=Sec.4}}

To use the interior-point method, we need a [[self-concordant barrier]] for ''G''. Let ''b'' be an ''M''-self-concordant barrier for ''G'', where ''M''≥1 is the self-concordance parameter. We assume that we can compute efficiently the value of ''b'', its gradient, and its [[Hessian matrix|Hessian]], for every point x in the interior of ''G''.

Line 98:

=== Practical considerations ===

The theoretic guarantees assume that the penalty parameter is increased at the rate <math>\mu = \left(1+r/\sqrt{M}\right)</math>, so the worst-case number of required Newton steps is <math>O(\sqrt{M})</math>. In theory, if ''μ'' is larger (e.g. 2 or more), then the worst-case number of required Newton steps is in <math>O(M)</math>. However, in practice, larger ''μ'' leads to a much faster convergence. These methods are called ''long-step methods''.<ref name=":0" />{{Rp|___location=Sec.4.6}} In practice, if ''μ'' is between 3 and 100, then the program converges within 20-40 Newton steps, regardless of the number of constraints (though the runtime of each Newton step of course grows with the number of constraints). The exact value of ''μ'' within this range has little effect on the performane.<ref name=":3" />{{Rp|___location=chpt.11}}

== Potential-reduction methods ==

For potential-reduction methods, the problem is presented in the ''conic form'':<ref name=":0" />{{Rp|___location=Sec.5}} <blockquote>'''minimize ''c''^T''x'' s.t. ''x'' in ''{b+L} ᚢ K''''', </blockquote>where ''b'' is a vector in R^''n'', L is a [[linear subspace]] in R^''n'' (so ''b''+''L'' is an [[affine plane]]), and ''K'' is a closed pointed [[convex cone]] with a nonempty interior. Every convex program can be converted to the conic form. To use the potential-reduction method (specifically, the extension of [[Karmarkar's algorithm]] to convex programming), we need the following assumptions:<ref name=":0" />{{Rp|___location=Sec.6}}

* A. The feasible set ''{b+L} ᚢ K'' is bounded, and intersects the interior of the cone ''K''.

Line 183:

The function <math>b</math> is self-concordant with parameter ''M''=''m'' (the number of constraints). Therefore, the number of required Newton steps for the path-following method is O(''mn''²), and the total runtime complexity is O(''m''^3/2 ''n''²).{{Clarify|reason=This is the cost for an approximate solution - not an exact solution. The text does not elaborate on this.|date=November 2023}}

===[[Quadratically constrained quadratic program]]s===

Given a quadratically constrained quadratic program of the form:

<math display="block">\begin{aligned}

Line 194:

<math display="block">b(x) := -\sum_{j=1}^m \ln(-f_j(x)).</math> The function <math>b</math> is a self-concordant barrier with parameter ''M''=''m''. The Newton complexity is O(''(m+n)n''²), and the total runtime complexity is O(''m''^1/2 (m+n) ''n''²).

===L_p norm approximation===

Consider a problem of the form

<math display="block">\begin{aligned}

\operatorname{minimize}\quad & \sum_j |v_j - u_j^\top x|_p

\end{aligned},</math>

where each <math>u_j</math> is a vector, each <math>v_j</math> is a scalar, and <math>|\cdot|_p</math> is an [[Lp norm|L_p norm]] with <math>1< p < \infty.</math> After converting to the standard form, we can apply path-following methods with a self-concordant barrier with parameter ''M''=4''m''. The Newton complexity is O(''(m+n)n''²), and the total runtime complexity is O(''m''^1/2 (m+n) ''n''²).

===[[Geometric program]]s===

Consider the problem

<math display="block">\begin{aligned}

Line 210:

\end{aligned}</math>

There is a self-concordant barrier with parameter 2''k''+''m''. The path-following method has Newton complexity O(''mk''²+''k''³+''n''³) and total complexity O((''k+m'')^1/2[''mk''²+''k''³+''n''³]).

=== [[Semidefinite program]]s ===