はじめに

本記事は機械工学専攻な凸最適化初心者が，近接勾配法を用いた凸最適化について勉強したので，アウトプットしようとしたサムシングです．

なお，その後に博士課程進学し，所属は数理学系になってしまいました．

例にももれず，数学が苦手＆数理最適化初学者というステータスを持っています．
クリティカルな間違いがありましたら，コメントか ~~Twitter~~ X: @santana_hammerまで教えていただけると嬉しいです．

それでは，やっていきましょうか．

必要知識

凸最適化周りの基礎知識について身についていることが前提です．
以下に僕が作った資料のURLを置いていますので，参考までに．

凸最適化からDC最適化まで - Trigger-FK

（そのうち，凸最適化の基礎についてざっと知れる記事も書く予定です．）

近接作用素

近接勾配法のキーアイテムである近接作用素(proximal operator)について述べていきます．

定義

プロパーな閉凸関数$f: \mathbb{R}^n \to \mathbb{R} \cup \{ \infty \}$と実数$\gamma>0$に対して，近接作用素は以下のように定義される．

\text{prox}_{\gamma f}(v) \triangleq \underset{x \in \text{dom}(f)}{\text{arg min}} \left\{ f(x) + \frac{1}{2 \gamma}\|x-v\|_2^2 \right\}

こいつがとても重要です，これを知ったらこの記事を読む価値はなくなったと言っても過言ではありません．
本日はここまでです，お疲れさまでした．

ていうのは冗談で．
近接作用素は射影作用素と最小化問題を組み合わせたものであり，$\gamma$の値によってどちらを重視するか重み付けすることが可能です．

わかりやすいものとして，参考文献1のSection 4.2に記載されている例を取り上げます．
まず，試しに$\gamma \to \infty$として定義式の右辺第二項を消去します．

\text{prox}_{\infty f}(v) = \underset{x \in \text{dom}(f)}{\text{arg min}} \ f(x)

上記の式は，単純に関数$f$を最小化する$x$を求める最小化問題になります．
これは想像に難くないと思います．

次に，$\gamma \to 0$とし，右辺第一項を消去します．

\text{prox}_{0 f}(v) = \underset{x \in \text{dom}(f)}{\text{arg min}} \ \|x-v\|_2^2

これは，$v$とのユークリッド距離を最小とするような，集合$\text{dom}(f)$の要素への射影を表しています．
関数$f$が成す領域から点$v$がはみ出していた場合，その領域内で現在点から一番近い点にどんどん移動させる役割を担っています．

最速ではないけど下手に遠回りせず，それなりに速いルートをたどってゴールに進んでいくイメージです．

とてもかしこそうですね．かしこかしこ．

近接勾配法とは

本題の近接勾配法に入ります．

これ以降，以下の形で表現される最適化問題を考えます．

\underset{x \in \mathbb{R}^{n}}{\text{minimize}} \ \left\{ g(x) + h(x) \right\}

$g(x)$は$\text{dom}(g)=\mathbb{R}^{n}$を満たす微分可能な凸関数，関数$h$はプロパーな閉凸関数であるとします，微分不可能な関数でも設定可能です．

この最適化問題に対して，近接勾配法のアルゴリズムは以下の形で与えられます．

\begin{align}
x_{k+1} 
&= \text{prox}_{\gamma h}\left(x_{k} - \gamma \nabla g(x_{k})\right)\\
&= \text{argmin}_{x} \left(h(x) + g(x_{k}) + \nabla g(x_{k})^{\top}(x-x_{k}) + \frac{1}{2\gamma}\|x-x_{k}\|^2_2\right)
\end{align}

$\gamma$はアルゴリズムのステップサイズとなり，$\nabla g(x)$は関数$g$の$x$における勾配を表します．
もし関数$g$が$L$-平滑（$L$-リプシッツ連続）な関数であれば，$\gamma=L$（$L$はリプシッツ定数）とすることで収束が保証されます．

L-平滑関数

$g$が$L$-平滑関数であるとは，

g(y) \leq g(x) + \nabla g(x)^{\top}(y-x) + \frac{L}{2}\|y-x\|^2

が任意の$x, y$で成立すること．これは，$g$の勾配$\nabla g$に対して

\|\nabla g(y)-\nabla g(x)\| \leq L\|y-x\|

が任意の$x, y$で成立することと等価である．

補足

「$\gamma$に対してリプシッツ定数を設定すれば収束が保証される」と書きました．
しかし，リプシッツ定数が陽に求められるケースは非常に限られており，ほとんどの場合は導出することが困難です．
その場合，人力パラメータチューニング（制御工学でいう限界感度法？）を行ってシミュレーションを行なう必要があったりします．
また，段階的にパラメータ変更を行うバックトラッキング法を使うことで，探索しながら問題を解くことが可能です．

あと，近接購買法についてもっと知りたい方は，以下のサイトがおすすめです．
近接勾配法とproximal operator - 甲斐性なしのブログ

アルゴリズム

現在，近接勾配法では様々なアルゴリズムが提案されています．
その中でも，高速なアルゴリズムとして有名なFISTAについて軽く紹介します．

FISTA (Fast Iterative Shrinkage-Thresholding Algorithm)

近接勾配アルゴリズムをベースとした反復縮小しきい値アルゴリズム(ISTA: Iterative Shrinkage-Thresholding Algorithm)に対して，Nesterovの加速勾配法を導入したアルゴリズムです（Fast ISTAと言ったり）．

以下にpseudocodeを示します．

なお，$F(x)=g(x)+h(x)$とします．

どれくらい高速化されるのかについて，収束レートを以下に示します．
まずはISTAについて．

F(x_{k}) - F(x^*) \leq \frac{L\|x_{0} - x^*\|^2}{2k}

そしてFISTA．

F(x_{k}) - F(x^*) \leq \frac{2L\|x_{0} - x^*\|^2}{k^2}

ここで，$x^*$は最適解を表します．

ISTAでは誤差が$O(1/k)$のオーダで収束しますがFISTAでは$O(1/k^2)$で収束し，かなり高速化されることがわかります．
なお，これ以上の高速化は理論的には不可能であることが言われています．

終わりに

本記事の内容は，スパースモデリングと非常に関係性の高い内容になっています．
（あれ，前の記事でもなんかスパースモデリングに関係する話をしてなかったっけ）

もっと体系的にやってみたいorもっと知りたい方は，上述したブログが参考になるかと思います．
また，北九州市立大学で開講していたスパースモデリングの講義動画もありますので，ぜひご覧ください．

スパースモデリング 3-(1) 凸最適化の基礎
 スパースモデリング 3-(2) 近接作用素
 スパースモデリング 3-(3) 近接分離法
 スパースモデリング 3-(4) 近接勾配法
 スパースモデリング 3-(5) 一般化LASSOとADMM

凸最適化最高！！凸最適化しか勝たん！！

参考文献

M. Nagahara, "Sparsity Methods for Systems and Control," Boston-Delft: now publishers, 2020.
A. Beck and M. Teboulle, "A fast Iterative Shrinkage-Thresholding Algorithm with application to wavelet-based image deblurring," 2009 IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 693-696, 2009.