Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 64:
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<sub>t</sub>(x) := ''c''<sup>T</sup>''x +'' b(''x'')''', We define the path of minimizers by: '''x*(t) := arg min f<sub>t</sub>(x)'''. We apporimate this path along an increasing sequence ''t<sub>i</sub>'', which 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/\sqrt{M}\right)t_i</math>.</blockquote>For each ''t<sub>i</sub>'', we find an approximate minimum of ''f<sub>ti</sub>'', denoted by ''x<sub>i</sub>''. 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<sub>i</sub>''<sub>+1</sub>, we start with ''x<sub>i</sub>'' 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<sub>i</sub>''<sub>+1</sub>.<ref name=":0" />{{
=== Convergence rate ===
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{X}{t_0} \left[1 + \frac{r}{\sqrt{M}}\right]^{-i} </math>, where <math>X = M+\frac{L}{1-L}\sqrt{M} </math></blockquote>{{Under construction|placedby=Erel Segal}}
==Primal-dual methods==
| |||