制約なし凸最適化問題の目的関数に強凸性を仮定することの意味について考える

本記事は以下の過去記事の内容を用います．

勉強を進めていて，凸最適化問題の目的関数についての強凸(strong convexity)という性質について知り，その内容が面白くまた重要に感じました．そこで，強凸性を仮定することの意味について，目的関数の具体的な関数形やアルゴリズムには踏み込まない階層における内容をまとめておくことにしました．Boyd and Vandenberghe(2004)の9章1節をベースにしています．

=================================================================================

$\;$ 0. 準備
$\;\;\;$ 0.1. 制約なし凸最適化問題
$\;\;\;$ 0.2. 初期点と劣位集合

$\;$ 1. 強凸性を仮定することの意味
$\;\;\;$ 1.1. 二階導関数の下界
$\;\;\;$ 1.2. 二階導関数の上界
$\;\;\;$ 1.3. 劣位集合の条件数
$\;\;\;$ 1.4. 強凸性の定数
$\;\;\;$ 1.5. まとめ

[ 0. 準備 ]

[ 0.1. 制約なし凸最適化問題 ]

制約なし最適化問題(unconstrained optimization problem)を導入します． $x \in \mathbb{R}^n$ です．

(0.1.1)
$\mathrm{minimize} \;\;\;\; f(x)$

$\mathcal{D} = \mathrm{dom} \ f$ を最適化問題(0.1.1)の定義域(domain)といいます．目的関数 $f : \mathbb{R}^n \to \mathbb{R}$ は凸で二階微分可能であるとします(よって $\mathrm{dom} \ f$ は開集合です)．以後，この問題は求解可能，すなわち最適点 $x^*$ が存在すると仮定します(より正確には，このとき強凸性の仮定を追加すると最適点はただ一つ存在します．次の章で示します)．最適値を $f(x^*)= p^*$ とします．

関数 $f$ は(二階)微分可能で凸なので， $x^*$ が最適となるための必要十分条件は以下です(例えば文献[3] THEOREM 1.2.2 にあります(有名な結果なので証明なしで用います))．

(0.1.2) $\;\;\; \nabla f(x^*) = 0$

このように，制約なし凸最適化問題(0.1.1)を解くことは， $n$ 本の方程式と $n$ 個の変数 $x_1, \ldots , x_n$ からなる方程式(0.1.2)の解を求めることと等価です．いくつかの特別な場合に(0.1.2)を代数的に解くことが可能ですが，通常は $f(x^{(k)}) \to p^*, \ k \to \infty$ となる点列 $x^{(0)},x^{(1)},\ldots \in \mathrm{dom} \ f$ を計算する反復的アルゴリズム(iterative algorithm)を用います．そのような点列を問題(0.1.1)の最小化列(minimizing sequence)といいます．アルゴリズムはある許容誤差を $\epsilon \gt 0$ として収束判定条件 $f(x^{(k)}) - p^* \le \epsilon$ をみたすとき終了します．

[ 0.2. 初期点と劣位集合 ]

アルゴリズムの初期点 $x^{(0)} \in \mathrm{dom} \ f$ とします．関数 $f$ の劣位集合(sublevel set)とは以下で定義される集合です．

(0.2.1) $\;\;\; S = \{ x \in \mathrm{dom} \ f \; | \; f(x) \le f(x^{(0)}) \}$

劣位集合 $S$ は $f$ が(二階微分可能なので)連続であることから閉集合です(冒頭の過去記事(連続関数の劣位集合)にあります)．

