凸集合の条件数について考える - エンジニアを目指す浪人のブログ

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

勉強を進めていて，数理最適化における凸集合の条件数(condition number)についてモヤモヤしてしまったので，内容をまとめておくことにしました．Boyd and Vandenberghe(2004)の9章1節(の一部)をベースにしています．

問題を設定するため，いくつか準備をします．

凸集合の定義は文献[2]にあります．
(ユークリッド)ノルムの定義は文献[3]にあります．
行列の条件数の定義は文献[4]にあります．
平方根行列の定義は冒頭の過去記事(行列式の対数)事実0.4.にあります．

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

凸集合 $C \subseteq \mathbb{R}^n$ の，方向(ベクトル) $q \in \mathbb{R}^n, \; \left\| q \right\|_2 = 1$ における幅(width)を以下のように定義します． $q^T z$ は内積なので，第一項では $q$ に最も方向が近いベクトル $z$ を $C$ の中からとります．同様に，第二項では $-q$ に最も方向が近い( $q$ と逆方向の)ベクトル $z$ を $C$ の中からとります．

(1.1) $\;\;\; W(C,q) = \sup_{z \in C} q^T z - \inf_{z \in C} q^T z$

最小幅(minimum width)，最大幅(maximum width)を以下とします．それぞれ，幅が最小になる方向ベクトル $q$ ，幅が最大になる方向ベクトル $q$ をとります．

(1.2) $\;\;\; W_{\mathrm{min}}(C) = \inf_{\left\| q \right\|_2 = 1} W(C,q)$

(1.3) $\;\;\; W_{\mathrm{max}}(C) = \sup_{\left\| q \right\|_2 = 1} W(C,q)$

凸集合 $C$ の条件数を以下のように定義します．

(1.4) $\;\;\; \mathrm{cond}(C) = \frac{ \left( W_{\mathrm{max}}(C) \right)^2}{ \left( W_{\mathrm{min}}(C) \right)^2} \; ( \geq 1 )$

条件数は異方性(anisotropy)あるいは離心率(eccentricity)の尺度です．条件数が小さい(1に近い)とき，凸集合 $C$ は全ての方向についておおよそ同じ幅となっています．例えば球です．条件数が大きいとき，凸集合はある方向について他の方向よりも幅が大きく(広く)なっていることを意味します．

具体例を考えます．
'--------------------------------------------------------------------------------------------------------------------------------------------
例 9.1
$n \times n$ 行列 $A$ は対称行列で正定値とします．楕円 $\mathcal{E}$ を考えます(楕円は凸集合です)．

(1.5) $\;\;\; \mathcal{E} = \{ x \; | \; (x - x_0)^T A^{-1} (x - x_0) \leq 1 \}$

$\;\;\;\;\;\;\;\;\;\;\;\; = \left\{ x \; | \; (x - x_0)^T \left( A^{1/2} A^{1/2} \right)^{-1} (x - x_0) \leq 1 \right\} \because$ 冒頭の過去記事(行列式の対数)事実0.4.

$\;\;\;\;\;\;\;\;\;\;\;\; = \left\{ x \; | \; (x - x_0)^T A^{-1/2} A^{-1/2} (x - x_0) \leq 1 \right\} \;\;\; \because$ 冒頭の過去記事(行列式の対数)事実0.4.

$\;\;\;\;\;\;\;\;\;\;\;\; = \left\{ x \; | \; \left[ A^{-1/2} (x - x_0) \right]^T \left[ A^{-1/2} (x - x_0) \right] \leq 1 \right\}$

$\;\;\;\;\;\;\;\;\;\;\;\; = \left\{ x \; | \; \left\| A^{-1/2} (x - x_0) \right\|_2^2 \leq 1 \right\}$

$\;\;\;\;\;\;\;\;\;\;\;\; = \left\{ x \; | \; u = A^{-1/2} (x - x_0), \ \left\| u \right\|_2 \leq 1 \right\}$

$\;\;\;\;\;\;\;\;\;\;\;\; = \{ x \; | \; x = x_0 + A^{1/2} u, \; \left\| u \right\|_2 \leq 1 \}$

