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

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

強凸関数のヘッセ行列の逆行列の不等式を証明する

数学 数理最適化

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

制約なし凸最適化問題の目的関数に強凸性を仮定することの意味について考える - エンジニアを目指す浪人のブログ

行列が半正定値(あるいは正定値)であるための必要十分条件はすべての固有値が非負(あるいは正)であることを証明する - エンジニアを目指す浪人のブログ


勉強を進めていて，強凸性(strong convexity)を仮定する関数のヘッセ行列の逆行列のみたす不等式を証明したので，メモしておくことにしました．

二階微分可能な関数 {\displaystyle f : \mathbb{R}^n \to \mathbb{R} } が強凸(strongly convex)であるとは，すべての {\displaystyle x \in \mathrm{dom} \ f } について以下をみたすような {\displaystyle m \gt 0 } が存在することです．{\displaystyle \mathrm{dom} \ f } は {\displaystyle f } の定義域，{\displaystyle I } は {\displaystyle n \times n } 単位行列，{\displaystyle \left\| \cdot \right\|_2 } はユークリッドノルムです．

(1.1){\displaystyle \;\;\; m I \preceq \nabla^2 f(x) }

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

関数 {\displaystyle f(x) } は二階微分可能で強凸であると仮定します．すると任意の有界閉集合 {\displaystyle D \subset \mathrm{dom} \ f } として以下をみたす {\displaystyle m \gt 0, M \gt 0, m \lt M } が存在します(冒頭の過去記事(制約なし凸最適化問題の目的関数)(1.3.1)にあります)．

(1.2){\displaystyle \;\;\; m I \preceq \nabla^2 f(x) \preceq M I, \;\;\; x \in D }


以上の設定の下で，本記事の目的に進みます．

以下の事実を示します．

'--------------------------------------------------------------------------------------------------------------------------------------------
事実.

強凸関数 {\displaystyle f } のヘッセ行列の逆行列について，以下が成り立つ．

{\displaystyle \;\;\; M^{-1} I \preceq \nabla^2 f(x)^{-1} \preceq m^{-1} I, \;\;\;\;\;\; m \gt 0, M \gt 0, m \lt M }


証明.

(1.1)より {\displaystyle \nabla^2 f(x) } は正定値である． {\displaystyle \nabla^2 f(x) } の固有値を {\displaystyle \lambda_{i}, \ i=1,\ldots,n } とすると，冒頭の過去記事(行列が半正定値)事実.より {\displaystyle \lambda_{i} \gt 0 } である．{\displaystyle \nabla^2 f(x) } は実対称行列なので，ある直交行列 {\displaystyle Q } で固有値分解できる(文献[2]にあります)．

(1.3){\displaystyle \;\;\; \nabla^2 f(x) = Q \ \mathrm{diag}(\lambda_1,\ldots,\lambda_n) \ Q^T }

以下の {\displaystyle z \in \mathbb{R}^n } を考える． {\displaystyle Q^T } は直交行列なので列ベクトル(行ベクトル)は正規直交基底になっており(文献[3]にあります)，したがって {\displaystyle w \neq 0 \Leftrightarrow z \neq 0 } である．

(1.4){\displaystyle \;\;\; z = Q^T w }


(1.2)より以下を得る．

(1.5){\displaystyle \;\;\; m I \preceq Q \ \mathrm{diag}(\lambda_1,\ldots,\lambda_n) \ Q^T \preceq M I \;\;\; \because } (1.3)

{\displaystyle \Leftrightarrow \ m \left[ w^T w \right] \le w^T \left[ Q \ \mathrm{diag}(\lambda_1,\ldots,\lambda_n) \ Q^T \right] w \le M \left[ w^T w \right], \;\;\; w \in \mathbb{R}^n, \; w \neq 0 }

{\displaystyle \Leftrightarrow \ m \left[ w^T Q Q^T w \right] \le \left[ w^T Q \right] \ \mathrm{diag}(\lambda_1,\ldots,\lambda_n) \ \left[ Q^T w \right] \le M \left[ w^T Q Q^T w \right] \;\;\; \because Q^T = Q^{-1} }

{\displaystyle \Leftrightarrow \ m \left[ z^T z \right] \le z^T \ \mathrm{diag}(\lambda_1,\ldots,\lambda_n) \ z \le M \left[ z^T z \right], \;\;\; z \in \mathbb{R}^n, \; z \neq 0 \;\;\; \because } (1.4)