この劣位集合が閉集合であるという条件は，関数 $f$ が閉(closed)すなわちすべての劣位集合が閉のとき(文献[4]にあります)，すべての $x^{(0)} \in \mathrm{dom} \ f$ について成り立ちます． $\mathbb{R}^n$ は開集合でも閉集合でもあります．したがって $\mathrm{dom} \ f = \mathbb{R}^n$ の連続関数 $f$ は閉なので， $\mathrm{dom} \ f = \mathbb{R}^n$ ならば任意の $x^{(0)}$ について劣位集合は閉集合となります．また， $\mathrm{dom} \ f$ が開集合で $f(x) \to \infty, \; x \to \mathrm{bd \; dom} \ f$ ( $\mathrm{bd}$ の定義は文献[5]にあります)をみたす連続関数 $f$ は閉なので，任意の $x^{(0)}$ について劣位集合は閉集合となります．

[ 1. 強凸性を仮定することの意味 ]

本記事の目的に進みます．二階微分可能な凸関数の最適化問題(0.1.1)の目的関数 $f$ に強凸性を仮定することの意味について考えていきます．

[ 1.1. 二階導関数の下界 ]

目的関数 $f$ は $S$ 上で強凸(strongly convex)であると仮定します．強凸とは，すべての $x \in S$ について以下をみたすような $m \gt 0$ が存在することです． $I$ は $n \times n$ 単位行列， $\left\| \cdot \right\|_2$ はユークリッドノルムです．

(1.1.1) $\;\;\; m I \preceq \nabla^2 f(x)$

$\;\;\;\;\; \Leftrightarrow \; m \left\| w \right\|_2^2 \le w^T \nabla^2 f(x) w, \;\; w \in \mathbb{R}^n, \; w \neq 0$

すべての $x,y \in S$ と線分 $[ x,y ]$ 上の点 $z$ (ただし $z \neq x,y$ )について以下を得ます．

(1.1.2) $\;\;\; f(y) = f(x) + \nabla f(x)^T (y - x) + \frac{1}{2} (y - x)^T \nabla^2 f(z) (y - x) \;\;\; \because$ テイラーの定理(文献[6])

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge f(x) + \nabla f(x)^T (y - x) + \frac{1}{2} (y - x)^T\ m I \ (y - x) \;\;\;\;\;\; \because$ (1.1.1)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f(x) + \nabla f(x)^T (y - x) + \frac{m}{2} \left\| y - x \right\|_2^2$

$m = 0$ のとき凸関数を意味する不等式となります(冒頭の過去記事(ラグランジュ関数)(0.9)にあります); $m \gt 0$ のとき凸関数よりもよい(大きい) $f(y)$ の下界(lower bound)を得ます．

強凸性を仮定することにより得られる不等式(1.1.2)を用いて以下の事実を示すことができます．

'--------------------------------------------------------------------------------------------------------------------------------------------
事実1.(強凸性)

・ $(1/2m) \left\| \nabla f(x) \right\|_2^2$ により $f(x) - p^*$ を上から抑えられる．(点 $x$ の準最適性(suboptimality))
・ $(2/ \ m) \ \left\| \nabla f(x) \right\|_2$ により $\left\| x - x^* \right\|_2$ を上から抑えられる．
・最適点 $x^*$ はただ一つに定まる
'--------------------------------------------------------------------------------------------------------------------------------------------

はじめに， $\left\| \nabla f(x) \right\|_2^2$ により $f(x) - p^*$ を上から抑えられることを示します．(1.1.2)の最右辺は( $x$ を固定すると) $y$ の二次関数で係数行列が単位行列なので凸です(冒頭の過去記事(係数行列が対称行列)定理 1.を $Q = I$ として用います)．勾配が零となる $y = \tilde{y}$ は以下です．

(1.1.3) $\;\;\; 0 = \nabla \left[ f(x) + \nabla f(x)^T (y - x) + \frac{m}{2} \left\| y - x \right\|_2^2 \right]$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \nabla \left[ \nabla f(x)^T y + (m/2) \left\| y - x \right\|_2^2 \right]$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \nabla f(x) + (m/2) \left( 2 y - 2 x \right)$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \nabla f(x) + m \left( y - x \right)$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow \ \tilde{y} = x - (1/m) \nabla f(x) \;\;\; \because m \gt 0$

