座標降下

座標降下法は、関数の最小値を見つけるために座標方向に沿って連続的に最小化する最適化アルゴリズムです。各反復で、アルゴリズムは座標選択規則を介して座標または座標ブロックを決定し、他のすべての座標または座標ブロックを固定したまま、対応する座標超平面上で正確または不正確に最小化します。現在の反復で座標方向に沿った直線検索を実行して、適切なステップ サイズを決定できます。座標降下法は、微分可能なコンテキストと導関数のないコンテキストの両方に適用できます。

座標降下法は、多変数関数の最小化は、一度に1つの方向に沿って最小化することによって達成できる、つまり、ループで単変量（または少なくともはるかに単純な）最適化問題を解くことによって達成できるという考えに基づいています。^[1]巡回座標降下法の最も単純なケースでは、一度に1つずつ方向を巡回的に反復し、各座標方向に関して目的関数を一度に最小化します。つまり、初期変数値から始めて、 ${\displaystyle F(\mathbf {x} )}$

${\displaystyle \mathbf {x} ^{0}=(x_{1}^{0},\ldots ,x_{n}^{0})}$、

ラウンドは、単一変数最適化問題を反復的に解くことによって 定義されます${\displaystyle k+1}$${\displaystyle \mathbf {x} ^{k+1}}$${\displaystyle \mathbf {x} ^{k}}$

${\displaystyle x_{i}^{k+1}={\underset {y\in \mathbb {R} }{\operatorname {arg\,min} }}\;f(x_{1}^{k+1},\dots ,x_{i-1}^{k+1},y,x_{i+1}^{k},\dots ,x_{n}^{k})}$^[2]

の各変数について、は1 から までです。 ${\displaystyle x_{i}}$${\displaystyle \mathbf {x} }$${\displaystyle i}$${\displaystyle n}$

したがって、 の局所的最小値の初期推定から始めて、 反復的にシーケンスを取得します。 ${\displaystyle \mathbf {x} ^{0}}$${\displaystyle F}$${\displaystyle \mathbf {x} ^{0},\mathbf {x} ^{1},\mathbf {x} ^{2},\dots }$

各反復で直線探索を行うことで、自動的に

${\displaystyle F(\mathbf {x} ^{0})\geq F(\mathbf {x} ^{1})\geq F(\mathbf {x} ^{2})\geq \dots .}$

このシーケンスは最急降下法と同様の収束特性を持つことがわかります。座標方向に沿った直線探索の 1 サイクル後に改善が見られない場合は、静止点に到達したことを意味します。

このプロセスは以下に示されます。

連続的に微分可能な関数Fの場合、座標降下アルゴリズムは次のように表される。^[1]

ステップサイズは、例えばf ( xi )= F ( x )の正確な最小値（つまり、xi_以外のすべての変数を固定したF ）を求める_方法や、従来の直線探索基準など、さまざまな方法で選択できます。^[1]

座標降下法には 2 つの問題があります。その 1 つは、目的関数が滑らかでない場合です。次の図は、関数のレベル曲線が滑らかでない場合、座標降下法の反復が非定常点で停止する可能性があることを示しています。アルゴリズムが点(-2, -2)にあると仮定します。この場合、赤い矢印で示されているように、ステップを踏むために考慮できる軸に沿った 2 つの方向があります。ただし、これら 2 つの方向に沿った各ステップは目的関数の値を増加させるため (最小化問題を想定)、両方のステップを一緒に踏むとアルゴリズムが最適値に近づくにもかかわらず、アルゴリズムはステップを踏まないことになります。この例は、座標降下法が必ずしも最適値に収束するわけではないことを示していますが、妥当な条件下では形式的な収束を示すことは可能です。^[3]

もう一つの問題は並列処理の難しさである。座標降下法の性質は方向を巡回し、各座標方向に関して目的関数を最小化することであるため、座標降下法は大規模な並列処理の明らかな候補ではない。最近の研究では、各座標方向に関する目的関数の変更を緩和することで、大規模な並列処理が座標降下法に適用できることが示されている。^{[4] [5] [6]}

座標降下法アルゴリズムは、その単純さから実務家の間で人気があるが、同じ特性のため、最適化研究者は、より興味深い（複雑な）手法を優先して、座標降下法を無視してきた。^[1]座標降下法最適化の初期の応用は、コンピュータ断層撮影の分野であった^[7] 。そこでは、座標降下法は収束が速いことがわかり^[8]、その後、臨床のマルチスライスヘリカルスキャンCT再構成に使用された。^[9]巡回座標降下法アルゴリズム（CCD）は、タンパク質構造予測に応用されている。^{[10]さらに、}機械学習における大規模な問題の出現により、座標降下法の使用に対する関心が高まっており、線形サポートベクターマシンのトレーニング^[11]（LIBLINEARを参照）や非負値行列因子分解などの問題に適用した場合、座標降下法は他の手法に匹敵することが示された。^[12]勾配の計算が不可能な問題では、おそらく、計算に必要なデータがコンピュータネットワークに分散しているために、座標降下法は魅力的である。[ ^13]

• 適応座標降下法 – 座標降下法アルゴリズムの改良
• 共役勾配 – 数学的最適化アルゴリズムリダイレクト先の簡単な説明を表示するページ
• 勾配降下法 – 最適化アルゴリズム
• 直線探索 – 最適化アルゴリズム
• 数理最適化 – 最適化問題のための数学的アルゴリズムの研究
• ニュートン法 – 関数の停留点を見つける方法
• 確率的勾配降下法 - 最適化アルゴリズム - 1つの座標ではなく、一度に1つの例を使用する

• Bezdek, JC; Hathaway, RJ; Howard, RE; Wilson, CA; Windham, MP (1987)、「座標降下のグループ化変数バージョンの局所収束分析」、Journal of Optimization Theory and Applications、vol. 54、no. 3、Kluwer Academic/Plenum Publishers、pp. 471–477、doi :10.1007/BF00940196、S2CID  120052975
• Bertsekas, Dimitri P. (1999)。非線形計画法、第 2 版、Athena Scientific、マサチューセッツ州ベルモント。ISBN 1-886529-00-0。 
• Luo, Zhiquan; Tseng, P. (1992)、「凸微分可能最小化のための座標降下法の収束について」、Journal of Optimization Theory and Applications、vol. 72、no. 1、Kluwer Academic/Plenum Publishers、pp. 7–35、doi :10.1007/BF00939948、hdl : 1721.1/3164、S2CID  121091844。
• Wu, TongTong; Lange, Kenneth (2008)、「Lasso ペナルティ回帰のための座標降下アルゴリズム」、応用統計年報、第 2 巻、第 1 号、数理統計研究所、pp. 224–244、arXiv : 0803.3876、doi :10.1214/07-AOAS147、S2CID  16350311。
• Richtarik, Peter; Takac, Martin (2011 年 4 月)、「合成関数を最小化するランダム化ブロック座標降下法の反復計算量」、Mathematical Programming、vol. 144、no. 1–2、Springer、pp. 1–38、arXiv : 1107.2848、doi :10.1007/s10107-012-0614-z、S2CID  16816638。
• Richtarik, Peter; Takac, Martin (2012 年 12 月)、「ビッグ データ最適化のための並列座標降下法」、ArXiv:1212.0873、arXiv : 1212.0873。