内点法

内点法（ないてんほう、英: interior point method, internal point method）とは、連続最適化問題のアルゴリズムであり、カーマーカー法に触発されて生まれた多くの手法の総称である^[1]。実行可能領域の内部を経由して、最適解に収束するのが特徴である。また、大規模問題に対しては計算効率が良い点や非線型問題にも対応できる点で、シンプレックス法よりも優れているといえる。内点法は、点列を生成する方法によって、アフィン変換法、ポテンシャル減少法、解析的中心追跡法、パス追跡法などに分類される^[2]。また、扱う問題によっては、与えられた問題を直接扱う方法（主内点法、英: primal interior point method）、その双対問題を扱う方法（双対内点法、英: dual interior point method）、主問題と双対問題を同時に解く方法（主双対内点法、英: primal-dual interior point method）に分けられる^[3]。

主双対内点法による非線型最適化

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

最小化:

f(x)

条件:

c(x)\geq 0,x\in \mathbb {R} ^{n},c(x)\in \mathbb {R} ^{m}~~~~(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

{\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}}

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

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

\lambda \geq 0

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

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

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

分類

線形計画法

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

凸二次計画問題・線形相補性問題

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

実装

IPOPT

脚注

[脚注の使い方]

注釈

^ 近傍は $N_{2}(\beta )=\{(x,y,z)\in F^{0}:||Xz-\mu e||_{2}\leq \beta \mu ,\mu ={\frac {x^{T}z}{n}}\}\quad \mathrm {for} \,\beta \in [0,1]$ である。
^ 近傍は $N_{ln}(\beta )=\{(x,y,z)\in F^{0}:n\mathrm {ln} \mu -\sum _{i=1}^{n}\mathrm {ln} (x_{i}z_{i})\leq \beta ,\mu ={\frac {x^{T}z}{n}}\}\quad \mathrm {for} \,\beta \geq 0$ である。

出典

^ 小島政和『Introduction to Mathematical Programming from the Viewpoint of Interior-Point Methods』（レポート）東京工業大学、1998年9月、1頁。2025年2月22日閲覧。
^ 小島 2001, pp. 7–14.
^ 小島 2001, p. 55.
^ ^a ^b 小島 2001, p. 72.
^ 小島 2001, p. 65.
^ “terative solution of problems of linear and quadratic programming”. Doklady Akademii Nauk SSSR (Soviet Mathematics Doklady) 8: 674-675. (1967).
^ 小島 2001, pp. 72–80.
^ 小島 2001, pp. 8–9.
^ 小島 2001, p. 84.
^ Karmarkar, N. (1984). “A new polynomial-time algorithm for linear programming” (PDF). Proceedings of the sixteenth annual ACM symposium on Theory of computing – STOC '84. p. 302. doi:10.1145/800057.808695. ISBN 0-89791-133-4. 2013年12月28日時点のオリジナル (PDF)よりアーカイブ.
^ 小島 2001, pp. 65–67, 84–100.
^ E.R.Barnes (1986). “A variation on Karmarkar’s algorithm for solving linear programming problems”. Mathematical Programming (Mathematical Optimization Society) 36: 174-182.
^ ^a ^b 小島 2001, pp. 10–11.
^ R.J.Vanderbei; M.S.Meketon; B.A.Freedman (1986). “modification of Karmarkar’s linear programming algorithm,”. Algorithmica (Springer Science+Business Media) 1: 395-407.
^ ^a ^b ^c 小島 2001, p. 131.
^ 小島政和; 水野眞治; 吉瀬章子『多項式オーダーの主双対内点法』（レポート） 5巻、統計数理研究所共同研究レポート、1987年、13-24頁。
^ 小島 2001, pp. 127–133.
^ 田辺國士『Complementarity-enforcing centered Newton method for mathematical programming』（レポート） 5巻、統計数理研究所共同研究レポート、1987年、118-143頁。
^ J.Renegar (1988). “A polynomial-time algorithm, based on Newton’s method, for linear programming”. Mathematical Programming (Mathematical Optimization Society) 40: 59-93. doi:10.1007/BF01580724.
^ 小島 2001, pp. 68–69.
^ ^a ^b 小島 2001, p. 141.
^ Mehrotra, S. (1992). “On the implementation of a primal–dual interior point method”. SIAM Journal on Optimization (SIAM PUBLICATIONS) 2 (4): 575–601. doi:10.1137/0802028.
^ 小島 2001, pp. 141–145.
^ M.Kojima; S.Mizuno; A.Yoshise (1989). “A polynomial-time algorithm for a class of linear complementarity problem”. Matheamtical Programming 44: 1-26.
^ ^a ^b 小島 2001, pp. 162–163.
^ M.Kojima; S.Mizuno; A.Yoshise (1991). “An O(√n) iteration potential reduction algorithm for linear complementarity problems”. Matheamtical Programming 50: 331-342.