これを用いて以下を得ます．

(1.1.4) $\;\;\; f(y) \ge f(x) + \nabla f(x)^T (y - x) + \frac{m}{2} \left\| y - x \right\|_2^2$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge f(x) + \nabla f(x)^T ( \tilde{y} - x) + (m/2) \left\| \tilde{y} - x \right\|_2^2$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f(x) + \nabla f(x)^T \left[ - (1/m) \nabla f(x) \right] + (m/2) \left\| - (1/m) \nabla f(x) \right\|_2^2 \;\;\; \because$ (1.3)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f(x) - \frac{1}{2m} \left\| \nabla f(x) \right\|_2^2$

(1.1.5) $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \Rightarrow \ p^* \ge f(x) - \frac{1}{2m} \left\| \nabla f(x) \right\|_2^2 \;\;\; \because y \in S$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow f(x) - \ p^* \le \frac{1}{2m} \left\| \nabla f(x) \right\|_2^2$

この不等式は，勾配が小さい点は最適点 $x^*$ に近い点であることを示しています．また，この不等式は最適性条件(0.1.2)の一般化である準最適性条件として解釈することも可能です(最適性条件は $\nabla f = 0$ を扱い，準最適性条件は $\nabla f \approx 0$ を扱っています)．以下に示します:

(1.1.6) $\;\;\; \left\| \nabla f(x) \right\|_2 \le (2 m \epsilon)^{1/2}$

$\;\;\;\;\;\;\;\;\; \Leftrightarrow (1/ 2 m ) \left\| \nabla f(x) \right\|_2^2 \le \epsilon \;\;\; \because m \gt 0$

$\;\;\;\;\;\;\;\;\; \Rightarrow \ f(x) - p^* \le \epsilon \;\;\;\;\;\; \because$ (1.1.5)

次に， $x$ と任意の最適点 $x^*$ の距離 $\left\| x - x^* \right\|_2$ が $\left\| \nabla f(x) \right\|_2$ により上から抑えられることを示します．(1.1.2)で $y = x^*$ として以下を得ます． $\langle \cdot , \cdot \rangle$ は通常の内積です．

(1.1.7) $\;\;\; p^* = f(x^*)$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge f(x) + \nabla f(x^*)^T (x^* - x) + \left( m/2 \right) \left\| x^* - x \right\|_2^2$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f(x) + \langle \nabla f(x^*) , x^* - x \rangle + ( m / 2 ) \left\| x^* - x \right\|_2^2$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge f(x) - \left\| \nabla f(x^*) \right\|_2 \left\| x^* - x \right\|_2 + ( m / 2 ) \left\| x^* - x \right\|_2^2$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because$ コーシーシュワルツの不等式(文献[7]にあります)

$\;\;\;\;\;\;\;\;\;\;\; 0 \ge p^* - f(x) \;\;\; \because f(x) \ge p^*$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge - \left\| \nabla f(x^*) \right\|_2 + ( m / 2 ) \left\| x^* - x \right\|_2 \;\;\; \because x \neq x^*$

(1.1.8) $\;\;\;\;\;\;\;\;\; \Leftrightarrow \ \left\| x - x^* \right\|_2 \le \frac{2}{m} \left\| \nabla f(x) \right\|_2$

ここで $x^*$ とは別に最適点 $x = z^*$ が存在すると仮定して(1.1.8)に代入すると以下となり， $x^* \neq z^*$ に矛盾します．したがって(1.1.8)より(強凸関数の)最適点 $x^*$ はただ一つであることがわかります．

(1.1.9) $\;\;\;\;\;\;\;\;\; \ \left\| z^* - x^* \right\|_2 \le (2/m) \left\| \nabla f(z^*) \right\|_2$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 0 \;\;\; \because$ (0.1.2)

[ 1.2. 二階導関数の上界 ]

