鏡像降下法

鏡像降下法（きょうぞうこうかほう、）とは、数理最適化において微分可能関数の極値を求める反復法の一種。

鏡像降下法は最急降下法やを一般化したアルゴリズムである。

 歴史 
鏡像降下法は1983年に、ユーディンによって初めて提案されたArkadi Nemirovsky and David Yudin. Problem Complexity and Method Efficiency in Optimization. John Wiley & Sons, 1983。

 動機 
最急降下法において学習率の列  を微分可能関数  に適用する。関数  の極小値を求めるために初期点  から開始し、点列  を求めていく:

これを以下のように書き換える:

言い換えると、 は関数  の点  における一次式に近似の項  を追加した関数を最小化する。

この二乗ユークリッド距離はの特別な例である。別のブレグマン距離を使用すると特定の幾何上で最適化するのに適した Hedgeアルゴリズムなどのアルゴリズムを導くことができるNemirovski, Arkadi (2012) Tutorial: mirror descent algorithms for large-scale deterministic and stochastic convex optimization.https://www2.isye.gatech.edu/~nemirovs/COLT2012Tut.pdf。

 定式化 
凸集合  上で凸関数  を最適化することを考える。そして  でいくつかのノルム  が与えられているとする。

また、各ノルムには-強凸関数の微分可能凸関数  が与えられる。これは距離生成関数（distance-generating function）と呼ばれ、その勾配  は鏡像写像（mirror map）として知られている。

初期点  から始め、各反復における鏡像降下法の手続きは:

 双対空間への写像: 
 勾配ステップにおいて双対空間を更新する: 
 主空間に写像: 
 実行可能空間  に射影: 、ただし、 はである。

 拡張 
における鏡像降下法はオンライン鏡像降下法（: OMD）として知られている。

 脚注 

 関連項目 
 最急降下法



Category:最適化アルゴリズムとメソッド
Category:勾配法
Category:数学に関する記事