楕円 $\mathcal{E}$ の幅は以下です． $\left\| q \right\|_2 = 1$ です． $A$ の最小固有値を $\lambda_{\mathrm{min}}(A)$ ，最大固有値を $\lambda_{\mathrm{max}}(A)$ とします．

(1.6) $\;\;\; W(\mathcal{E},q) = \sup_{z \in \mathcal{E}} q^T z - \inf_{z \in \mathcal{E}} q^T z$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \sup_{\left\| u \right\|_2 \leq 1} q^T \left( x_0 + A^{1/2} u \right) - \inf_{\left\| u \right\|_2 \leq 1} q^T \left( x_0 + A^{1/2} u \right)$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = q^T x_0 + \sup_{\left\| u \right\|_2 \leq 1} \left( q^T A^{1/2} u \right) - q^T x_0 - \inf_{\left\| u \right\|_2 \leq 1} \left( q^T A^{1/2} u \right)$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \sup_{\left\| u \right\|_2 \leq 1} \left( A^{1/2} q \right)^T u - \inf_{\left\| u \right\|_2 \leq 1} \left( A^{1/2} q \right)^T u \;\;\; \because ( A^{1/2} )^T = A^{1/2}$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| A^{1/2} q \right\|_2 - \left( - \left\| A^{1/2} q \right\|_2 \right) \;\;\; \because$ ベクトルの内積の最大と最小を考える

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 2 \left\| A^{1/2} q \right\|_2$

(1.7) $\;\;\; W_{\mathrm{min}}(\mathcal{E}) = \inf_{\left\| q \right\|_2 = 1} W(\mathcal{E},q) \;\;\; \because$ (1.2)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 2 \inf_{\left\| q \right\|_2 = 1} \left\| A^{1/2} q \right\|_2 \;\;\; \because$ (1.6)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 2 \inf_{\left\| q \right\|_2 = 1} \left[ ( A^{1/2} q )^T ( A^{1/2} q ) \right]^{1/2}$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 2 \inf_{\left\| q \right\|_2 = 1} \left[ q^T (A^{1/2})^T A^{1/2} q \right]^{1/2}$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 2 \inf_{\left\| q \right\|_2 = 1} \left[ q^T A^{1/2} A^{1/2} q \right]^{1/2} \;\;\; \because ( A^{1/2} )^T = A^{1/2}$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 2 \inf_{\left\| q \right\|_2 = 1} \left[ q^T A q \right]^{1/2}$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 2 \left[\inf_{\left\| q \right\|_2 = 1} q^T A q \right]^{1/2} \;\;\; \because q^T A q \gt 0$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 2 [ \lambda_{\mathrm{min}}(A) ]^{1/2} \;\;\;\;\; \because \; A$ は対称行列 : 冒頭の過去記事(レイリー商)定理 4.2.2

(1.8) $\;\;\; W_{\mathrm{max}}(\mathcal{E}) = \sup_{\left\| q \right\|_2 = 1} W(\mathcal{E},q) \;\;\; \because$ (1.3)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 2 [ \lambda_{\mathrm{max}}(A) ]^{1/2} \;\;\; \because W_{\mathrm{min}}(\mathcal{E})$ と同様に式変形する

条件数は以下となります．行列 $A$ の条件数を $\kappa \left( A \right)$ とします．

(1.9) $\;\;\; \mathrm{cond}(\mathcal{E}) = \frac{ \left( W_{\mathrm{max}}(C) \right)^2}{ \left( W_{\mathrm{min}}(C) \right)^2} \;\;\; \because$ (1.4)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{ \lambda_{\mathrm{max}}(A) }{ \lambda_{\mathrm{min}}(A) } \;\;\; \because$ (1.7)(1.8)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \kappa \left( A \right)$

このように，楕円 $\mathcal{E}$ の条件数は元の行列の条件数と同じになります．(1.5)の行列が $A^{-1}$ であることと冒頭の過去記事(逆行列の固有値)事実.より，楕円 $\mathcal{E}$ の最短半径は $(\lambda_{\mathrm{min}})^{1/2}$ ，最長半径は $(\lambda_{\mathrm{max}})^{1/2}$ です(文献[5]にあります)．したがって，楕円の条件数は最短半径と最長半径の比の二乗を意味していることがわかります．
'--------------------------------------------------------------------------------------------------------------------------------------------