(1.1.2)はすべての $x, y \in S$ について成り立つので， $x = x^*$ (ただ一つの最適点)とすると以下を得ます．

(1.2.0) $\;\;\; f(x_0) \ge f(y) \;\;\;\; \because$ (0.2.1)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge f(x^*) + \nabla f(x^*)^T (y - x^*) + \frac{m}{2} \left\| y - x^* \right\|_2^2 \;\;\; \because$ (1.1.2)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f(x^*) + \frac{m}{2} \left\| y - x^* \right\|_2^2 \;\;\; \because$ (0.1.2)

$\;\;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow \ \left\| y - x^* \right\|_2^2 \le \frac{2}{m} \left( f(x_0) - f(x^*) \right), \;\; y \in S \;\;\; \because m \gt 0$

したがって劣位集合 $S$ は有界集合です(文献[8]にあります)．

連続関数である $n \times n$ 行列 $\nabla^2 f(x), \; x \in S$ の固有多項式は係数が連続関数の多項式なので，固有値は連続関数です(文献[9]にあります)．したがって有界性定理(boundedness theorem)(文献[10][11]にあります)より $\nabla^2 f(x), \; x \in S$ の最大固有値は有界閉集合 $S$ 上で有界です．すなわちすべての $x \in S$ について以下をみたすような定数 $M \gt 0$ が存在します．行列 $\nabla^2 f(x)$ の固有値の総和(行列 $\nabla^2 f(x)$ の対角成分の総和)は $M n$ 以下となることを意味します．

(1.2.1) $\;\;\; \nabla^2 f(x) \preceq M I$

$\;\;\;\; \Leftrightarrow \; w^T \nabla^2 f(x) w \le M \left\| w \right\|_2^2 \ \;\; w \in \mathbb{R}^n, \; w \neq 0$

任意の $x, y \in S$ について(1.1.2)と同様に以下を得ます．

(1.2.2) $\;\;\; f(y) = f(x) + \nabla f(x)^T (y - x) + \frac{1}{2} (y - x)^T \nabla^2 f(z) (y - x) \;\;\; \because$ テイラーの定理(文献[6])

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le f(x) + \nabla f(x)^T (y - x) + \frac{1}{2} (y - x)^T\ M I \ (y - x) \;\;\;\;\;\; \because$ (1.2.1)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f(x) + \nabla f(x)^T (y - x) + \frac{M}{2} \left\| y - x \right\|_2^2$

強凸性を仮定することにより得られる不等式(1.2.2)を用いて以下の事実を示すことができます．

'--------------------------------------------------------------------------------------------------------------------------------------------
事実2.(強凸性)

・ $(1/2M) \left\| \nabla f(x) \right\|_2^2$ により $f(x) - p^*$ を下から抑えられる．
'--------------------------------------------------------------------------------------------------------------------------------------------

(1.2.2)の左辺を $y = x^*$ ，右辺を(1.1.3)で求めた $\tilde{y}$ の $m$ を $M$ と置き換えたものを用いて両辺を最小化すると以下を得ます．これは(1.1.5)に対応するものです．

(1.2.3) $\;\;\; p^* \le f(x) + \nabla f(x)^T \left[ - (1/M) \nabla f(x) \right] + (M/2) \left\| - (1/M) \nabla f(x) \right\|_2^2$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f(x) - \frac{1}{2M} \left\| \nabla f(x) \right\|_2^2$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow \ \frac{1}{2M} \left\| \nabla f(x) \right\|_2^2 \le f(x) - p^*$

[ 1.3. 劣位集合の条件数 ]

強凸性を仮定したことにより得られる不等式(1.1.1)(1.2.1)より以下を得ます．

(1.3.1) $\;\;\; m I \preceq \nabla^2 f(x) \preceq M I, \;\;\; x \in S$

強凸性を仮定することにより得られる不等式(1.3.1)を用いて以下の事実を示すことができます．条件数の定義は，冒頭の過去記事(凸集合の条件数)にあります．

