ja IPOPT

IPOPT
作者	Andreas Wächter, Carl Laird
初版	2005年8月26日 (19年前)
最新版	3.12.12 / 2018年11月18日 (6年前)
プログラミング; 言語	C++
対応OS	UNIX, Linux, macOS, Windows
ライセンス	Eclipse Public License
公式サイト	projects.coin-or.org/Ipopt
	テンプレートを表示

IPOPT（Interior Point OPTimizer、I-P-Opt と発音される）は、主双対内点法を利用した大規模（高次元）な連続最適化問題を解くライブラリである。C++で実装され、公開されているソースコードはEPLライセンスのもとで利用できる。

対象となる最適化問題

目的関数が以下の物で、

f:\mathbb {R} ^{n}\to \mathbb {R}

制約条件が以下の形式で与えられる物で、

g^{L}\leq g(x)\leq g^{U}

x^{L}\leq x\leq x^{U}

下記の最適化問題を解く^[2]。

\min _{x\in \mathbb {R} ^{n}}f(x)

f と g は微分可能でなければならない。大規模問題としては $f(x)=\sum _{i=1}^{n}x_{i}^{2}$ であれば、n = 100万でも実行できる。

アルゴリズム

IPOPT で実装されている最適化手法は、内点法の一種である主双対内点法に、フレッチャーとレイファーのフィルター法による直線探索^[3]を組み入れたものであり、最適化対象の関数の一階偏導関数（ヤコビ行列）および二階偏導関数（ヘッセ行列）が与えられた場合はそれを利用する。ただしAMPLなどの計算環境から呼び出された場合には自動微分を行う。ヤコビ行列やヘッセ行列は疎行列を使うことにより高速化している^[4]。ヘッセ行列が与えられない場合は準ニュートン法 (L-BFGS法) でその近似値で代用することもできる^[5]。

API

ライブラリで実装されているAPIは、C++、C言語、Fortran、Javaなどのプログラミング言語や、MATLAB、R言語などの数値計算ソフトウェアから呼び出すことができる。非公式に、.NET Framework、Python、Scilab、Juliaのインターフェイスも作られている^[6]。

開発

開発は COIN-OR (COmputational INfrastructure for Operations Research) プロジェクト^[7]の一部として、オープンソースで行われている。

アンドレアス・ウェチター (Andreas Wächter) がカーネギーメロン大学のローレンツ・ビーグラー (Lorenz T. Biegler) 研究室の博士課程の学生だったときに始められ、その後、彼とカール・レアード (Carl Laird) がC++版を実装した。この二人は2011年にジェームズ・H・ウィルキンソン賞を受賞している。