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

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

係数行列が半正定値の二次関数が最小値をもつための必要十分条件は勾配が零ベクトルであることを証明する

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

分散共分散行列(と相関行列)は半正定値であることを証明する - エンジニアを目指す浪人のブログ

いくつかの行列の公式を証明するその1 - エンジニアを目指す浪人のブログ


本記事は以下の過去記事の内容を既知とすると考えやすいです.

係数行列が対称行列の二次関数が凸関数(あるいは狭義凸関数)であるための必要十分条件はその係数行列が半正定値(あるいは正定値)であることを証明する - エンジニアを目指す浪人のブログ


応用上よく使われる関数に,係数行列が半正定値(positive semidefinite)である(ベクトル値)二次関数(quadratic function)があります.このような二次関数が最小値をもつときの条件と勾配(gradient)の関係についてモヤモヤしてしまったので,調べてまとめることにしました.


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

{\displaystyle \;\;\; \mathbb{R}^{n}  \;\;\;\;\;\;\;\;  } {\displaystyle \mathbb{R} } の要素を要素にもつ {\displaystyle n } 次元ベクトルの集合
{\displaystyle \;\;\; \mathbb{R}^{n \times n}  \;\;\;\; } {\displaystyle \mathbb{R} } の要素を要素にもつ {\displaystyle n \times n } 行列の集合
{\displaystyle \;\;\; x \;\;\;\;\;\;\;\;\;\; } {\displaystyle n } 次元ベクトル
{\displaystyle \;\;\; c \;\;\;\;\;\;\;\;\;\; } {\displaystyle n } 次元ベクトル
{\displaystyle \;\;\; Q \;\;\;\;\;\;\;\;\; } {\displaystyle n \times n } 行列


半正定値の定義は冒頭の過去記事(分散共分散行列)定義 4.1.11.にあります.

関数 {\displaystyle f: \mathbb{R}^n \to \mathbb{R} } の勾配の定義は文献[2]にあります.

転置行列についての以下の性質は文献[3]にあります.

{\displaystyle \;\;\; \left( A_1 A_2 A_3 \right)^T = \left( A_3 \right)^T  \left( A_2 \right)^T \left( A_1 \right)^T }


冒頭の過去記事(いくつかの行列の公式)事実2.(2.1)を再掲します.

(0.1){\displaystyle \;\;\; \frac{ \partial }{ \partial x }  x^T Q x = 2 Q x \;\;\;\;\;\; \mathrm{if} \;\; Q =  Q^T }

冒頭の過去記事(いくつかの行列の公式)事実3.(3.1)を再掲します.

(0.2){\displaystyle \;\;\; \frac{ \partial }{ \partial x }  c^T x = c   }


{\displaystyle Q = Q^T } のとき関数 {\displaystyle f(x) = (1/2) x^T Q x + c^T x } の勾配は以下です.

{\displaystyle \nabla f(x) =  \begin{bmatrix} \frac{ \partial f(x) }{ \partial x_1 }  \\ \frac{ \partial f(x) }{ \partial x_2 } \\ \vdots \\ \frac{ \partial f(x) }{ \partial x_n }  \end{bmatrix}  =  \begin{bmatrix} \frac{ \partial }{ \partial x_1 } \left( \frac{1}{2} x^T Q x + c^T x \right) \\ \frac{ \partial }{ \partial x_2 } \left( \frac{1}{2} x^T Q x + c^T x \right) \\ \vdots \\ \frac{ \partial }{ \partial x_n } \left( \frac{1}{2} x^T Q x + c^T x \right) \end{bmatrix} = \begin{bmatrix} \frac{1}{2} \frac{ \partial }{ \partial x_1 } \left( x^T Q x  \right) + \frac{ \partial }{ \partial x_1 } \left( c^T x \right) \\ \frac{1}{2} \frac{ \partial }{ \partial x_2 } \left( x^T Q x  \right) + \frac{ \partial }{ \partial x_2 } \left( c^T x \right) \\ \vdots \\ \frac{1}{2} \frac{ \partial }{ \partial x_n } \left( x^T Q x  \right) + \frac{ \partial }{ \partial x_n } \left( c^T x \right) \end{bmatrix} }

{\displaystyle \;\;\;\;\;\;\;\;\;\; = \frac{1}{2} \begin{bmatrix} \frac{ \partial }{ \partial x_1 } \left( x^T Q x  \right) \\ \frac{ \partial }{ \partial x_2 } \left( x^T Q x  \right)  \\ \vdots \\ \frac{ \partial }{ \partial x_n } \left( x^T Q x  \right) \end{bmatrix} + \begin{bmatrix} \frac{ \partial }{ \partial x_1 } \left( c^T x \right) \\ \frac{ \partial }{ \partial x_2 } \left( c^T x \right) \\ \vdots \\ \frac{ \partial }{ \partial x_n } \left( c^T x \right) \end{bmatrix} = \frac{1}{2} \frac{ \partial }{ \partial x }  x^T Q x + \frac{ \partial }{ \partial x }  c^T x  }

