制約条件付きの凸最適化を解析的に解く方法としてよく用いられる方法。
大まかには、以下の手続きで問題の制約を緩和して解く。
(1) 微分可能な凸関数f ( x ) f(\boldsymbol{x}) f ( x )
(2) ラグランジュ未定乗数 という未知の値λ ≥ 0 \lambda\geq0 λ ≥ 0 ラグランジュ関数 （ラグランジアン ）
L ( x , λ ) = f ( x ) + λ ( g ( x ) − 0 ) = f ( x ) + λ g ( x ) L(\boldsymbol{x}, \lambda) = f(\boldsymbol{x}) + \lambda (g(\boldsymbol{x}) - 0)=f(\boldsymbol{x}) + \lambda g(\boldsymbol{x}) L ( x , λ ) = f ( x ) + λ ( g ( x ) − 0 ) = f ( x ) + λ g ( x ) を作る。
(3) ラグランジュ双対問題
max λ L ( x , λ ) subject to λ ≥ 0 \begin{align}\max_\lambda \hspace{1em} & L(\boldsymbol{x}, \lambda)\\\text{subject to} \hspace{1em} & \lambda \geq 0\end{align} λ max subject to L ( x , λ ) λ ≥ 0 を解いていく。L ( x , λ ) L(\boldsymbol{x}, \lambda) L ( x , λ ) x \boldsymbol{x} x
0 = ∂ L ∂ x = ∂ f ∂ x + λ ∂ g ∂ x \boldsymbol{0} = \frac{\partial L}{\partial \boldsymbol{x}} = \frac{\partial f}{\partial \boldsymbol{x}}+ \lambda \frac{\partial g}{\partial \boldsymbol{x}} 0 = ∂ x ∂ L = ∂ x ∂ f + λ ∂ x ∂ g これを解いて最適解λ ∗ , x ∗ \lambda^*, \boldsymbol{x}^* λ ∗ , x ∗ x ∗ \boldsymbol{x}^* x ∗
ラグランジュ緩和 ¶ 以下のような最適化問題があるとする
minimize f ( x ) subject to g i ( x ) = b i ( i = 1 , . . . , k ) h j ( x ) ≥ b j ( j = 1 , . . . , l ) \begin{align}
\text{minimize } \hspace{1em}
& f(\boldsymbol{x})\\
\text{subject to } \hspace{1em}
& g_i(\boldsymbol{x}) = b_i \hspace{1em} (i=1,...,k)\\
& h_j(\boldsymbol{x}) \geq b_j \hspace{1em} (j=1,...,l)
\end{align} minimize subject to f ( x ) g i ( x ) = b i ( i = 1 , ... , k ) h j ( x ) ≥ b j ( j = 1 , ... , l ) この問題の制約を緩和して、もう少し簡単な問題にするアプローチの一つがラグランジュ緩和である。
例えば等式制約g i ( x ) = b i g_i(\boldsymbol{x}) = b_i g i ( x ) = b i β i \beta_i β i
ラグランジュ双対問題 ¶ 微分可能な凸関数f i ( x ) , ( i = 0 , . . . , m ) f_i(x), (i=0,...,m) f i ( x ) , ( i = 0 , ... , m )
min x f 0 ( x ) subject to f i ( x ) ≤ a i ( i = 1 , . . . , m ) \begin{align}\min_x \hspace{1em} & f_0(x)\\\text{subject to} \hspace{1em} & f_i(x) \leq a_i \hspace{1em} (i=1, ..., m)\end{align} x min subject to f 0 ( x ) f i ( x ) ≤ a i ( i = 1 , ... , m ) のラグランジュ双対問題とは、ラグランジュ未定乗数λ i \lambda_i λ i
L ( x , λ ) = f 0 ( x ) + ∑ i = 1 m λ i ( f i ( x ) − a i ) L(x, \lambda) = f_0(x) + \sum^{m}_{i=1} \lambda_i (f_i(x) - a_i) L ( x , λ ) = f 0 ( x ) + i = 1 ∑ m λ i ( f i ( x ) − a i ) を用いて、以下のように定義される。
max λ inf x L ( x , λ ) subject to λ ≥ 0 \begin{align}\max_{\lambda} \inf_{x} \hspace{1em} & L(x, \lambda)\\\text{subject to}\hspace{1em} & \lambda \geq 0\end{align} λ max x inf subject to L ( x , λ ) λ ≥ 0