以下の事実を示します．
'--------------------------------------------------------------------------------------------------------------------------------------------
事実.
$n \times n$ 行列 $A$ は対称行列で正定値とする．その固有値はすべて正である．以下の二つの楕円を考える．

$\;\;\; \mathcal{E} = \{ x \; | \; (x - x_0)^T A^{-1} (x - x_0) \leq 1 \}$
$\;\;\; \mathcal{E_{-1}} = \{ x \; | \; (x - x_0)^T A (x - x_0) \leq 1 \}$

このとき以下が成り立つ．

$\;\;\; \mathrm{cond}(\mathcal{E}) = \frac{ \lambda_{\mathrm{max}}(A) }{ \lambda_{\mathrm{min}}(A) } = \kappa(A) = \kappa(A^{-1} ) = \frac{ \lambda_{\mathrm{max}}(A^{-1}) }{ \lambda_{\mathrm{min}}(A^{-1}) } = \mathrm{cond}(\mathcal{E_{-1}})$

証明.
行列 $A$ の固有値について以下が成り立つ．

$\;\;\;\;\;\;\;\;\;\; 0 \lt \lambda_\mathrm{min}(A) = \lambda_1(A) \le \lambda_2(A) \le \cdots \le \lambda_{n-1}(A) \le \lambda_n(A) = \lambda_\mathrm{max}(A)$

${\displaystyle \;\;\;\;\;\; \Leftrightarrow 0 \lt \frac{1}{ \lambda_\mathrm{max}(A)} = \frac{1}{\lambda_{n}(A)} \le \frac{1}{\lambda_{n-1}(A)} \le \cdots \le \frac{1}{\lambda_{2}(A)} \le \frac{1}{\lambda_{1}(A)} = \frac{1}{\lambda_\mathrm{min}(A)} }$

これと冒頭の過去記事(逆行列の固有値)事実.より以下を得る．

$\;\;\; \lambda_\mathrm{max}(A^{-1}) = 1 / \lambda_\mathrm{min}(A) \;\;\;$ (※)

$\;\;\; \lambda_\mathrm{min}(A^{-1}) = 1 / \lambda_\mathrm{max}(A) \;\;\;$ (※)

したがって条件数についての結果を得る．

$\;\;\; \kappa(A) = \frac{ \lambda_{\mathrm{max}}(A) }{ \lambda_{\mathrm{min}}(A) }$

$\;\;\;\;\;\;\;\;\;\;\;\; = \frac{ 1 / \lambda_{\mathrm{min}}(A^{-1}) }{ 1 / \lambda_{\mathrm{max}}(A^{-1}) } \;\;\; \because$ (※)

$\;\;\;\;\;\;\;\;\;\;\;\; = \frac{ \lambda_{\mathrm{max}}(A^{-1}) }{ \lambda_{\mathrm{min}}(A^{-1}) }$

$\;\;\;\;\;\;\;\;\;\;\;\; = \kappa(A^{-1})$

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

以上，凸集合の条件数について考えてみました．幾何的なイメージができるようになってきたと思います．

参考文献
[1] Boyd, S., and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.
[2] Wikipedia Convex setのページ https://en.wikipedia.org/wiki/Convex_set
[3] Wikipedia Norm (mathematics)のページ https://en.wikipedia.org/wiki/Norm_(mathematics)
[4] Wikipedia Condition numberのページ https://en.wikipedia.org/wiki/Condition_number
[5] Stanford University Sanjay Lall先生のノート http://ee263.stanford.edu/lectures/ellipsoids.pdf
[6] Northeastern University Laurent Lessard先生のノート https://laurentlessard.com/teaching/cs524/slides/11%20-%20quadratic%20forms%20and%20ellipsoids.pdf
[7] Core Concept Technologies Inc. のブログ https://recruit.cct-inc.co.jp/tecblog/machine-learning/condition-number/