書籍「機械学習のための連続最適化」を読んでいる途中ですが、自分用にまとめます。１、3、9、10章は個人的に目新しさがなかったので省略。随時追記予定。

2019/2/10: 2章を加筆、11、12章を追記しました。

2章：基礎事項

リプシッツ連続

関数 $f$ がリプシッツ連続であるとは、

$|f(\boldsymbol{x}) - f(\boldsymbol{y}) | \leq L || \boldsymbol{x}- \boldsymbol{y}||$

が成り立つこと。

一階微分の絶対値が有限とみなすと覚えやすい。

γ平滑

勾配 $\nabla f$ がリプシッツ連続性

$|\nabla f(\boldsymbol{x}) - \nabla f(\boldsymbol{y}) | \leq \gamma || \boldsymbol{x}- \boldsymbol{y}||$

を満たすとき、 $f$ を $\gamma$ -平滑関数という。

二階微分が有限。

アフィン包

集合 $S$ を包むような超平面で次元が最小になるもの

例えば、集合 $S$ が二次元でも $y=x$ のように一次元的に点が並んでいれば、その直線がアフィン包になる。

相対的内点

集合 $S$ の相対的内点は $\text{ri}(S)$ などと書かれる。内点と比較して考えるとわかりやすい。

内点：ε近傍（中心が $x$ で半径εの円）がSに含まれるようなε近傍が存在するとき、点 $x \in S$ を内点という。

相対的内点：アフィン包とε近傍との共通集合が、Sに含まれるようなε近傍が存在するとき、点 $x \in S$ を相対的内点という。

相対的内点ではアフィン包との共通集合をとっているために、相対的内点ではあるが内点ではない点というのが存在する。例えば、 $S \in \mathbb{R}^ 3$ だが、 $z=0$ の制限が有り、点が $xy$ 平面に拘束される場合を考える。この場合、 $z$ 方向に $z=0$ から少し（たとえεでも）ずれると、そこは $S$ に属さないため、内点は存在しない。だが、アフィン包（この場合は $xy$ 平面）とε近傍との共通集合である相対的内点は存在する。

以下の記事は例が豊富でとてもわかりやすい。 seetheworld1992.hatenablog.com

相対的内部の扱いどころは、Wikipedia大先生が詳しい。

相対的内部は（中略）高次元空間内の低次元集合を扱う際にしばしば有用となる

相対的内部 - Wikipedia

エピグラフ

関数 $f$ のエピグラフは以下のように定義される、「ある関数の上側の領域」。

$\text{epi}(f) = \{(x,t) \in \mathbb{R}^n \times \mathbb{R} | f(x)\leq t\}$

凸関数 $f$ のエピグラフが空集合でないとき、 $f$ を真凸関数という。真凸関数であることは、 $f(x)\neq + \infty$ となる $x$ が存在することと同値。

By Eli Osherovich - 投稿者自身による作品, CC 表示-継承 3.0, Link

上図はエピグラフ (数学) - Wikipedia)より引用。

エピグラフが閉集合の時、 $f$ を閉凸関数という。閉凸関数であることは、凸関数 $f$ が下半連続であることと同値。

下半連続

下半連続の概念は、Wikipediaの説明と図が理解しやすい。

半連続性（英: semi-continuity）とは、拡張実数値関数（値として[tex] \pm \infty]を取り得る）に対して定義される「連続性」よりも弱い性質である。

By Mktyscn - 投稿者自身による作品, パブリック・ドメイン, Link

上図は、 $x_0$ で下半連続である関数を示している。半連続 - Wikipediaより引用。

$f$ が $x_0$ で下半連続であることは、数式では次のように書ける。

$f(x_0) \leq \liminf_{x\to x_0} f(x)$

定義域の全ての点で下半連続となる関数を、下半連続関数という。

共役関数

真凸関数 $f$ に対して次式で定義される関数のこと。

$f^*(y) = \sup \{y^T x - f(x)| x \in \mathbb{R}^n\}$

$f(x)$ の接平面の情報を保持している。双対上昇法で出てくる。

劣微分

勾配の概念を拡張したもの。微分可能とは限らない凸関数にも微分を定義できる。凸関数が微分可能なら劣微分はその勾配に一致するが、そうでない場合は、劣微分は一般に集合となる。

4章：勾配法の基礎

直線探索

1変数関数 $\phi(\alpha) = f(\boldsymbol{x}+\alpha \boldsymbol{d})$ の最小値を見つけるための計算法を直線探索法という。