'--------------------------------------------------------------------------------------------------------------------------------------------
事実3.(強凸性)

・ $M / m$ により $\alpha$ -劣位集合 $C_\alpha = \{ x \in \mathrm{dom} \ | \ f(x) \le \alpha \}$ の条件数を上から抑えられる．
・ $M / m$ により行列 $\nabla^2 f(x^*)$ の条件数(最大固有値と最小固有値の比)を上から抑えられる．
・ $C_\alpha$ は $\alpha$ が $p^*$ に近いとき中心 $x^*$ の楕円で近似できる．
'--------------------------------------------------------------------------------------------------------------------------------------------

(1.3.1)が成り立つときの $C_\alpha, \; p^* \lt \alpha \le f(x^{(0)})$ の条件数の上界を導出します．

中心点 $x^*$ の球を二つ定義します． $m \le M$ より $B_{\alpha,\mathrm{inner}} \subseteq B_{\alpha,\mathrm{outer}}$ です．

(1.3.2) $\;\;\; B_{\alpha,\mathrm{inner}}= \{ y \ | \ \left\| y - x^* \right\|_2 \le \left( 2 ( \alpha - p^* ) / M \right)^{1/2} \}$

(1.3.3) $\;\;\; B_{\alpha,\mathrm{outer}} = \{ y \ | \ \left\| y - x^* \right\|_2 \le \left( 2 ( \alpha - p^* ) / m \right)^{1/2} \}$

強凸性を仮定することにより得られる不等式(1.1.2)(1.2.2)で $x = x^*$ として以下を得ます．

(1.3.4) $\;\;\; p^* + \frac{m}{2} \left\| y - x^* \right\|_2^2 \le f(y) \le p^* + \frac{M}{2} \left\| y - x^* \right\|_2^2, \;\; y \in S$

$\;\;\;\;\;\; \Rightarrow \ p^* + \frac{m}{2} \left\| y - x^* \right\|_2^2 \le f(y) \le p^* + \frac{M}{2} \left\| y - x^* \right\|_2^2, \;\; y \in C_\alpha \;\;\; \because \forall \alpha, \; C_\alpha \subseteq S$

左側の不等式について考えます．

(1.3.5) $\;\;\; p^* + \frac{m}{2} \left\| y - x^* \right\|_2^2 \le f(y), \;\; y \in C_\alpha$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \alpha \;\;\; \because y \in C_\alpha$

$\;\;\;\;\;\; \Rightarrow \ \left\| y - x^* \right\|_2 \le \left( 2 ( \alpha - p^* ) / m \right)^{1/2} \;\;\; \because m \gt 0$

$\;\;\;\;\;\; \Leftrightarrow \ y \in B_{\alpha,\mathrm{outer}} \;\;\; \because$ (1.3.3)

$\;\;\;\;\;\; \Rightarrow \ C_\alpha \subseteq B_{\alpha,\mathrm{outer}}$

右側の不等式について考えます．

(1.3.6) $\;\;\; f(y) \le p^* + \frac{M}{2} \left\| y - x^* \right\|_2^2, \;\; y \in S$

$y \notin C_\alpha$ とします．

(1.3.7) $\;\;\; y \notin C_\alpha$

$\;\;\;\;\;\; \Rightarrow \ \alpha \lt f(y)$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le p^* + \frac{M}{2} \left\| y - x^* \right\|_2^2 \;\;\; \because$ (1.3.6)

$\;\;\;\;\;\; \Leftrightarrow \ \left\| y - x^* \right\|_2 \gt \left( 2 ( \alpha - p^* ) / M \right)^{1/2}$

$\;\;\;\;\;\; \Leftrightarrow \ y \notin B_{\alpha,\mathrm{inner}}$

対偶をとって $[ y \in B_{\alpha,\mathrm{inner}} \ \Rightarrow \ y \in C_\alpha ]$ が示せたので以下を得ます．

