Interior-point method: Difference between revisions

Revision as of 19:26, 2 May 2024

Revision as of 21:54, 13 June 2024

Line 70:

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 apporimateapproximate 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: <math>t_{i+1} := \mu \cdot t_i</math>.

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}}