非線形最適化ソルバIPOPTのアウトプットの読み方

※記事内に商品プロモーションを含むことがあります。

はじめに

主双対内点法を用いた非線形最適化ソルバIPOPTのアウトプットの読み方を解説する。

主双対内点法については、以下の記事を参考のこと。
非線形計画問題の主双対内点法

Pythonの最適化モデリングツールであるCasADiを使ってIPOPTを実行したときを例に、アウトプットの読み方を示す。使用したPythonとライブラリのバージョンは以下の通り。

ライブラリ	バージョン
Python	3.8.5
CasADi	3.5.5
IPOPT	3.12.3

pipでCasADiをインストールすると、IPOPTも同時にインストールされる。

pip install casadi

実行したスクリプト

2変数の制約付き最小化問題を解く。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


import casadi
opti = casadi.Opti()
x = opti.variable(2) # 変数
opti.set_initial(x, 5)

OBJ = casadi.sum1(x**2) # 目的関数
opti.minimize(OBJ)

opti.subject_to( 2*x[0] + x[1] == 3 ) # 制約条件
opti.subject_to( x >=0 )

opti.solver('ipopt') # 最適化ソルバを設定
sol = opti.solve() # 最適化計算を実行

print(f'評価関数：{sol.value(OBJ)}')
print(f'x: {sol.value(x)}')

アウトプットの全体

スクリプトを実行すると、IPOPTのアウトプットとしては以下が表示される（CasADiのアウトプットは省略する）。
なお、IPOPTのアウトプットの詳細度合いはprint_levelというオプションで、0～12の13段階で調節できる。今回表示したのはレベル5（デフォルト）である。

******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
 Ipopt is released as open source code under the Eclipse Public License (EPL).
         For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************

This is Ipopt version 3.12.3, running with linear solver mumps.
NOTE: Other linear solvers might be more efficient (see Ipopt documentation).

Number of nonzeros in equality constraint Jacobian...:        2
Number of nonzeros in inequality constraint Jacobian.:        2
Number of nonzeros in Lagrangian Hessian.............:        2

Total number of variables............................:        2
                     variables with only lower bounds:        0
                variables with lower and upper bounds:        0
                     variables with only upper bounds:        0
Total number of equality constraints.................:        1
Total number of inequality constraints...............:        2
        inequality constraints with only lower bounds:        2
   inequality constraints with lower and upper bounds:        0
        inequality constraints with only upper bounds:        0

iter    objective    inf_pr   inf_du lg(mu)  ||d||  lg(rg) alpha_du alpha_pr  ls
   0 5.0000000e+001 1.20e+001 1.80e+000  -1.0 0.00e+000    -  0.00e+000 0.00e+000   0
   1 1.8429917e+000 0.00e+000 1.00e-006  -1.0 4.21e+000    -  1.00e+000 1.00e+000f  1
   2 1.8056300e+000 0.00e+000 3.26e-002  -1.7 1.18e-001    -  9.60e-001 1.00e+000f  1
   3 1.8000756e+000 4.44e-016 2.83e-008  -2.5 5.93e-002    -  1.00e+000 1.00e+000f  1
   4 1.8000000e+000 0.00e+000 1.50e-009  -3.8 7.60e-003    -  1.00e+000 1.00e+000f  1
   5 1.8000000e+000 0.00e+000 1.84e-011  -5.7 1.77e-004    -  1.00e+000 1.00e+000f  1
   6 1.8000000e+000 0.00e+000 2.51e-014  -8.6 9.82e-007    -  1.00e+000 1.00e+000f  1

Number of Iterations....: 6

                                   (scaled)                 (unscaled)
Objective...............:  1.8000000000000000e+000   1.8000000000000000e+000
Dual infeasibility......:  2.5059035640133008e-014   2.5059035640133008e-014
Constraint violation....:  0.0000000000000000e+000   0.0000000000000000e+000
Complementarity.........:  2.5090647396970575e-009   2.5090647396970575e-009
Overall NLP error.......:  2.5090647396970575e-009   2.5090647396970575e-009


Number of objective function evaluations             = 7
Number of objective gradient evaluations             = 7
Number of equality constraint evaluations            = 7
Number of inequality constraint evaluations          = 7
Number of equality constraint Jacobian evaluations   = 7
Number of inequality constraint Jacobian evaluations = 7
Number of Lagrangian Hessian evaluations             = 6
Total CPU secs in IPOPT (w/o function evaluations)   =      0.039
Total CPU secs in NLP function evaluations           =      0.000

EXIT: Optimal Solution Found.

アウトプットの読み方

IPOPTのアウトプットの読み方を述べる。アウトプットは以下の4つの情報に分けられる。

最適化問題の情報
最適化の反復ごとの状態
最適化の結果
終了ステータス

最適化問題の情報

最適化の計算前に、問題の変数の数などの情報が表示される。

Number of nonzeros in equality constraint Jacobian...:        2
Number of nonzeros in inequality constraint Jacobian.:        2
Number of nonzeros in Lagrangian Hessian.............:        2

これは、

等式制約のヤコビアン
不等式制約のヤコビアン
ラグランジュ関数のヘッシアン

