凸最適化
{\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&&&h_{j}(x)=0,\quad j=1,\dots ,p.\end{aligned}}}
等式制約 h ( x ) = 0 {\displaystyle h(x)=0} は2つの 不等式制約 h ( x ) ≤ 0 {\displaystyle h(x)\leq 0} と − h ( x ) ≤ 0 {\displaystyle -h(x)\leq 0} を用いて置き換えることができる。 そのため等式制約は理論的には冗長であるが実際上の利点のため使用される。 これらのことから、なぜ h j ( x ) = 0 {\displaystyle h_{j}(x)=0} が単に凸であるのではなくアフィンであるのかが容易に理解できる。 h j ( x ) {\displaystyle h_{j}(x)} を凸とすると h j ( x ) ≤ 0 {\displaystyle h_{j}(x)\leq 0} は凸であるが − h j ( x ) ≤ 0 {\displaystyle -h_{j}(x)\leq 0} は凹となる。 そのため h j ( x ) = 0 {\displaystyle h_{j}(x)=0} が凸となるための条件が h j ( x ) {\displaystyle h_{j}(x)} がアフィンであることである。
標準形に表された凸最小化問題を考える。 コスト関数を f ( x ) {\displaystyle f(x)} 、 不等式制約を g i ( x ) ≤ 0 ( i = 1 ... m ) {\displaystyle g_{i}(x)\leq 0(i=1\ldots m)} とすると、定義域 X {\displaystyle {\mathcal {X}}} は
X = { x ∈ X | g 1 ( x ) ≤ 0 , ... , g m ( x ) ≤ 0 } . {\displaystyle {\mathcal {X}}=\left\lbrace {x\in X\vert g_{1}(x)\leq 0,\ldots ,g_{m}(x)\leq 0}\right\rbrace .}
この問題に対するラグランジュ関数は
L(x,λ0,...,λm) = λ0f(x) + λ1g1(x) + ... + λmgm(x).
X上の関数fを最小化するX上の点xに関して 実数値のラグランジュ係数λ0, ..., λmが存在し、 以下を満たす。
X上のすべての変数に関してxはL(y, λ0, λ1, ..., λm) を最小化する
λ0 ≥ 0, λ1 ≥ 0, ..., λm ≥ 0, 少なくともひとつは λk>0,
λ1g1(x) = 0, ..., λmgm(x) = 0 (相補スラック性).