関数値が十分に減少したかを判定するための条件がいくつか提案されている。

アルミホ条件
ウルフ条件
強ウルフ条件
ゴールドシュタイン条件

アルミホ条件を用いて直線探索を行う方法の一つが、バックトラッキング法。

ゾーテンダイク条件

この条件が成り立つ関数を最小化する場合、最適化アルゴリズムが設定する降下方向と、目的関数の勾配方向が直交しなければ（ $\liminf_{k\to \infty} (\cos\theta_k)^2 > 0$ ならば）、初期解 $\boldsymbol{x}_0$ に依存せずに、目的関数の勾配がゼロベクトルに収束（大域的収束）する。

したがって、最適化アルゴリズムの収束性を議論する際には以下の条件を示すことが多い。

$\liminf_{k\to \infty} (\cos\theta_k)^2 > 0$

座標降下法

目的関数を、各座標軸に沿って最適化していく手法。

最急降下法

関数を一次近似したときに、関数値が最も減少する方向である $-\nabla f(\boldsymbol{x})$ の方向を探索する。

5章：ニュートン法

ニュートン法

おなじみニュートン法。関数を二次近似したときに、関数値が最も減少する方向 $\boldsymbol{d}_k$ を探索する。

$\boldsymbol{d}_k = - \nabla^2 f(\boldsymbol{x})^{-1} \nabla f(\boldsymbol{x})$

ただし、ヘッセ行列 $\nabla^2 f(\boldsymbol{x})$ が正定値でない場合、関数が減少しない。

修正ニュートン法

ヘッセ行列を修正し、確実に目的関数を減少できるようにした方法。

$\boldsymbol{d}_k = - (\nabla^2 f(\boldsymbol{x}) + \mu \boldsymbol{I})^{-1} \nabla f(\boldsymbol{x})$

$\nabla^2 f(\boldsymbol{x})$ の最小固有値が $\lambda_1$ のとき、 $\mu$ を $\max(0,-\lambda_1)$ より大きくとれば、正定値性が保証される。

ガウス ニュートン法

目的関数が次のように二乗の形で表されるときに使える。目的関数を一次近似したときの線形最小二乗解の方向へ探索する。 Introduction to Applied Linear Algebraの説明の方がわかりやすい。

$f(\boldsymbol{x}) = \frac{1}{2} \Sigma^{m}_{i=1} (l_i(\boldsymbol{x}))^2$

waregawa-log.hatenablog.com

レーベンバーグ・マーカート法

ガウスニュートン法とレーベンバーグ・マーカート法の関係は、ニュートン法に対する修正ニュートン法の関係と同じで、正定値性を保証する修正を加えたもの。 Introduction to Applied Linear Algebraでは、別の解釈が紹介されている。すなわち、ガウスニュートン法で解く線形最小二乗問題の目的関数に、 $\boldsymbol{x}_{k+1}$ と $\boldsymbol{x}_{k}$ の距離を小さくするという評価項を加えたものだと説明されている。

自然勾配法

距離構造が、ユークリッド距離でなくヘリンジャー距離で表される場合に用いる最適化手法。機械学習屋さんは使うんですかね。。

6章：共役勾配法

目的関数が楕円のような形状をしている場合、最急降下法では効率的に最適化できない。共役勾配法では、座標変換により楕円を真円に補正することで、この課題を解決している。

7章：準ニュートン法

ニュートン法の実行にはヘッセ行列を計算する必要があり、計算コストがかかる。これを回避するために考えられた、ヘッセ行列を低計算量で模擬する方法が準ニュートン法である。近似ヘッセ行列（正確にはその逆行列）は、漸化式の形で毎ステップ計算できる。

BFGS法、DFP法

目的関数の勾配： $\nabla f(\boldsymbol{x}_k)$ を $\boldsymbol{x}_{k+1}$ まわりで1次近似した式を、近似ヘッセ行列が満たすべき拘束条件として扱う。 →セカント条件：式(7.2)

セカント条件を満たす正定値行列のなかで、今の近似行列に最も「近い」ものを次ステップの近似行列とする。

定式化：式(7.6)
本書では、主にKLダイバージェンスを使って「近さ」を定式化する
距離の公理を満たす基準を用いた場合→7.2.3節

距離基準としてKLダイバージェンスを採用した場合の解 $\boldsymbol{B}$ ：BFGS公式、DFP公式：式(7.3), (7.4)

