内点法

主双対内点法のアイディアは単純で、制約付き非線型最適化問題にも応用が可能である。ここでは単純のために制約式が全て不等式で与えられる非線型最適化問題について考える。

最小化: ${\displaystyle f(x)}$

条件: ${\displaystyle c(x)\geq 0,x\in \mathbb {R} ^{n},c(x)\in \mathbb {R} ^{m}~~~~(1)}$

この最適化問題の対数バリア関数は次のようになる。

${\displaystyle B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\ln(c_{i}(x))~~~~(2)}$

ここで${\displaystyle \mu }$は正のスカラーで、時に「バリア・パラメータ」とも呼ばれる。この${\displaystyle \mu }$が0に収束していくと、${\displaystyle B(x,\mu )}$が最適解に収束していく。

前述のバリア関数の勾配は

${\displaystyle g_{b}=g-\mu \sum _{i=1}^{m}{\frac {1}{c_{i}(x)}}\nabla c_{i}(x)~~~~(3)}$

となる。ただし、${\displaystyle g}$は元の関数${\displaystyle f(x)}$の勾配であり、${\displaystyle \nabla c_{i}}$は${\displaystyle c_{i}}$の勾配を表す。

主値${\displaystyle x}$に加えて、双対値${\displaystyle \lambda \in \mathbb {R} ^{m}}$をラグランジュ乗数として導入する。

${\displaystyle \forall i=1,\ldots ,m,c_{i}(x)\lambda _{i}=\mu ~~~~(4)}$

この条件は時に摂動相補性条件とも呼ばれる。式(4)を式(3)に適用することにより以下を得る。

${\displaystyle g-A^{T}\lambda =0~~~~(5)}$

ただし、行列${\displaystyle A}$は制約${\displaystyle c(x)}$のヤコビ行列である。

式(5)が表しているのは関数${\displaystyle f(x)}$の勾配が制約式の勾配により張られる部分空間の中に存在するということである。このとき小さな${\displaystyle \mu }$による摂動相補性条件は、最適解が${\displaystyle c_{i}(x)=0}$の境界付近に存在するか、もしくは制約${\displaystyle c_{i}(x)}$の勾配${\displaystyle g}$がほとんど0であるということを表している。

式(4)および式(5)に対してニュートン法を用いて${\displaystyle (x,\lambda )}$を更新していくことを考えると、その更新幅${\displaystyle (p_{x},p_{\lambda })}$は次の線型方程式の解として与えられる。

${\displaystyle {\begin{pmatrix}W&-A^{T}\\\Lambda A&C\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}-g+A^{T}\lambda \\\mu 1-C\lambda \end{pmatrix}}}$

ただし行列${\displaystyle W}$は関数${\displaystyle B(x,\mu )}$のヘッセ行列であり、対角行列${\displaystyle \Lambda }$は${\displaystyle \lambda }$を対角成分に持つ。また、${\displaystyle C}$は${\displaystyle C_{ii}=c_{i}(x)}$なる対角行列である。

式(1), (4), および${\displaystyle \mu >0}$から

${\displaystyle \lambda \geq 0}$

がそれぞれのステップに課される。この条件を保つために、適切なステップ更新幅${\displaystyle \alpha }$を選び、

${\displaystyle (x,\lambda )\rightarrow (x+\alpha p_{x},\lambda +\alpha p_{\lambda })}$

とすることで、最適解に向かって収束していく。

Summarize Timeline Fact Check

発表年	名称	考案者	計算量	補足	出典
1967年	アフィン変換法	I.I.ディキン		線形計画問題に対する内点法として始めて提案された解法である[4]。1988年に米国において再発見された[5][4]。	[6][7]
1984年	カーマーカーの射影変換法 （カーマーカー法）	ナレンドラ・カーマーカー	反復回数: ${\displaystyle O(nL)}$ 総計算量: ${\displaystyle O(n^{4}L)}$	内点法として初めて多項式オーダーで動作することが証明された解法である[8]。カーマーカー法が提案されたことによって、内点法が盛んに研究されるようになった[9]。	[10][11]
1986年	アフィン変換法	バーンズ			[12][13]
1986年	アフィン変換法	Vanderbei、Meketon、Freedman			[14][13]
1987年	パス追跡法 （主双対内点法）	小島政和、水野眞治、吉瀬章子		主双対内点法の一種。ステップ幅の決定に近傍${\displaystyle N_{2}(\beta )}$[注釈 1] を使用する[15]。	[16][17]
1987年	パス追跡法 （主双対内点法）	田辺國士		主双対内点法の一種。ステップ幅の決定に近傍${\displaystyle N_{ln}(\beta )}$[注釈 2] を使用する[15]。	[18][15]
1988年	リネガーの解析的中心追跡法	J.リネガー	反復回数: ${\displaystyle O({\sqrt {n}}L)}$		[19][20]
1992年	メロートラの予測子・修正子法	サンジェイ・メロートラ		非常に効率よく解くことのできる解法として知られている内点法[21]。非実行可能型の主双対内点法に分類される[21]。	[22][23]

発表年	名称	考案者	計算量	補足	出典
1989年	パス追跡法	小島政和、水野眞治、吉瀬章子	反復回数: ${\displaystyle O({\sqrt {n}}L)}$	実行可能型内点法。	[24][25]
1991年	ポテンシャル減少法	小島政和、水野眞治、吉瀬章子	反復回数: ${\displaystyle O({\sqrt {n}}L)}$	実行可能型内点法。	[26][25]