多倍長計算と SDP

SDP の計算をしていて途中で止まってしまう（つまり計算が継続出来なくなる）のは、以下の二つの場合が多い。
１: 極めて小さいサイズのステップ長しか取れなくなる。つまり探索方向は計算できるのだが、その方向にわずかにでも進むと実行可能領域の境界にぶつかってしまう。
２: コレスキー分解に失敗する。つまり行列が半正定値ではなく、対角成分の値が低めである。
SDP に元々実行可能解が無いあるいは有界ではない場合には最適解が存在しないので、どれだけ頑張っても最適解は得られない。今まで解いても精度が上がらない問題はまさにこういった”解けない”問題の類かと思っていたが、多倍長計算などの適用によって”解けない”のではなく”解きにくい”問題だということがわかってきた。つまり本来”解けない”問題ならば多倍長計算しても解けないのであるが、多くの問題で優れた解（今までは考えらないレベル）を得ることに成功している。
以下はグラフ分割問題に対する SDP 緩和問題を SDPA(倍精度)とSDPA-GMP(任意精度)で解いたものである。この問題はある制約式によっておそらく退化現象が起きていると考えられていて、Duality gap の小さい解は存在しないものとみなされていたが、多倍長計算の結果はこの予想を覆すものになっている。

relative gap 　主問題と双対問題の相対 gap
objValPrimal(Dual) 主問題(双対問題）の目的関数値
p.(d.)feas.error 主問題(双対問題)の実行可能性

SDPA 6.2
phase.value = pFEAS
Iteration = 23
mu = 9.9850360320008491e-06
relative gap = 4.3502496540397718e-05 <---
gap = 1.2381444679681053e-03
digits = 4.3614858188475063e+00
objValPrimal = -7.3430648223721393e+00 <---
objValDual = -7.3433842709725763e+00 <---
p.feas.error = 1.4589832814104753e-11 <---
d.feas.error = 3.0451851520518769e-04 <---
total time = 1.120

SDPA-GMP
phase.value = pdOPT
Iteration = 96
mu = 2.2516542601099410e-22
relative gap = 9.2157503527747540e-21 <---
gap = 2.7920512825363268e-20
digits = 2.0035469298447865e+01
objValPrimal = -7.3430762652465377e+00 <---
objValDual = -7.3430762652465377e+00 <---
p.feas.error = 4.1495434498941082e-57 <---
d.feas.error = 3.7954060927013347e-35 <---
relative eps = 3.7092061506874214e-68
total time = 1437.830

ただし上記の２の場合には対角成分が同行の他の成分よりも大きくなるような補正が必要であり、多倍長計算だけでは対応できない。