論文読み：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 の適用はあまり多くないので、こういったところから他の手法を組み合わせていろいろと発展させられるかもしれない。

論文読み：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 も扱えるようにする、とかがあるかと思う。

Termux の Emacs の起動を速くする

Termux での Emacs を起動すると 7 秒程度かかるので、これを少しだけ速くする。

基本的には言語のロードを外す。
具体的には
cd /data/data/com.termux/files/usr/share/emacs/26.3/lisp
cp loadup.el loadup.el.original
として、
emacs loadup.el
で

(load "language/chinese")

(load "language/cyrillic")
...

などとなっている各言語で自分が使わないところは行頭にセミコロンをつけてコメントアウトする。

これによって、だいたい5秒ぐらいまで短縮された。

本当は他のパッケージも外したいところだが、なぜか上手くいかず、変なメッセージが出て Emacs がクラッシュしてしまう。

論文読み：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緩和が非常に弱い例）にどういう値が得られるか（元問題との差がどれくらいになるか）。