論文読み：On the Complexity of an Inexact Restoration Method for Constrained Optimization

今回チェックした論文は、
On the Complexity of an Inexact Restoration Method for Constrained Optimization
https://epubs.siam.org/doi/abs/10.1137/18M1216146?mobileUi=0
というもの。

非線形の制約付き最適化問題
min : f(x) s.t. h(x) = 0, x \in Omega
に対する IR (Inexact Restoration) が O(epsilon_{feasible}^{-1} + epsilon_{optimality}^{-2}) の反復回数で収束する、というもの。
ここで、epsilon_{feasible} は h(x) = 0 に対する許容残差で、epsilon_{optimality}は最適値に関する許容ギャップというところ。
あと、Omega は compact である、という仮定を満たせば理論的には良くて、実用上は l<=x <= u のような上下限制約などがおもなたいしょうになるとのこと。

アルゴリズムは、||h(x)||^2 を減らす Restoration Phase と f(x) を減らす Phase があって、それぞれの Phase では、BFGS、あるいは SQP に近いような近似によって計算が行われている。ただ、２次微分は使っていないので、基本的には first-order method の範囲であり、そう考えると、上の計算量のオーダーも納得というところ。

この論文ではアルゴリズムの数値実験は行っていないのでどれくらいの速度で実際に計算できるかどうか分からないが、アルゴリズムの構成からすると最適解近くでの収束速度が良くなさそうにも思う。（もともと SIAM Journal on Optimization という雑誌に載っている結果は理論面がメインなので、実際の計算速度という意味では他の雑誌に載っているアルゴリズムの方が良いことが多いように個人的には思っている。）

この論文の拡張としては、シンプルなものとしては、制約に半正定値制約を入れて SDP も扱えるようにする、とかがあるかと思う。