双対上昇法の実装

anmitsu

2022年2月12日 12:55

私は不定期で学部時代のレポート課題で作成したプログラムを再編集してGithubで公開している。本記事ではそのうちの双対上昇法に関する課題で作成したプログラムを再編集したものについて、少しだけコメントを書き連ねていきたいと思う。

正直に言うと、双対上昇法の実装の件について、書きたいことはないが、最近、noteでもTeX記法が使用できるようになったということで、とりあえず記事を作成することにした。

今回考える問題

今回は$${f(x,y) = x^2+2y^2}$$という関数の$${x+y=1}$$という条件下での最小値を求めることを考える。この問題は高校数学の２次関数の知識を使うだけで簡単に解くことができる。

$${y=1-x}$$と変形して代入するだけで、$${x}$$だけの関数になる。あとは、以下のように平方完成させれば最小値が2/3であることがわかる。

$$
x^2 + 2(1-x)^2 = 3x^2 - 4x + 2 = 3\left( x-\frac{2}{3} \right)^2 + \frac{2}{3}
$$

ラグランジュの未定乗数法

制約付きの最適化問題を解くに活躍するのがラグランジュの未定乗数法である。詳しい理論の話は適当な最適化手法の本やWeb資料などを参照してもらいたい。ここでラグランジュ関数$${\mathcal{L}(x,y,\lambda)}$$を次のように定義する。

$$
\mathcal{L}(x,y,\lambda) = x^2 + 2y^2 +\lambda (x+y-1)
$$

これを$${x, y, \lambda}$$それぞれについて微分して0となる点が関数$${f(x,y)}$$の最適解の候補となる。あくまで候補であることに注意する必要がある。

双対問題

元の最適化問題と等価な問題（双対問題）を考えることで、問題が解きやすくなることがある。

上記の$${\mathcal{L}(x,y,\lambda)}$$について、$${\lambda}$$に関して最大化することを考える。$${x+y-1=0}$$が満たされていれば、$${\lambda}$$を含む項は消えて、$${f(x,y) = x^2 + 2y^2}$$が残る。しかし、$${x+y-1\neq 0}$$の場合は$${\lambda}$$を$${+\infty}$$または$${-\infty}$$とすることで$${\mathcal{L}(x,y,\lambda)}$$を$${+\infty}$$とすることができる。

このことを最大値の候補の中で最小のものが$${f(x,y)}$$であり、そのようになるのが、元の最適化問題の制約条件を満足している場合に限るとみなすと、元の最適化問題の解は

$$
\min_{x,y\in \mathbb{R}} \left\{ \max_{\lambda \in \mathbb{R}} \mathcal{L}(x,y,\lambda) \right\}
$$

と一致する。そして、適当な条件の下では（少なくとも、今回考えている最適化問題ではこの条件を満足している）、上記のmin-max（ミニマックス）問題と次のmax-min問題が等価である強双対性が成立する。

$$
\max_{\lambda \in \mathbb{R}} \left\{ \min_{x,y\in \mathbb{R}} \mathcal{L}(x,y,\lambda) \right\}
$$

この強双対性をもとに、問題を書きかえることが可能である。$${\mathcal{L}(x,y,\lambda)}$$は$${x,y}$$について２次関数であり、$${x, y}$$の積の項を一切含んでいないため、$${x, y}$$に関する最小化は簡単にできる。最小となる際の$${x, y}$$は$${\lambda}$$を用いて、$${(x,y) = (-\lambda/2, -\lambda/4)}$$と書ける。$${\mathcal{L}(x,y,\lambda)}$$の式にこの値を代入すると、$${\lambda}$$だけで表される$${\min \mathcal{L}(x,y,\lambda)}$$が得られる。

$$
\phi(\lambda) := \min_{x,y\in \mathbb{R}} \mathcal{L}(x,y,\lambda) = -\frac{3}{8} \lambda^2 - \lambda
$$

$${x, y}$$$は$${\lambda}$$の式で表されるため、$${\phi(\lambda)}$$の最適化を行うことで$${\lambda}$$が最適値に近づき、対応する$${x, y}$$も最適値に近づく。こうすることで元の最適化問題を解くことが可能である。