のそれぞれ非ゼロ要素の数である。例として、計算した問題の等式制約は

$$ g(\bm{x}) = 2x_0 + x_1 - 3 = 0 $$

であるから、ヤコビアンは、

$$ \frac{\partial g}{\partial \bm{x}} = [ \begin{array}{cc} 2 & 1 \end{array} ] $$

となり、非ゼロ要素の数は2である。

Total number of variables............................:        2
                     variables with only lower bounds:        0
                variables with lower and upper bounds:        0
                     variables with only upper bounds:        0
Total number of equality constraints.................:        1
Total number of inequality constraints...............:        2
        inequality constraints with only lower bounds:        2
   inequality constraints with lower and upper bounds:        0
        inequality constraints with only upper bounds:        0

変数の数
等式制約の数
不等式制約の数

がそれぞれ表示される。

最適化の反復ごとの状態

iter    objective    inf_pr   inf_du lg(mu)  ||d||  lg(rg) alpha_du alpha_pr  ls
   0 5.0000000e+001 1.20e+001 1.80e+000  -1.0 0.00e+000    -  0.00e+000 0.00e+000   0
   1 1.8429917e+000 0.00e+000 1.00e-006  -1.0 4.21e+000    -  1.00e+000 1.00e+000f  1
   2 1.8056300e+000 0.00e+000 3.26e-002  -1.7 1.18e-001    -  9.60e-001 1.00e+000f  1
   3 1.8000756e+000 4.44e-016 2.83e-008  -2.5 5.93e-002    -  1.00e+000 1.00e+000f  1
   4 1.8000000e+000 0.00e+000 1.50e-009  -3.8 7.60e-003    -  1.00e+000 1.00e+000f  1
   5 1.8000000e+000 0.00e+000 1.84e-011  -5.7 1.77e-004    -  1.00e+000 1.00e+000f  1
   6 1.8000000e+000 0.00e+000 2.51e-014  -8.6 9.82e-007    -  1.00e+000 1.00e+000f  1

Number of Iterations....: 6

最適化の反復ごとの状態が表示される。

列	意味
iter	反復回数
objective	評価関数
inf_pr	制約違反の最大値（無限大ノルム）
inf_du	dual infeasibilityの最大値
lg(mu)	バリアパラメータ$\mu$の常用対数
\|\|d\|\|	解の更新方向$\| \Delta x \|$の最大値
lg(rg)
alpha_du	双対変数$z$のステップ幅
alpha_pr	主変数$x$のステップ幅
ls	直線探索のバックトラッキング回数

dual infeasibilityについて述べる。主双対内点法では、ラグランジュ関数
$$ L(\bm{x}, \bm{y}, \bm{z}) = f(\bm{x}) + \bm{y}^{\top} \bm{g}(\bm{x}) - \bm{z}^{\top} \bm{x} $$
を定義する。最適解において、ラグランジュ関数の$\bm{x}$に対する偏微分
$$ \nabla f(\bm{x}) + \bm{g}(\bm{x}) + \bm{y} - \bm{z} $$
は0となる。dual infeasibilityはこの偏微分の値の大きさである。

最適化の結果

                                   (scaled)                 (unscaled)
Objective...............:  1.8000000000000000e+000   1.8000000000000000e+000
Dual infeasibility......:  2.5059035640133008e-014   2.5059035640133008e-014
Constraint violation....:  0.0000000000000000e+000   0.0000000000000000e+000
Complementarity.........:  2.5090647396970575e-009   2.5090647396970575e-009
Overall NLP error.......:  2.5090647396970575e-009   2.5090647396970575e-009

最終結果が表示される。上から順に、評価関数、Dual infeasibility, 制約違反量、相補性条件である（最後のOverall NLP errorは、Dual infeasibility, Constraint violation, Complementarityの3つの最大値と思われるが詳細不明）。

Number of objective function evaluations             = 7
Number of objective gradient evaluations             = 7
Number of equality constraint evaluations            = 7
Number of inequality constraint evaluations          = 7
Number of equality constraint Jacobian evaluations   = 7
Number of inequality constraint Jacobian evaluations = 7
Number of Lagrangian Hessian evaluations             = 6
Total CPU secs in IPOPT (w/o function evaluations)   =      0.004
Total CPU secs in NLP function evaluations           =      0.000

関数などの評価回数、計算時間などが表示される。

終了ステータス

最後に終了ステータスが表示される。よく表示されるステータスは以下の通り。

EXIT: Optimal Solution Found.: 最適解が得られた。
EXIT: Solved To Acceptable Level.: 収束条件は満たさないが許容範囲 (Acceptable) である。
EXIT: Converged to a point of local infeasibility. Problem may be infeasible.: 制約条件を満たすことができない局所解に陥った。
EXIT: Maximum Number of Iterations Exceeded.: 設定された最大反復回数に達した。
EXIT: Restoration Failed!: 実行不能領域から実行可能領域に戻るのに失敗した。
EXIT: Problem has too few degrees of freedom.: 制約の数に対して変数の数が少なすぎる（自由度が少ない）。

参考

以下の論文を参考にした。