Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 66:
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" />{{Rp|___location=Sec.4}}
=== Convergence
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>The number of Newton steps required to go from ''x<sub>i</sub>'' to ''x<sub>i</sub>''<sub>+1</sub> is at most a fixed number, that depends only on ''r'' and ''L''.{{Under construction|placedby=Erel Segal}}
==Primal-dual methods==
| |||