はじめに
最適制御や機械学習をやっていれば、主問題とラグランジュ双対問題を聞いたことがあると思います。最適化の本を調べると、本の通りに式変形をすると確かにラグランジュ双対問題を導出できるし、なぜか強双対性とかいって、主問題とラグランジュ双対問題の最適解が一致するとか言われて、頭の中が？？？と混乱したことはないでしょうか？標示関数を使って説明されても、なんかイメージが湧かない方もいらっしゃるかもしれません。とはいえ、下の記事はわかりやすく説明されているので紹介しておきます。
最適化の本や上の記事で、そっと本や記事を閉じてしまった方を対象に直観的にわかるようにゆるふわに解説します。
ラグランジュ双対問題を幾何学的に理解する。
以下の主問題を考えます。
\begin{eqnarray}
\min_x & &f(\boldsymbol{x}) \\
\mathrm{s.t.} & &g(\boldsymbol{x})\leq 0\\
& & \boldsymbol{x}\in X
\end{eqnarray}
このときのラグランジュ双対問題は、$\theta(u):=\inf_{\boldsymbol{x}\in X}\lbrace f(\boldsymbol{x})+ug(\boldsymbol{x})\rbrace$とおけば、
\begin{eqnarray}
\max_u & &\theta(u) \\
\mathrm{s.t.} & &u\geq 0\\
\end{eqnarray}
ここの式変形を幾何学的に理解していきましょう！
凸最適化問題について考えると、主問題とラグランジュ双対問題は下図の関係にあります。$(x_0,y_0)$は主問題の最適解を表します。凸最適化問題では、主問題とラグランジュ双対問題の最適解は一致する(強双対性)ことがわかります。ラグランジュ双対問題を考えるとき、傾き$u\geq0$の条件をつけないといけないことに注意します。
図の見方について説明します。
Step1で何をしているかというと、$\theta(u):=\inf_{\boldsymbol{x}\in X}\lbrace f(\boldsymbol{x})+ug(\boldsymbol{x})\rbrace$を考えています。集合$G$の点と交わるように、傾き$u$を固定して切片$\alpha^\prime$を最小化しているんですね。切片$\alpha^\prime$は、$\theta(u)$に相当しています。ただし$u$は$u\geq0$の範囲であらゆる値をとる変数であることに注意です。
Step2で何をしているかというと、ラグランジュ双対問題を考えています。集合$G$の点と交わるように、傾き$u$について切片$\alpha$を最大化しているんですね。Step1の条件を満足する必要があるのでStep2では支持平面のみ考えればよいです。切片$\alpha$は、ラグランジュ双対問題の目的関数に相当します。この直線$y+u_0x=\alpha_0$と集合$G$の交わる点が、最適解$(x_0,y_0)$となります。つまり、主問題とラグランジュ双対問題の最適解は一致することがわかります。
$u<0$の場合どうなるの？という疑問は出てくると思います。$u<0$の場合について考えると、主問題とラグランジュ双対問題の解が一致しないことが分かります。さらに、ラグランジュ双対問題の解は、$g(\boldsymbol{x})\leq0$を満たしていないことが分かります。これは困りました。やはり$u\geq0$という条件は必要なようです。
ラグランジュ双対問題の導出
標示関数を用いてラグランジュ双対問題を導出する際、$u<0$の場合を式変形の中で除外できるようにラグランジュ関数$L(\boldsymbol{x},u)$を設計する必要があります。試しに、こんな定義はどうでしょう？
L(\boldsymbol{x},u)=
\left\{
\begin{array}
af(\boldsymbol{x})+ug(\boldsymbol{x}) & u\geq0\\
-\infty & u<0
\end{array}
\right.
あとは、機械的にラグランジュ双対問題を求めるだけです。$\theta(u) = \inf_{\boldsymbol{x}\in X}L(\boldsymbol{x},u)$とおけば、ラグランジュ双対問題は下式です。
\max_u \theta(u) \\
制約式がないように見えますが、$u<0$のとき、$\theta(u)=-\infty$となるため、$u\geq0$という制約条件を含んでいることが分かります。
\begin{eqnarray}
\max_u & &\theta(u) \\
\mathrm{s.t.} & &u\geq 0\\
\end{eqnarray}
機械的に主問題からラグランジュ双対問題を導出できました。めでたしめでたし。
おわりに
本記事では厳密な議論を避け直観的に説明しました。本当はよくないことです。この記事でラグランジュ双対問題について直観的に分かった方は、ぜひ参考文献を購入することを検討してみてください！
以下は、線形計画を通してラグランジュ双対問題を理解しようという記事です。
KKT条件については下記の記事を参照ください。
ラグランジュ双対問題とKKT条件が理解出来たら、Pythonで線形計画を実装してみましょう。
参考文献
- 凸解析と最適化理論、田中謙輔、牧野書店
- 非線形最適化の基礎、福島雅夫、朝倉書店
- Convex Optimization、Stephen Boyd、Lieven Vandenberghe、CAMBRIDGE UNIVERSITY PRRESS