{\displaystyle \Leftrightarrow \ m \left\| z \right\|_2^2 \le \lambda_1 z_1^2 + \cdots + \lambda_n z_n^2 \le M \left\| z \right\|_2^2 }

{\displaystyle \Leftrightarrow \ m z_1^2 + \cdots + m z_n^2 \le \lambda_1 z_1^2 + \cdots + \lambda_n z_n^2 \le M z_1^2 + \cdots + M z_n^2 }

{\displaystyle \Leftrightarrow \ m \le \lambda_1, \ \cdots, \ m \le \lambda_n, \;\;\;\;\;\; \lambda_1 \le M, \ \cdots, \ \lambda_n \le M }

{\displaystyle \Leftrightarrow \ \frac{1}{\lambda_1} \le \frac{1}{m} , \ \cdots \ , \frac{1}{\lambda_n} \le \frac{1}{m} , \;\;\;\;\;\; \frac{1}{M} \le \frac{1}{\lambda_1}, \ \cdots, \ \frac{1}{M} \le \frac{1}{\lambda_n} }

{\displaystyle \Leftrightarrow \ \frac{1}{M} z_1^2 + \cdots + \frac{1}{M} z_n^2 \le \frac{1}{\lambda_1} z_1^2 + \cdots + \frac{1}{\lambda_n} z_n^2 \le \frac{1}{m} z_1^2 + \cdots + \frac{1}{m} z_n^2 }

{\displaystyle \Leftrightarrow \ \frac{1}{M} \left\| z \right\|_2^2 \le \frac{1}{\lambda_1} z_1^2 + \cdots + \frac{1}{\lambda_n} z_n^2 \le \frac{1}{m} \left\| z \right\|_2^2 }


{\displaystyle \Leftrightarrow \ \frac{1}{M} \left[ z^T z \right] \le z^T \ \mathrm{diag}(1/\lambda_1,\ldots,1/\lambda_n) \ z \le \frac{1}{m} \left[ z^T z \right], \;\;\; z \in \mathbb{R}^n, \; z \neq 0 }

{\displaystyle \Leftrightarrow \ \frac{1}{M} \left[ w^T Q Q^T w \right] \le \left[ w^T Q \right] \ \mathrm{diag}(1/\lambda_1,\ldots,1/\lambda_n) \ \left[ Q^T w \right] \le \frac{1}{m} \left[ w^T Q Q^T w \right] \;\;\; \because } (1.4)

{\displaystyle \Leftrightarrow \ \frac{1}{M} \left[ w^T w \right] \le w^T \left[ Q \ \mathrm{diag}(1/\lambda_1,\ldots,1/\lambda_n) \ Q^T \right] w \le \frac{1}{m} \left[ w^T w \right] \;\;\; \because Q^T = Q^{-1} }

{\displaystyle \Leftrightarrow \ \frac{1}{M} \left[ w^T w \right] \le w^T \left[ Q \ \mathrm{diag}(\lambda_1,\ldots,\lambda_n)^{-1} \ Q^T \right] w \le \frac{1}{m} \left[ w^T w \right] }

{\displaystyle \Leftrightarrow \ \frac{1}{M} \left[ w^T w \right] \le w^T \left[ (Q^{T})^{-1} \ \mathrm{diag}(\lambda_1,\ldots,\lambda_n)^{-1} \ Q^{-1} \right] w \le \frac{1}{m} \left[ w^T w \right] }

{\displaystyle \Leftrightarrow \ \frac{1}{M} \left[ w^T w \right] \le w^T \left[ Q \ \mathrm{diag}(\lambda_1,\ldots,\lambda_n) \ Q^T \right]^{-1} w \le \frac{1}{m} \left[ w^T w \right] }

{\displaystyle \Leftrightarrow \ \frac{1}{M} I \preceq \left[ Q \ \mathrm{diag}(\lambda_1,\ldots,\lambda_n) \ Q^T \right]^{-1} \preceq \frac{1}{m} I }

{\displaystyle \Leftrightarrow \ \frac{1}{M} I \preceq \nabla^2 f(x)^{-1} \preceq \frac{1}{m} I \;\;\; \because } (1.3)


(証明終わり)
'--------------------------------------------------------------------------------------------------------------------------------------------


以上，強凸関数のヘッセ行列の逆行列の不等式を証明しました．



参考文献
[1] Boyd, S., and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.
[2] Wikipedia Eigendecomposition of a matrix のページ https://en.wikipedia.org/wiki/Eigendecomposition_of_a_matrix
[3] Wikipedia Orthogonal matrix のページ https://en.wikipedia.org/wiki/Orthogonal_matrix