{\displaystyle \;\;\;\;\;\;\;\;\;\; = Q x + c \;\;\; \because } (0.1)(0.2)


以上の設定のもとで,本記事の目的に進みます.以下の定理と証明は,文献[1]Theorem 3をほぼ引用したものです.

'--------------------------------------------------------------------------------------------------------------------------------------------
定理3.

{\displaystyle x \in \mathbb{R}^n, \ Q \in \mathbb{R}^{n \times n}, \ Q = Q^T, \; Q } は半正定値であるとする.関数 {\displaystyle f(x) = \frac{1}{2} x^T Q x + c^T x }{\displaystyle x = x^* } で最小値 {\displaystyle f(x^*) } をもつための必要十分条件は,{\displaystyle f(x)} の勾配 {\displaystyle \nabla f(x)}{\displaystyle x = x^* } で零ベクトルとなること,すなわち以下の方程式が成り立つことである.

{\displaystyle \;\;\; \nabla f(x^*) =  Q x^* + c = 0 }


証明.

{\displaystyle x^* }{\displaystyle  Q x^* + c = 0 } をみたすとする.任意の {\displaystyle x \in \mathbb{R}^n } について以下が成り立つ.

{\displaystyle f(x) - c^T x }

{\displaystyle = f( x^* + (x - x^*) ) - c^T ( x^* + (x - x^*) ) }

{\displaystyle = \frac{1}{2} \left( x^* + (x - x^*) \right)^T Q \left( x^* + (x - x^*) \right) }

{\displaystyle = \frac{1}{2} \left( x^* + (x - x^*) \right)^T  \left( Q x^* + Q (x - x^*) \right) }

{\displaystyle = \frac{1}{2} \left[ (x^*)^T Q x^* + (x^*)^T Q (x - x^*) + (x - x^*)^T Q x^* + (x - x^*)^T Q (x - x^*) \right] }

{\displaystyle = \frac{1}{2} \left[ (x^*)^T Q x^* + \left( (x^*)^T Q (x - x^*) \right)^T + (x - x^*)^T Q x^* + (x - x^*)^T Q (x - x^*) \right] }

{\displaystyle = \frac{1}{2} \left[ (x^*)^T Q x^* + (x - x^*)^T Q^T ((x^*)^T)^T + (x - x^*)^T Q x^* + (x - x^*)^T Q (x - x^*) \right] }

{\displaystyle = \frac{1}{2} \left[ (x^*)^T Q x^* + (x - x^*)^T Q x^* + (x - x^*)^T Q x^* + (x - x^*)^T Q (x - x^*) \right] }

{\displaystyle = \frac{1}{2} \left[ (x^*)^T Q x^* + 2(x - x^*)^T Q x^* + (x - x^*)^T Q (x - x^*) \right]  }

{\displaystyle = \frac{1}{2} (x^*)^T Q x^* + (x - x^*)^T Q x^* + \frac{1}{2} (x - x^*)^T Q (x - x^*) }

{\displaystyle \Leftrightarrow f(x) }

{\displaystyle  = f( x^* - ( x - x^* ) )  }

{\displaystyle  = \frac{1}{2} (x^*)^T Q x^* + (x - x^*)^T Q x^* + \frac{1}{2} (x - x^*)^T Q (x - x^*) + c^T ( x^* + (x - x^*) ) }

{\displaystyle  = \frac{1}{2} (x^*)^T Q x^* + (x - x^*)^T Q x^* + \frac{1}{2} (x - x^*)^T Q (x - x^*) + c^T x^* +c^T (x - x^*) }

{\displaystyle  = \frac{1}{2} (x^*)^T Q x^* + (x - x^*)^T Q x^* + \frac{1}{2} (x - x^*)^T Q (x - x^*) + c^T x^* + (x - x^*)^T c }

{\displaystyle  = \frac{1}{2} (x^*)^T Q x^* + (x - x^*)^T Q x^* + (x - x^*)^T c + \frac{1}{2} (x - x^*)^T Q (x - x^*) + c^T x^* }

{\displaystyle  = \frac{1}{2} (x^*)^T Q x^* + (x - x^*)^T \left( Q x^* + c \right) + \frac{1}{2} (x - x^*)^T Q (x - x^*) + c^T x^* }

{\displaystyle  = \frac{1}{2} (x^*)^T Q x^* + (x - x^*)^T 0 + \frac{1}{2} (x - x^*)^T Q (x - x^*) + c^T x^* \;\;\; \because } 仮定

{\displaystyle  = \frac{1}{2} (x^*)^T Q x^* + \frac{1}{2} (x - x^*)^T Q (x - x^*) + c^T x^* }

{\displaystyle  = \frac{1}{2} (x^*)^T Q x^* + c^T x^* + \frac{1}{2} (x - x^*)^T Q (x - x^*) }

{\displaystyle  = f( x^* ) + \frac{1}{2} (x - x^*)^T Q (x - x^*) }

