ウルフの二重性

数学的最適化において、フィリップ・ウルフにちなんで名付けられたウルフ双対性は、目的関数と制約がすべて微分可能な関数である双対問題の一種です。この概念を使用すると、弱い双対性原理により、最小化問題の下限を見つけることができます。^[1]

不等式制約を伴う最小化問題の場合、

${\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {最小化} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\end{aligned}}}$

ラグランジアン双対問題は

${\displaystyle {\begin{aligned}&{\underset {u}{\operatorname {最大化} }}&&\inf _{x}\left(f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\right)\\&\operatorname {subject\;to} &&u_{i}\geq 0,\quad i=1,\dots ,m\end{aligned}}}$

ここで目的関数はラグランジュ双対関数である。関数とが凸で連続微分可能であると仮定すると、最小値は勾配がゼロに等しいところで発生する。問題は ${\displaystyle f}$${\displaystyle g_{1},\ldots ,g_{m}}$

${\displaystyle {\begin{aligned}&{\underset {x,u}{\operatorname {maximize} }}&&f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\\&\operatorname {subject\;to} &&\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)=0\\&&&u_{i}\geq 0,\quad i=1,\dots ,m\end{aligned}}}$

はウルフ双対問題と呼ばれる。^[2] この問題はKKT条件を制約条件として採用している。また、等式制約は一般に非線形であるため、ウルフ双対問題は非凸最適化問題である可能性がある。いずれにしても、弱い双対性が成立する。^[3]${\displaystyle \nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)}$

• ラグランジアン双対性
• フェンチェルの二重性