ダイバージェンスをとる順番で、得られる公式がBFGSかDFPか決まる：式(7.8), (7.9)
図示：図(7.1)
BFGSとDFPは相補的な関係： $\boldsymbol{B}$ をBFGSで更新したとき、 $\boldsymbol{H}=\boldsymbol{B}^{-1}$ はDFPで更新されている。したがって、 $\boldsymbol{B}$ を計算した後にその逆行列 $\boldsymbol{H}$ を求める、といった回り道はせず、直に欲しい値： $\boldsymbol{H}$ を公式で計算すればよい
行列の更新則は、座標変換に関して共変的（座標変換してから更新しても、その逆順でも、得られる $\boldsymbol{x}_{k+1}$ は同じ）

L-BFGS法

BFGS： $O(n^2)$ の計算量に加え、 $n\times n$ 行列を記憶できるだけのメモリ容量が必要だが、 $n$ が大きくなったとき、これらは現実的でない。そこで計算量、必要なメモリ量がともに $O(mn)$ なL-BFGS法が提案されている。 $2m$ が記憶しておくべきベクトルの本数。次元 $n$ が数千の問題に対しては、 $m=10$ 程度で良好な結果が得られるとのこと。

8章：信頼領域法

信頼領域法ではまず、目的関数をモデル関数 $m_k(\boldsymbol{p})$ （通常、二次関数）で近似する。次に、この近似が妥当な範囲 $||\boldsymbol{p}|| \leq \Delta_k$ （信頼領域）内でモデル関数を最適化する。すなわち、次の2次関数の制約付き最適化問題を逐次解いていく形になる。

$\min_{\boldsymbol{p}\in \mathbb{R}^n} m_k (\boldsymbol{p}) \quad \text{s.t.} \quad ||\boldsymbol{p}|| \leq \Delta_k$

信頼領域 $\Delta_k$ は繰り返し計算中で一定ではなく、モデル関数が目的関数をよく近似できるようであれば大きくし、そうでないようであれば小さくする。

11章：主問題に対する最適化法

有効制約法

まず、有効制約式について説明する。有効制約式とは、不等式制約( $g_i(x)\leq 0$ )ありの最適化問題の実行可能解 $x$ に対して、 $g_i(x) = 0$ を満たす制約式の集合 $I(x)$ をいう。実行可能解 $x$ で等式 $g_i(x) = 0$ が成り立っていない制約は $x$ の近傍では考慮する必要がないため、このような区別は有用である。

それでは、有効制約法の実行手順について説明する。テキストの図11.1を見ると理解が進む。なお、制約は線形不等式制約を仮定する。

有効制約 $I(x)$ を一定に保ったまま（有効な制約の直線上を滑らせ）、目的関数がこれ以上小さくならない点まで解を更新する。
有効制約のうちの幾つかを外し、 $g_i(x) \lt 0$ の方向へ解を更新することで目的関数を小さくすることができるのであれば、そのように解を更新する。無理ならそこで終了。
手順2で更新する場合、別の制約に引っかかるか、あるいは $f$ の最小値を見つけるかするまで解を更新する。別の制約に引っかかった場合は、それを有効制約に加え、1へ戻る。 $f$ の最小値が見つかったらもちろん終了。

ペナルティ法

目的関数を修正し、制約なし最適化問題として扱う手法。具体的には、ペナルティ関数 $P(x)$ と呼ばれる非負値連続関数を目的関数 $f(x)$ に次のように加える。

$f(x) + cP(x)$

等式制約に対してよく用いられるペナルティ関数は制約 $g_i(x)$ の二乗和。ペナルティ関数を絶対値の和とした手法は正確なペナルティ関数法と呼ばれる。通常のペナルティ法では、 $c$ を徐々に大きくして最適化問題を繰り返し解く。だが、 $c$ を十分に大きくしないと元の問題の最適化問題の解が求まらない一方で、 $c$ が大きいと最適化が困難になるというジレンマが存在する。正確なペナルティ関数法では、ある程度大きなパラメータ $c$ に対して１回だけ最適化を行えば、元の問題の局所解を得ることができる。

バリア関数法

方針はペナルティ法と同じ。 $g_i(x) = 0$ となる境界の点で無限大に発散する罰則項（バリア関数）を目的関数に加える点が異なる。こちらも最適化問題を繰り返し解くが、ペナルティ法とは違い、途中でイテレーションを止めてもそれまでで最も良い実行可能解が得られるとのこと。つまり、繰り返しは必要ないと思われる。テキスト上に記載はないが。