係数行列が対称行列の二次関数が凸関数(あるいは狭義凸関数)であるための必要十分条件はその係数行列が半正定値(あるいは正定値)であることを証明する

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

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

応用上よく使われる関数に，凸(convex)(あるいは狭義凸(strictly convex))である(ベクトル値)二次関数(quadratic function)があります．二次関数が凸となる条件についてモヤモヤしてしまったので，調べてまとめることにしました．

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

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

正定値(positive definite)，半正定値(positive semidefinite)の定義は冒頭の過去記事定義 4.1.11.にあります．

凸関数，狭義凸関数の定義は文献[3]にあります．

転置行列についての以下の性質は文献[4]にあります．
$\;\;\; \left( A_1 A_2 A_3 \right)^T = \left( A_3 \right)^T \left( A_2 \right)^T \left( A_1 \right)^T$

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

'--------------------------------------------------------------------------------------------------------------------------------------------
定理1.

$x \in \mathbb{R}^n, \ Q \in \mathbb{R}^{n \times n}, \ Q = Q^T$ とする．関数 $f(x) = \frac{1}{2} x^T Q x + c^T x$ が凸であるための必要十分条件は $Q$ が半正定値であることである．

証明.

$Q$ は半正定値でないとする．このとき $r^T Q r \lt 0$ となるある $r \in \mathbb{R}^n$ が存在する．以下の集合 $\mathcal{S}$ を考える．

$\;\;\; \mathcal{S} = \{ x \in \mathbb{R}^n | \ x = \theta r, \;\; \theta \in \mathbb{R}, \;\; r \in \mathbb{R}^n \;\; \mathrm{s.t.} \;\; r^T Q r \lt 0 \} \subset \mathbb{R}^n$

$x \in \mathcal{S}$ について $f(x) = f(\theta r) = (1/2) \theta^2 r^T Q r + \theta c^T r$ であり， $r$ を固定すればこれは $\theta$ の関数であるから $g(\theta) = (1/2) \left( r^T Q r \right) \theta^2 + \left( c^T r \right) \theta$ とおける．いま $r^T Q r \lt 0$ であるから $g(\cdot)$ は $\theta \in \mathbb{R}^n$ についての狭義凹であり，すなわち $x \in \mathcal{S}$ について $f(\cdot)$ は狭義凹になりうるので $\mathcal{S}$ 上では $f(\cdot)$ は凸ではない．

したがって $Q$ が半正定値でないとき $f(\cdot)$ は凸ではないので， $f(\cdot)$ が凸のとき $Q$ は半正定値である．

逆を示す． $Q$ は半正定値であるとする． $\forall x,y \in \mathbb{R}^n ,\ \forall \lambda \in [ 0,1 ]$ について以下が成り立つ．

$f \left( \lambda x + ( 1 - \lambda ) y \right)$

$= f \left( \lambda x + y - \lambda y \right)$

$= f \left( y + \lambda( x - y ) \right)$

$= \frac{1}{2} \left( y + \lambda( x - y ) \right)^T Q \left( y + \lambda( x - y ) \right) + c^T \left( y + \lambda( x - y ) \right)$

$= \frac{1}{2} \left( y + \lambda( x - y ) \right)^T \left( Q y + Q \lambda( x - y ) \right) + c^T \left( y + \lambda( x - y ) \right)$

$= \frac{1}{2} \left[\ y^T Q y + y^T Q \lambda( x - y ) + \lambda( x - y )^T Q y + \lambda( x - y )^T Q \lambda( x - y ) \right] + c^T \left( y + \lambda( x - y ) \right)$

$= \frac{1}{2} \left[\ y^T Q y + \lambda y^T Q ( x - y ) + \lambda ( x - y )^T Q y + \lambda^2 ( x - y )^T Q ( x - y ) \right] + c^T \left( y + \lambda( x - y ) \right)$

$= \frac{1}{2} \left[\ y^T Q y + \left( \lambda y^T Q ( x - y ) \right)^T + \lambda ( x - y )^T Q y + \lambda^2 ( x - y )^T Q ( x - y ) \right] + c^T \left( y + \lambda( x - y ) \right)$

$= \frac{1}{2} \left[\ y^T Q y + \lambda ( x - y )^T Q^T (y^T)^T + \lambda ( x - y )^T Q y + \lambda^2 ( x - y )^T Q ( x - y ) \right] + c^T \left( y + \lambda( x - y ) \right)$

$= \frac{1}{2} \left[\ y^T Q y + \lambda ( x - y )^T Q y + \lambda ( x - y )^T Q y + \lambda^2 ( x - y )^T Q ( x - y ) \right] + c^T \left( y + \lambda( x - y ) \right)$

$= \frac{1}{2} \left[\ y^T Q y + 2 \lambda ( x - y )^T Q y + \lambda^2 ( x - y )^T Q ( x - y ) \right] + c^T \left( y + \lambda( x - y ) \right)$

$= \frac{1}{2} y^T Q y + \lambda ( x - y )^T Q y + \frac{1}{2} \lambda^2 ( x - y )^T Q ( x - y ) + c^T \left( y + \lambda( x - y ) \right)$

$= \frac{1}{2} y^T Q y + \lambda ( x - y )^T Q y + \frac{1}{2} \lambda^2 ( x - y )^T Q ( x - y ) + c^T y + \lambda c^T ( x - y )$