参考文献

福島雅夫『数理計画入門』朝倉書店、1996年。ISBN 978-4254280043。
福島雅夫『非線形最適化の基礎』朝倉書店、2001年。ISBN 978-4254280012。
小島政和、土谷隆、水野眞治、矢部博『内点法』朝倉書店〈経営科学のニューフロンティア 9〉、2001年。ISBN 978-4254275193。

[15] 近傍は $N_{2}(\beta )=\{(x,y,z)\in F^{0}:||Xz-\mu e||_{2}\leq \beta \mu ,\mu ={\frac {x^{T}z}{n}}\}\quad \mathrm {for} \,\beta \in [0,1]$ である。

[19] 近傍は $N_{ln}(\beta )=\{(x,y,z)\in F^{0}:n\mathrm {ln} \mu -\sum _{i=1}^{n}\mathrm {ln} (x_{i}z_{i})\leq \beta ,\mu ={\frac {x^{T}z}{n}}\}\quad \mathrm {for} \,\beta \geq 0$ である。

[1] 小島政和『Introduction to Mathematical Programming from the Viewpoint of Interior-Point Methods』（レポート）東京工業大学、1998年9月、1頁。2025年2月22日閲覧。

[FOOTNOTE小島20017–14-2] 小島 2001, pp. 7–14.

[FOOTNOTE小島200155-3] 小島 2001, p. 55.

[FOOTNOTE小島200172-4] 小島 2001, p. 72.

[FOOTNOTE小島200165-5] 小島 2001, p. 65.

[6] “terative solution of problems of linear and quadratic programming”. Doklady Akademii Nauk SSSR (Soviet Mathematics Doklady) 8: 674-675. (1967).

[FOOTNOTE小島200172–80-7] 小島 2001, pp. 72–80.

[FOOTNOTE小島20018–9-8] 小島 2001, pp. 8–9.

[FOOTNOTE小島200184-9] 小島 2001, p. 84.

[10] Karmarkar, N. (1984). “A new polynomial-time algorithm for linear programming” (PDF). Proceedings of the sixteenth annual ACM symposium on Theory of computing – STOC '84. p. 302. doi:10.1145/800057.808695. ISBN 0-89791-133-4. 2013年12月28日時点のオリジナル (PDF)よりアーカイブ.

[FOOTNOTE小島200165–67,_84–100-11] 小島 2001, pp. 65–67, 84–100.

[12] E.R.Barnes (1986). “A variation on Karmarkar’s algorithm for solving linear programming problems”. Mathematical Programming (Mathematical Optimization Society) 36: 174-182.

[FOOTNOTE小島200110–11-13] 小島 2001, pp. 10–11.

[14] R.J.Vanderbei; M.S.Meketon; B.A.Freedman (1986). “modification of Karmarkar’s linear programming algorithm,”. Algorithmica (Springer Science+Business Media) 1: 395-407.

[FOOTNOTE小島2001131-16] 小島 2001, p. 131.

[17] 小島政和; 水野眞治; 吉瀬章子『多項式オーダーの主双対内点法』（レポート） 5巻、統計数理研究所共同研究レポート、1987年、13-24頁。

[FOOTNOTE小島2001127–133-18] 小島 2001, pp. 127–133.

[20] 田辺國士『Complementarity-enforcing centered Newton method for mathematical programming』（レポート） 5巻、統計数理研究所共同研究レポート、1987年、118-143頁。

[21] J.Renegar (1988). “A polynomial-time algorithm, based on Newton’s method, for linear programming”. Mathematical Programming (Mathematical Optimization Society) 40: 59-93. doi:10.1007/BF01580724.

[FOOTNOTE小島200168–69-22] 小島 2001, pp. 68–69.

[FOOTNOTE小島2001141-23] 小島 2001, p. 141.

[24] Mehrotra, S. (1992). “On the implementation of a primal–dual interior point method”. SIAM Journal on Optimization (SIAM PUBLICATIONS) 2 (4): 575–601. doi:10.1137/0802028.

[FOOTNOTE小島2001141–145-25] 小島 2001, pp. 141–145.

[26] M.Kojima; S.Mizuno; A.Yoshise (1989). “A polynomial-time algorithm for a class of linear complementarity problem”. Matheamtical Programming 44: 1-26.

[FOOTNOTE小島2001162–163-27] 小島 2001, pp. 162–163.

[28] M.Kojima; S.Mizuno; A.Yoshise (1991). “An O(√n) iteration potential reduction algorithm for linear complementarity problems”. Matheamtical Programming 50: 331-342.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[注釈 1]

[15]

[16]

[17]

[注釈 2]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]