論文読み：An inexact first-order method for constrained nonlinear optimization

今回チェックした論文は、
An inexact first-order method for constrained nonlinear optimization
https://www.tandfonline.com/doi/abs/10.1080/10556788.2020.1712601?journalCode=goms20

一般（非凸も含むけど関数は連続微分可能）の制約付き最適化問題について、first-order method で解く、というもの。
アルゴリズムの特徴としては、
1. 制約はペナルティ項として目的関数に組み込んで、それを最小化する。等式制約c(x)=0については絶対値 |c(x)| を用いて、不等式制約 c(x) <= 0 については max{c(x), 0} を用いる。
2. ペナルティ項付き目的関数を1次までのTaylor展開をして（つまり線形近似をして）、それを最小化することで探索方向を決める。さらに探索方向に沿って Armijo のルールを適用してステップ長を決める。
3. ペナルティのウェイトは、双対問題の情報を使って更新する。
4. 子問題を解いたりするときには信頼領域法も併用する。

計算量については、得たい精度が epsilon の場合には O(1/(epsilon^2)) ということで、first-order method ではよく見かえる計算量なわけだけど、面白いと思うのは非線形の制約がついても計算量としては決して悪くない、ということ。

つまり、epsilon だけで計算量を評価する場合には、制約なし最適化問題と制約あり最適化問題は計算量が同じになるということである。

個人的には、今回の論文のアルゴリズムは複雑すぎる印象がある。例えば、Armijo のルールと信頼領域法を併用しているのは、どちらか一方でいいようにも感じる。

その一方で、一般の制約付き最適化問題への first-order method の適用はあまり多くないので、こういったところから他の手法を組み合わせていろいろと発展させられるかもしれない。