$= \frac{1}{2} y^T Q y + \lambda ( x - y )^T Q y + \frac{1}{2} \lambda^2 ( x - y )^T Q ( x - y ) + c^T y + \lambda c^T x - \lambda c^T y$

$= \frac{1}{2} y^T Q y + \lambda ( x - y )^T Q y + \frac{1}{2} \lambda^2 ( x - y )^T Q ( x - y ) + \lambda c^T x + ( 1 - \lambda ) c^T y$

$\le \frac{1}{2} y^T Q y + \lambda ( x - y )^T Q y + \frac{1}{2} \lambda ( x - y )^T Q ( x - y ) + \lambda c^T x + ( 1 - \lambda ) c^T y \;\;\; \because \; \lambda \in [ 0,1 ]$

$= \frac{1}{2} y^T Q y + \lambda ( x - y )^T Q y + \frac{1}{2} \lambda ( x - y )^T \left( Q x - Q y \right) + \lambda c^T x + ( 1 - \lambda ) c^T y$

$= \frac{1}{2} y^T Q y + \lambda ( x - y )^T Q y + \frac{1}{2} \lambda \left( x^T Q x - x^T Q y - y^T Q x + y^T Q y \right) + \lambda c^T x + ( 1 - \lambda ) c^T y$

$= \frac{1}{2} y^T Q y + \lambda x^T Q y - \lambda y^T Q y + \frac{1}{2} \lambda \left( x^T Q x - x^T Q y - y^T Q x + y^T Q y \right) + \lambda c^T x + ( 1 - \lambda ) c^T y$

$= \frac{1}{2} \lambda x^T Q x + \frac{1}{2} (1 - \lambda ) y^T Q y + \lambda x^T Q y + \frac{1}{2} \lambda \left( - x^T Q y - y^T Q x \right) + \lambda c^T x + ( 1 - \lambda ) c^T y$

$= \frac{1}{2} \lambda x^T Q x + \frac{1}{2} (1 - \lambda ) y^T Q y + \lambda x^T Q y + \frac{1}{2} \lambda \left( - x^T Q y - ( y^T Q x )^T \right) + \lambda c^T x + ( 1 - \lambda ) c^T y$

$= \frac{1}{2} \lambda x^T Q x + \frac{1}{2} (1 - \lambda ) y^T Q y + \lambda x^T Q y + \frac{1}{2} \lambda \left( - x^T Q y - x^T Q^T (y^T)^T \right) + \lambda c^T x + ( 1 - \lambda ) c^T y$

$= \frac{1}{2} \lambda x^T Q x + \frac{1}{2} (1 - \lambda ) y^T Q y + \lambda x^T Q y + \frac{1}{2} \lambda \left( - x^T Q y - x^T Q y \right) + \lambda c^T x + ( 1 - \lambda ) c^T y$

$= \frac{1}{2} \lambda x^T Q x + \frac{1}{2} (1 - \lambda ) y^T Q y + \lambda c^T x + ( 1 - \lambda ) c^T y$

$= \frac{1}{2} \lambda x^T Q x + \lambda c^T x + \frac{1}{2} (1 - \lambda ) y^T Q y + ( 1 - \lambda ) c^T y$

$= \lambda \left[ \frac{1}{2} x^T Q x + c^T x \right] + (1 - \lambda ) \left[ \frac{1}{2} y^T Q y + c^T y \right]$

$= \lambda f(x) + (1 - \lambda ) f(y)$

したがって $Q$ が半正定値のとき $f(\cdot)$ は凸である．

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

以下の系は，文献[1]Corollary 2を参考にしています．

'--------------------------------------------------------------------------------------------------------------------------------------------
系2.

$f(x)$ が狭義凸であるための必要十分条件は $Q$ が正定値であることである．

証明.

定理1.の証明.では集合 $\{ r \ | \ r^T Q r \lt 0 \}$ を用いたが，ここでは集合 $\{ r \ | \ r^T Q r \le 0 \}$ を考えることになる．以下の関係がある．

$\{ r \ | \ r^T Q r \lt 0 \} \subset \{ r \ | \ r^T Q r \le 0 \}$

また，任意の関数は狭義凸ならば凸であるので，凸でないならば狭義凸でない．

したがって， $Q$ は正定値でない $\Rightarrow f(\cdot)$ は狭義凸ではない，は定理1.の証明.と同様に示せる．

逆についても， $Q$ を正定値と仮定すれば定理1.の証明.と同様に示せる．ただし $\forall \lambda \in ( 0,1 )$ について考えるので，式変形中の $\le$ を $\lt$ におきかえ，狭義凸であることを示すことになる．

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

以上，係数行列が対称行列の二次関数が凸関数(あるいは狭義凸関数)であるための必要十分条件はその係数行列が半正定値(あるいは正定値)であることを証明しました．

参考文献
[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] University of Delaware Thomas S. Angell先生のノート http://www.math.udel.edu/~angell/Opt/conv_fcn.pdf
[3] Wikipedia Convex function のページ https://en.wikipedia.org/wiki/Convex_function
[4] Wikipedia Transpose のページ https://en.wikipedia.org/wiki/Transpose