(1.3.8) $\;\;\; B_{\alpha,\mathrm{inner}} \subseteq C_\alpha$

したがって(1.3.5)(1.3.8)をまとめると以下を得ます．

(1.3.9) $\;\;\; B_{\alpha,\mathrm{inner}} \subseteq C_\alpha \subseteq B_{\alpha,\mathrm{outer}}$

冒頭の過去記事(連続関数の劣位集合)事実1.より $C_\alpha$ は凸集合です． $C_\alpha$ の条件数 $\mathrm{cond}(C_\alpha)$ は二つの球 $B_{\alpha,\mathrm{inner}}, \ B_{\alpha,\mathrm{outer}}$ の半径の二乗の比により上から抑えられます:

(1.3.10) $\;\;\; \mathrm{cond}(C_\alpha) = \frac{ \left( W_{\mathrm{max}}(C_\alpha) \right)^2}{ \left( W_{\mathrm{min}}(C_\alpha) \right)^2} \;\;\; \because$ 冒頭の過去記事(凸集合の条件数)(1.4)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \frac{ 2 ( \alpha - p^* ) / m }{ 2 ( \alpha - p^* ) / M } \;\;\; \because$ (1.3.2)(1.3.3)(1.3.9)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{ M }{ m }$

次に，行列 $\nabla^2 f(x)$ の最適点 $x^*$ における条件数 $\kappa \left(\nabla^2 f(x^*) \right)$ の幾何的解釈を考えます．テイラーの定理より $f(y)$ を $y = x^*$ のまわりで展開して以下を得ます．

(1.3.11) $\;\;\; f(y) \approx p^* + \nabla f(x^*)^T (y - x^*) + \frac{1}{2} (y - x^*)^T \nabla^2 f(x^*) (y - x^*)$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = p^* + \frac{1}{2} (y - x^*)^T \nabla^2 f(x^*) (y - x^*)$

$p^*$ に近い $\alpha$ において劣位集合 $C_\alpha$ は以下となります．

