5.3 計算誤差について

計算機は有限桁の数しか取り扱えないため，計算誤差が生じる． 特に条件数が大きな大規模行列の取り扱いは難しくなる． 内点法を実行する場合，反復点が最適解に近づくにつれて， 主問題(1)の反復点 $\mbox{\boldmath$X$}$と 双対問題(2)の反復点 $\mbox{\boldmath$Z$}$は悪条件となることが知られている． さらに，それらから構成されるSchur方程式の係数行列 $\mbox{\boldmath$B$}$も悪条件となる． このとき，計算誤差の影響により，内点法が途中で破綻することがある．

一例として，ある問題を解いたときの，内点法の反復回数と誤差 の関係を表2に挙げた． 表中には，各反復での行列変数 $\mbox{\boldmath$Z$}$の最大固有値と最小固有値，並びに $\mbox{\boldmath$Z$}^{-1}$の誤差を掲載している． なお， $\mbox{\boldmath$Z$}^{-1}$はLAPACKのルーチンを用いて計算し， その誤差として行列 $\mbox{\boldmath$Z$}^{-1} \mbox{\boldmath$Z$}- \mbox{\boldmath$I$}$の絶対値が最大の要素を取った．

表 2: 逆行列の誤差

内点法の反復回数	$\mbox{\boldmath$Z$}$の最大固有値	$\mbox{\boldmath$Z$}$の最小固有値	$\mbox{\boldmath$Z$}^{-1}$の誤差
0	1.00e+01	1.00e+01	0.00e+00
4	3.58e+00	1.60e-02	4.88e-15
8	3.99e+00	7.46e-05	1.82e-12
12	5.40e+00	2.41e-07	7.57e-10
16	6.75e+00	4.96e-10	4.20e-07
20	6.90e+00	3.74e-11	7.15e-06
24	6.91e+00	1.93e-12	1.11e-04

特に， 実行可能内点解が無いSDP問題を解く場合， 計算誤差の影響を受けやすいという傾向がある． 実行可能内点解が存在する問題だけを解く対象としたいものの， 現実に解きたいSDP問題はそうではないことも多い． 例えば，SDPの標準ベンチマーク集である SDPLIB 1.2 [4]にある92個の問題のうち， 45個の問題には主問題か双対問題のどちらかに実行可能内点解が存在しない． 計算誤差の問題を解決する方法は，現在模索中である．