Interior-point method: Difference between revisions

Revision as of 09:10, 10 December 2023

Revision as of 10:48, 10 December 2023

Line 69:

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''.

For every ''t''>0, we define the ''penalized objective'' '''f_t(x) := ''c''^T''x +'' b(''x'')'''. We define the path of minimizers by: '''x*(t) := arg min f_t(x)'''. We apporimate this path along an increasing sequence ''t_i''. The sequence is initialized by a certain non-trivial two-phase initialization procedure. Then, it is updated according to the following rule: (where ''r''>0 is a parameter called the ''penalty rate''):<blockquote><math>t_{i+1} := \left(1+r/mu \sqrt{M}\right)cdot t_i</math>.</blockquote>

For each ''t_i'', we find an approximate minimum of ''f_ti'', denoted by ''x_i''. The approximate minimum is chosen to satisfy the following "closeness condition" (where ''L'' is the ''path tolerance''):<blockquote><math>\sqrt{[\nabla_x f_t(x_i)]^T [\nabla_x^2 f_t(x_i)]^{-1} [\nabla_x f_t(x_i)]} \leq L</math>.</blockquote>To find ''x_i''₊₁, we start with ''x_i'' and apply the [[damped Newton method]]. We apply several steps of this method, until the above "closeness relation" is satisfied. The first point that satisfies this relation is denoted by ''x_i''₊₁.<ref name=":0" />{{Rp|___location=Sec.4}}

=== Convergence and complexity ===

The convergence rate of the method is given by the following formula, for every ''i'':<ref name=":0" />{{Rp|___location=Prop.4.4.1}}<blockquote><math>c^T x_i - c^* \leq \frac{2 M}{t_0} \left[1mu^{-i} +</math></blockquote><math>\mu = \frac{left(1+r}{/\sqrt{M}}\right]^{-i}) </math>. Taking <math>\mu = \left(1+r/blockquote\sqrt{M}\right) </math>The, the number of Newton steps required to go from ''x_i'' to ''x_i''₊₁ is at most a fixed number, that depends only on ''r'' and ''L''. In particular, the total number of Newton steps required to find an ''ε''-approximate solution (i.e., finding ''x'' in ''G'' such that ''c''^T''x'' - c* ≤ ''ε'') is at most:<ref name=":0" />{{Rp|___location=Thm.4.4.1}}<blockquote><math>O(1) \cdot \sqrt{M} \cdot \ln\left(\frac{M}{t_0 \varepsilon} + 1\right) </math></blockquote>where the constant factor O(1) depends only on ''r'' and ''L''. The number of Newton steps required for the two-step initialization procedure is at most:<ref name=":0" />{{Rp|___location=Thm.4.5.1}}<blockquote><math>O(1) \cdot \sqrt{M} \cdot \ln\left(\frac{M}{1-\pi_{x^*_f}(\bar{x})} + 1\right)

+

O(1) \cdot \sqrt{M} \cdot \ln\left(\frac{M \text{Var}_G(c)}{\epsilon} + 1\right)