Interior-point method: Difference between revisions

Revision as of 13:55, 12 December 2023

Revision as of 14:10, 12 December 2023

Line 163:

=== [[Linear program]]s ===

Consider a linear program of the form:

Given a program of the form: '''minimize ''c''^T''x'' s.t. ''Ax'' ≤ ''b''''', we can apply path-following methods with the barrier

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

\operatorname{minimize}\quad & c^\top x \\

\text{subject to}\quad

& Ax \leq b.

\end{aligned}.</math>

We can apply path-following methods with the barrier

<math display="block">b(x) := -\sum_{j=1}^m \ln(b_j - a_j^T x).</math>

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:

Given a program of the form: '''minimize d^Tx s.t. ''f_j''(''x'') := ''x''^T ''A_j x'' + ''b_j''^T''x'' + ''c_j'' ≤ 0 for all j in 1,...,''m''''', where all matrices ''A_j'' are [[Positive semidefinite matrices|positive-semidefinite program]], we can apply path-following methods with the barrier <math>b(x) := -\sum_{j=1}^m \ln(-f_j(x))</math>. It 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''²).

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

\operatorname{minimize}\quad & d^\top x \\

\text{subject to}\quad

& f_j(x) := x^\top A_j x + b_j^\top x + c_j \leq 0 \quad \text{ for all } j = 1, \dots, m,

\end{aligned}</math>

where all matrices ''A_j'' are [[Positive semidefinite matrices|positive-semidefinite program]].

We can apply path-following methods with the barrier

Consider a problem of the form '''minimize sum_''j''math |''v<subdisplay="block">j</sub>''-''u_j''^T''b(x''|^''p''''',) where:= -\sum_{j=1<''p''<∞,}^m ''u<sub>j\ln(-f_j(x)).</submath>'' areThe vectorsfunction and ''v<submath>jb</submath>'' are scalars. After converting to the standard form, we can apply path-following methods withis 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''²).

===L_p norm approximation===

Consider a problem of the form

Consider a problem of the form '''minimize sum_''j'' |''v_j''-''u_j''^T''x''|^''p''''', where 1<''p''<∞, ''u_j'' are vectors and ''v_j'' are scalars. 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''²).

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

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

\end{aligned},</math>

Givenwhere a program of the form: '''minimizeeach d<supmath>Tu_j</supmath>x is s.t.a vector, each ''f<submath>jv_j</submath>''(''x'') :=is ''x''^Ta scalar, and ''A<submath>j|\cdot|_p</submath> x''is +an ''b[[Lp norm|L_jp''^T''x'' +norm]] with ''c<submath>j1</sub>'' ≤p 0< for all j in 1,\infty...,''m''''', where all matrices ''A<sub>j</submath>'' areAfter [[Positiveconverting semidefiniteto matrices|positive-semidefinitethe program]]standard form, we can apply path-following methods with the barrier <math>b(x) := -\sum_{j=1}^m \ln(-f_j(x))</math>. It is 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

Consider a problem with objective function '''''f''₀(x)=sum''_i c_i0'' exp(''a_i''^T''x'')''', and constraints '''''f_j''(''x'')=sum''_i c_ij'' exp(''a_i''^T''x'') ≤ ''d_j'' for ''j'' in 1,...,''m''''' '''and ''i'' in 1,...,''k'''''. 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''³]).

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

\operatorname{minimize}\quad & f_0(x) := \sum_{i=1}^k c_{i0} \exp(a_i^\top x) \\

\text{subject to}\quad

& f_j(x) := \sum_{i=1}^k c_{ij} \exp(a_i^\top x) \leq d_j \quad \text{ for all } j = 1, \dots, m.

\end{aligned}</math>

Consider a problem with objective function '''''f''₀(x)=sum''_i c_i0'' exp(''a_i''^T''x'')''', and constraints '''''f_j''(''x'')=sum''_i c_ij'' exp(''a_i''^T''x'') ≤ ''d_j'' for ''j'' in 1,...,''m''''' '''and ''i'' in 1,...,''k'''''. 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 ===

Interior point methods can be used to solve semidefinite programs.<ref name=":0" />{{Rp|___location=Sec.11}}