エンジニアを目指す浪人のブログ

情報系に役立ちそうな応用数理をゆるめにメモします

双対問題を解くことを経て主問題を解くことの概要をまとめる

数学 数理最適化

本記事は以下の過去記事の内容を用います．

ラグランジュ関数，ラグランジュ双対問題，最適性条件(KKT条件)のあらすじをまとめる - エンジニアを目指す浪人のブログ


勉強を進めていて，最適化問題において，主問題を解くために双対問題を利用できることについてモヤモヤしてしまったので，その内容をまとめておくことにしました．Boyd and Vandenberghe(2004)の5章5節(の5)をベースにしています．


本記事で用いる記号や用語は冒頭の過去記事(ラグランジュ関数)にあります．


強双対性が成り立ちラグランジュ双対問題の最適点 {\displaystyle ( \lambda^*,\nu^* ) } が存在すると仮定すると，冒頭の過去記事(ラグランジュ関数)(3.1)より，主問題の任意の(実行可能な)最適点は {\displaystyle L(x, \lambda^*,\nu^* ) } を最小にする {\displaystyle x } です．この事実は，双対問題を解くことを利用して主問題を解くことを可能にします．

より正確に，強双対性が成り立ち {\displaystyle ( \lambda^*,\nu^* ) } が既知である(すなわち双対問題は解いてある)と仮定します．{\displaystyle L(x, \lambda^*,\nu^* ) } を最小化する点がただ一つ存在する，すなわち以下の制約なし最適化問題(1.1)の最適点はただ一つであると仮定します(凸最適化問題，たとえば {\displaystyle L(x, \lambda^*,\nu^* ) } が {\displaystyle x } の狭義凸関数のときこの仮定は起こりえます)．それを {\displaystyle \bar{x} } とします．

(1.1)
{\displaystyle \mathrm{minimize} \;\;\;\; f_0(x)+\sum_{i=1}^m \lambda_i^* f_i(x) +\sum_{i=1}^p \nu_i^* h_i(x) }

このとき，主問題(過去記事(ラグランジュ関数)(0.1)にあります)が最適化問題(1.1)の最適点 {\displaystyle \bar{x} } で実行可能であるとき，{\displaystyle \bar{x} } は主問題の最適点 {\displaystyle x^* } でなければなりません; 主問題(過去記事(ラグランジュ関数)(0.1)にあります)が最適化問題(1.1)の最適点 {\displaystyle \bar{x} } で実行可能でないとき，{\displaystyle \bar{x} \neq x^* } です．


以上の観察は，双対問題を解析的に解くことが可能であったり，あるいは利用可能な特殊な構造をもつなど，双対問題を解くことが主問題を解くことより簡単な場合に興味深いものとなります．


以上，双対問題を解くことを経て主問題を解くことの概要をまとめました．



参考文献
[1] Boyd, S., and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.
[2] 京都大学 山下信雄先生のノート http://www-optima.amp.i.kyoto-u.ac.jp/~nobuo/Ryukoku/2002/course5.pdf