(1.3.12) $\;\;\; C_\alpha = \{ y \ | \ f(y) \le \alpha \}$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \approx \{ y \ | \ p^* + \frac{1}{2} (y - x^*)^T \nabla^2 f(x^*) (y - x^*) \le \alpha \} \;\;\; \because$ (1.3.11)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \{ y \ | \ (y - x^*)^T \nabla^2 f(x^*) (y - x^*) \le 2 \left( \alpha - p^* \right) \}$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \{ y \ | \ (y - x^*)^T \frac{1}{2 \left( \alpha - p^* \right)} \nabla^2 f(x^*) (y - x^*) \le 1$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \{ y \ | \ (y - x^*)^T \left[ \left( \frac{1}{2 \left( \alpha - p^* \right)} \nabla^2 f(x^*) \right)^{-1} \right]^{-1} (y - x^*) \le 1$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \{ y \ | \ (y - x^*)^T \left[ 2 \left( \alpha - p^* \right) \left[ \nabla^2 f(x^*) \right]^{-1} \right]^{-1} (y - x^*) \le 1$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because (k A)^{-1} = k^{-1}A^{-1}, k \neq 0$ (文献[12]にあります)

すなわち， $p^*$ に近い $\alpha$ において $C_\alpha$ は中心点 $x^*$ の楕円により精度よく近似できます．したがって条件数は以下となります．

(1.3.13) $\;\;\; \lim_{ \alpha \to p^* } \mathrm{cond}(C_\alpha) = \kappa \left( 2 \left( \alpha - p^* \right) \left[ \nabla^2 f(x^*) \right]^{-1} \right) \;\;\; \because$ 冒頭の過去記事(凸集合の条件数)(1.9)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \kappa \left( \left[ \nabla^2 f(x^*) \right]^{-1} \right)$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \kappa \left( \nabla^2 f(x^*) \right) \;\;\; \because$ 冒頭の過去記事(凸集合の条件数)事実.

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le M / m \;\;\; \because$ (1.3.10)

以上の結果(1.3.13)より，行列 $\nabla^2 f(x^*)$ の条件数，すなわち最大固有値と最小固有値の比，の上界は $\kappa = M / m$ であることがわかります．

[ 1.4. 強凸性の定数 ]

定数 $m, \ M$ は通常は未知のパラメータなので，実際には(1.1.6)を収束判定として用いることはできません．それは勾配 $\nabla f(x)$ が十分小さい $x$ のとき， $f(x)$ と $p^*$ の差が小さい，という概念的な収束判定条件です． $(m \epsilon)^{1/2}$ よりも十分小さくなるような十分小さい $\eta$ をとり， $\left\| \nabla f(x^{(k)}) \right\|_2 \le \eta$ のときにアルゴリズムを止めるとき， $f(x^{(k)}) - p^* \le \epsilon$ となります．

[ 1.5. まとめ ]

制約なし凸最適化問題の目的関数に強凸を仮定することの意味をまとめます．

'--------------------------------------------------------------------------------------------------------------------------------------------
事実.(強凸性)(再掲)

・ $(1/2m) \left\| \nabla f(x) \right\|_2^2$ により $f(x) - p^*$ を上から抑えられる．(点 $x$ の準最適性)
・ $(1/2M) \left\| \nabla f(x) \right\|_2^2$ により $f(x) - p^*$ を下から抑えられる
・ $(2/ \ m) \ \left\| \nabla f(x) \right\|_2$ により $\left\| x - x^* \right\|_2$ を上から抑えられる．
・最適点 $x^*$ はただ一つに定まる
・ $M / m$ により $\alpha$ -劣位集合 $C_\alpha = \{ x \in \mathrm{dom} \ | \ f(x) \le \alpha \}$ の条件数を上から抑えられる．
・ $M / m$ により行列 $\nabla^2 f(x^*)$ の条件数(最大固有値と最小固有値の比)を上から抑えられる．
・ $C_\alpha$ は $\alpha$ が $p^*$ に近いとき中心 $x^*$ の楕円で近似できる．
'--------------------------------------------------------------------------------------------------------------------------------------------

=================================================================================

以上，制約なし凸最適化問題の目的関数に強凸性を仮定することの意味について考えてみました．

参考文献
[1] Boyd, S., and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.
[2] 東京大学松島慎先生のノート https://ml.c.u-tokyo.ac.jp/wp-content/uploads/2020/05/optimization.pdf
[3] University of Washington Jim Burke先生のノート https://sites.math.washington.edu/~burke/crs/516/notes/ch1.pdf

[4] Wikipedia Closed convex functionのページ https://en.wikipedia.org/wiki/Closed_convex_function
[5] Wikipedia Boundary (topology)のページ https://en.wikipedia.org/wiki/Boundary_(topology)
[6] Wikipedia Taylor's theoremのページ https://en.wikipedia.org/wiki/Taylor%27s_theorem
[7] Wikipedia Cauchy Schwarz inequalityのページ https://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality
[8] Wikipedia Bounded setのページ https://en.wikipedia.org/wiki/Bounded_set
[9] Mathematics Stack Exchange https://math.stackexchange.com/questions/556137/eigenvalues-are-continuous
[10] Wikipedia Extreme value theoremのページ https://en.wikipedia.org/wiki/Extreme_value_theorem
[11] Mathematics Stack Exchange https://math.stackexchange.com/questions/881564/multivariable-version-of-the-extreme-value-theorem
[12] Wikipedia Invertible matrixのページ https://en.wikipedia.org/wiki/Invertible_matrix

エンジニアを目指す浪人のブログ

情報系に役立ちそうな応用数理をゆるめにメモします

制約なし凸最適化問題の目的関数に強凸性を仮定することの意味について考える