DNN上でのSDP緩和問題

非負かつ半正定値(DNN : doubly non‐negative)制約を持つ SDP 緩和問題の最適解を求めると最適解との gap が非常に小さいことが数値実験によってわかってきた。ただし非負制約を全ての変数に対して入れていくとスラック変数の数が膨大になって非常に大きな SDP になってしまう。非負かつ半正定値の錐に対して self‐concordant barrier functionを作成できることがわかっているのだが、高速にニュートン方程式の解を見付けて安定した主双対内点法の作れるかどうかは未知数である。
とにかく現行の内点法アルゴリズムでも SDPARA などを用いてクラスタ計算機で解いていけば結構大きな SDP でも解くことができる。添付の図は問題の説明を省略してあるのでわかりにくいのだが、Cutting-plane algorithm による最適解の上限 \bar{f} と DNN 制約を持つ SDP 緩和問題による \lambda の値の差が小さく、この SDP 緩和問題の性能が良いことがわかる。