論文読み：A Limiting Analysis on Regularization of Singular SDP and its Implication to Infeasible Interior-point Algorithms

A Limiting Analysis on Regularization of Singular SDP and its Implication to Infeasible Interior-point Algorithms

http://www.optimization-online.org/DB_HTML/2019/12/7528.html

SDPの場合には、主問題と双対問題の両方に内点実行可能解があれば（つまり、Slater の条件が満たされれば）、主問題と双対問題の最適値が一致する、という双対理論は良く知られている。

この論文で扱っているのは、内点実行可能解がない場合（weakly infeasible とかなっている場合）にどうするか、という話で、結論を先に書くと「主問題と双対問題の最適値の間が得られる」ということだった。

個人的に今後の展開として面白そうかな、と考えられるのは、以下の２点といったところ。
１．homogenous self-dual の定式化を行ったときに、「主問題と双対問題の最適値の間のどこにくるか」を、より正確に扱うことが出来るかどうか。（例えば kappa と theta のあたりを解析すると面白いかもしれない。）
２．SDP緩和をすると目的関数値が -\inftyになってしまうような問題（SDP緩和が非常に弱い例）にどういう値が得られるか（元問題との差がどれくらいになるか）。