{\displaystyle  \ge f( x^* ) \;\;\; \because \; Q } は半正定値

したがって {\displaystyle x^* }{\displaystyle f(x) } を最小化する.


逆を示す.{\displaystyle x^* }{\displaystyle f(x) } を最小化するとする.いま {\displaystyle d=\nabla f(x^*) =  Q x^* + c } とおき {\displaystyle d \neq 0 } を仮定すると任意の {\displaystyle \alpha \in \mathbb{R} } について以下が成り立つ.

{\displaystyle f(x^* + \alpha d )  }

{\displaystyle = \frac{1}{2} (x^* + \alpha d)^T Q (x^* + \alpha d) + c^T (x^* + \alpha d) }

{\displaystyle = \frac{1}{2} (x^* + \alpha d)^T ( Q x^* + \alpha Q d) + c^T (x^* + \alpha d) }

{\displaystyle = \frac{1}{2} \left[\ (x^*)^T Q x^* + (x^*)^T (\alpha Q d) + (\alpha d)^T Q x^* + (\alpha d)^T Q (\alpha d) \right] + c^T (x^* + \alpha d) }

{\displaystyle = \frac{1}{2} \left[\ (x^*)^T Q x^* + \alpha (x^*)^T Q d + \alpha d^T Q x^* + \alpha^2 d^T Q d \right] + c^T (x^* + \alpha d) }

{\displaystyle = \frac{1}{2} \left[\ (x^*)^T Q x^* + \left( \alpha (x^*)^T Q d \right)^T + \alpha d^T Q x^* + \alpha^2 d^T Q d \right] + c^T (x^* + \alpha d) }

{\displaystyle = \frac{1}{2} \left[\ (x^*)^T Q x^* + \alpha d^T Q^T ((x^*)^T)^T + \alpha d^T Q x^* + \alpha^2 d^T Q d \right] + c^T (x^* + \alpha d) }

{\displaystyle = \frac{1}{2} \left[\ (x^*)^T Q x^* + \alpha d^T Q x^* + \alpha d^T Q x^* + \alpha^2 d^T Q d \right] + c^T (x^* + \alpha d) }

{\displaystyle = \frac{1}{2} \left[\ (x^*)^T Q x^* + 2 \alpha d^T Q x^* + \alpha^2 d^T Q d \right] + c^T (x^* + \alpha d) }

{\displaystyle = \frac{1}{2} (x^*)^T Q x^* + \alpha d^T Q x^* + \frac{1}{2} \alpha^2 d^T Q d + c^T (x^* + \alpha d) }

{\displaystyle = \frac{1}{2} (x^*)^T Q x^* + \alpha d^T Q x^* + \frac{1}{2} \alpha^2 d^T Q d + c^T x^* + \alpha c^T d }

{\displaystyle = \frac{1}{2} (x^*)^T Q x^* + \alpha d^T Q x^* + \frac{1}{2} \alpha^2 d^T Q d + c^T x^* + \alpha d^T c }

{\displaystyle = \frac{1}{2} (x^*)^T Q x^* + c^T x^* + \alpha d^T Q x^* + \alpha d^T c + \frac{1}{2} \alpha^2 d^T Q d }

{\displaystyle = \frac{1}{2} (x^*)^T Q x^* + c^T x^* + \alpha d^T  \left( Q x^* + c \right) + \frac{1}{2} \alpha^2 d^T Q d }

{\displaystyle = \frac{1}{2} (x^*)^T Q x^* + c^T x^* + \alpha d^T d + \frac{1}{2} \alpha^2 d^T Q d \;\;\; \because } 仮定

{\displaystyle = f(x^*) + \alpha d^T d + \frac{1}{2} \alpha^2 d^T Q d  \;\;\;\;\;\; }

ここで {\displaystyle | \alpha | } が十分小さい {\displaystyle \alpha \lt 0 } をとると {\displaystyle d^T d \gt 0 } より {\displaystyle \alpha d^T d + \frac{1}{2} \alpha^2 d^T Q d \lt 0  } なので {\displaystyle f(x^* + \alpha d) \lt f(x^*) } を得ることができ,{\displaystyle x^* }{\displaystyle f(x) } を最小化することに矛盾である.したがって {\displaystyle d = \nabla f(x^*) =  Q x^* + c = 0 } でなければならない.(証明終わり)

'--------------------------------------------------------------------------------------------------------------------------------------------


以上,係数行列が半正定値の二次関数が最小値をもつための必要十分条件は勾配が零ベクトルであることを証明しました.



参考文献
[1] Massachusetts Institute of Technology Robert M. Freund先生のノート https://ocw.mit.edu/courses/sloan-school-of-management/15-084j-nonlinear-programming-spring-2004/lecture-notes/lec4_quad_form.pdf
[2] Stanford University Jon Dattorro先生のノート https://ccrma.stanford.edu/~dattorro/matrixcalc.pdf
[3] Wikipedia Transpose のページ https://en.wikipedia.org/wiki/Transpose