内点法のソースを表示

'''内点法'''（ないてんほう、{{lang-en-short|interior point method, internal point method}}）とは、連続[[最適化問題]]の[[アルゴリズム]]であり、[[カーマーカー法]]に触発されて生まれた多くの手法の総称である<ref>{{Cite report |和書 |author=小島政和 |date=1998-09 |title=Introduction to Mathematical Programming from the Viewpoint of Interior-Point Methods |url=http://www.opt.c.titech.ac.jp/kojima/articles/b-349.pdf |publisher=[[東京工業大学]] |page=1 |access-date=2025-02-22 }}</ref>。[[実行可能領域]]の内部を経由して、最適解に収束するのが特徴である。また、大規模問題に対しては計算効率が良い点や非線型問題にも対応できる点で、[[シンプレックス法]]よりも優れているといえる。内点法は、点列を生成する方法によって、[[アフィン変換法]]、[[ポテンシャル減少法]]、解析的中心追跡法、[[パス追跡法]]などに分類される{{Sfn|小島|2001|pp=7-14}}。また、扱う問題によっては、与えられた問題を直接扱う方法（'''主内点法'''、{{lang-en-short|primal interior point method}}）、その双対問題を扱う方法（'''双対内点法'''、{{lang-en-short|dual interior point method}}）、主問題と双対問題を同時に解く方法（'''主双対内点法'''、{{lang-en-short|primal-dual interior point method}}）に分けられる{{Sfn|小島|2001|p=55}}。

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

:'''最小化:''' <math>f(x)</math> 
:'''条件:''' <math> c(x) \geq 0,  x \in \mathbb{R}^n, c(x) \in \mathbb{R}^m~~~~(1)</math>

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

:<math>B(x,\mu) = f(x) - \mu \sum_{i=1}^m \ln(c_i(x))~~~~(2)</math>

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

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

:<math>g_b = g - \mu \sum_{i=1}^m \frac{1}{c_i (x)} \nabla c_i (x)~~~~(3)</math>

となる。ただし、<math>g</math>は元の関数<math>f(x)</math>の勾配であり、<math>\nabla c_i</math>は<math>c_i</math>の勾配を表す。

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

:<math>\forall i=1, \ldots, m, c_i(x) \lambda_i = \mu~~~~(4)</math>

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

:<math>g - A^T \lambda = 0 ~~~~ (5) </math>

ただし、行列<math>A</math>は制約<math>c(x)</math>の[[ヤコビ行列]]である。

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

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

:<math> \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}</math>

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

式(1), (4), および<math>\mu > 0</math>から

:<math> \lambda \geq 0 </math>

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

:<math>(x, \lambda) \rightarrow (x + \alpha p_x, \lambda + \alpha p_\lambda)</math>

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

== 分類 ==
=== 線形計画法 ===
{| class="wikitable"
! 発表年
! 名称
! 考案者
! 計算量
! 補足
! 出典
|-
| 1967年
| [[アフィン変換法]]
| I.I.Dikin
| 
| 線形計画問題に対する内点法として始めて提案された解法である{{Sfn|小島|2001|p=72}}。1988年に米国において再発見された{{Sfn|小島|2001|p=65}}{{Sfn|小島|2001|p=72}}。
| <ref>{{Cite journal |author= |title=terative solution of problems of linear and quadratic programming |year=1967 |journal=Doklady Akademii Nauk SSSR |publisher=Soviet Mathematics Doklady |volume=8 |pages=674-675 }}</ref>{{Sfn|小島|2001|pp=72-80}}
|-
| 1984年
| [[カーマーカーの射影変換法]]<br />（カーマーカー法）
| [[ナレンドラ・カーマーカー]]
| 反復回数: <math>O(nL)</math>
総計算量: <math>O(n^4L)</math>
| 内点法として初めて多項式オーダーで動作することが証明された解法である{{Sfn|小島|2001|pp=8-9}}。カーマーカー法が提案されたことによって、内点法が盛んに研究されるようになった{{Sfn|小島|2001|p=84}}。
|<ref>{{cite conference |last1=Karmarkar |first1=N. |year=1984 |title=Proceedings of the sixteenth annual ACM symposium on Theory of computing – STOC '84 |pages=302 |doi=10.1145/800057.808695 |isbn=0-89791-133-4 |archive-url=https://web.archive.org/web/20131228145520/http://retis.sssup.it/~bini/teaching/optim2010/karmarkar.pdf |archive-date=28 December 2013 |doi-access=free |chapter-url=http://retis.sssup.it/~bini/teaching/optim2010/karmarkar.pdf |chapter=A new polynomial-time algorithm for linear programming |url-status=dead }}</ref>{{Sfn|小島|2001|pp=65-67,84-100}}
|-
| 1986年
| [[アフィン変換法]]
| バーンズ
| 
|
| <ref>{{Cite journal |author=E.R.Barnes |title=A variation on Karmarkar’s algorithm for solving linear programming problems |year=1986 |journal=Mathematical Programming |publisher=Mathematical Optimization Society |volume=36 |pages=174-182 }}</ref>{{Sfn|小島|2001|pp=10-11}}
|-
| 1986年
| [[アフィン変換法]]
| Vanderbei、Meketon、Freedman
| 
|
| <ref>{{Cite journal |author1=R.J.Vanderbei |author2=M.S.Meketon |author3=B.A.Freedman |title= modification of Karmarkar’s linear programming algorithm, |year=1986 |journal=Algorithmica |publisher=Springer Science+Business Media |volume=1 |pages=395-407 }}</ref>{{Sfn|小島|2001|pp=10-11}}
|-
| 1987年
| パス追跡法<br />（主双対内点法）
| 小島政和、水野眞治、吉瀬章子
| 
| 主双対内点法の一種。ステップ幅の決定に近傍<math>N_{2}(\beta)</math>{{Efn|近傍は <math>N_{2}(\beta)= \{(x,y,z) \in F^{0}: ||Xz - \mu e||_{2} \le \beta \mu, \mu = \frac{x^{T}z}{n} \} \quad \mathrm{for} \, \beta \in [0,1]</math> である。}} を使用する{{Sfn|小島|2001|p=131}}。
| <ref>{{Cite report |和書 |author1=小島政和 |author2=水野眞治 |author3=吉瀬章子 |title=多項式オーダーの主双対内点法 |publisher=統計数理研究所共同研究レポート |volume=5 |year=1987 |pages=13-24 }}</ref>{{Sfn|小島|2001|pp=127-133}}
|-
| 1987年
| パス追跡法<br />（主双対内点法）
| 田辺國士
| 
| 主双対内点法の一種。ステップ幅の決定に近傍<math>N_{ln}(\beta)</math>{{Efn|近傍は <math>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 \ge 0</math> である。}} を使用する{{Sfn|小島|2001|p=131}}。
| <ref>{{Cite report |和書 |author=田辺國士 |title=Complementarity-enforcing centered Newton method for mathematical
programming |publisher=統計数理研究所共同研究レポート |volume=5 |year=1987 |pages=118-143 }}</ref>{{Sfn|小島|2001|p=131}}
|-
| 1988年
| リネガーの解析的中心追跡法
| J.リネガー
| 反復回数: <math>O(\sqrt{n}L)</math>
|
|<ref>{{cite journal |author=J.Renegar |title=A polynomial-time algorithm, based on Newton’s method, for linear
programming |journal=Mathematical Programming |publisher=Mathematical Optimization Society |volume=40 |year=1988 |pages=59-93 |doi=10.1007/BF01580724 }}</ref>{{Sfn|小島|2001|pp=68-69}}
|-
| 1992年
| [[メロートラの予測子・修正子法]]
| サンジェイ・メロートラ
|
| 非常に効率よく解くことのできる解法として知られている内点法{{Sfn|小島|2001|p=141}}。非実行可能型の主双対内点法に分類される{{Sfn|小島|2001|p=141}}。
| <ref>{{cite journal |last=Mehrotra |first=S. |title=On the implementation of a primal–dual interior point method |journal=SIAM Journal on Optimization |publisher=SIAM PUBLICATIONS  |volume=2 |year=1992 |issue=4 |pages=575–601 |doi=10.1137/0802028 }}</ref>{{Sfn|小島|2001|pp=141-145}}
|-
|}

=== 凸二次計画問題・線形相補性問題 ===
{| class="wikitable"
! 発表年
! 名称
! 考案者
! 計算量
! 補足
! 出典
|-
| 1989年
| パス追跡法
| 小島政和、水野眞治、吉瀬章子
| 反復回数: <math>O(\sqrt{n}L)</math>
| 実行可能型内点法。
| <ref>{{Cite journal |author1=M.Kojima |author2=S.Mizuno |author3=A.Yoshise |title=A polynomial-time algorithm for a class of linear complementarity problem |journal=Matheamtical Programming |volume=44 |year=1989 |pages=1-26 }}</ref>{{Sfn|小島|2001|pp=162-163}}
|-
| 1991年
| ポテンシャル減少法
| 小島政和、水野眞治、吉瀬章子
| 反復回数: <math>O(\sqrt{n}L)</math>
| 実行可能型内点法。
| <ref>{{Cite journal |author1=M.Kojima |author2=S.Mizuno |author3=A.Yoshise |title=An O(√n) iteration potential reduction algorithm for linear complementarity problems |journal=Matheamtical Programming |volume=50 |year=1991 |pages=331-342 }}</ref>{{Sfn|小島|2001|pp=162-163}}
|-
|}

== 実装 ==
* [[IPOPT]]

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
{{Reflist|2}}

==参考文献==
{{Refbegin}}
*{{Cite book |和書 |author=福島雅夫 |title=数理計画入門 |publisher=朝倉書店 |year=1996 |ISBN=978-4254280043 |ref=harv }}
*{{Cite book |和書 |author=福島雅夫 |title=非線形最適化の基礎 |publisher=朝倉書店 |year=2001 |ISBN=978-4254280012 |ref=harv }}
*{{Cite book |和書 |author1=小島政和 |author2=土谷隆 |author3=水野眞治 |author4=矢部博 |title=内点法 |series=経営科学のニューフロンティア 9 |publisher=朝倉書店 |year=2001 |ISBN=978-4254275193 |ref={{Sfnref|小島|2001}} }}
{{Refend}}

{{最適化アルゴリズム}}

{{デフォルトソート:ないてんほう}}
[[Category:最適化アルゴリズム]]
[[Category:オペレーションズリサーチ]]
[[Category:数学に関する記事]]