内点法

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

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

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

最小化: ${\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 })}$

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

実装

• IPOPT

参考文献

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件（英語版） 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤン楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂シンプレックス法（英語版） 十字法（英語版） レムケの主ピボット操作法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 切断) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）