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

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

制約付き最小二乗法の基礎をまとめる

数学 数理最適化

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

最小二乗法の基礎をまとめる - エンジニアを目指す浪人のブログ

多目的最小二乗法の基礎をまとめる - エンジニアを目指す浪人のブログ


勉強を進めていて，制約付き最小二乗法(constrained least squares method)について知りました．応用でよく使われているようなので，その内容をまとめておくことにしました．Boyd and Vandenberghe(2018)の16章1,2節をベースにしています．

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

目次

{\displaystyle \; } 0. 準備
{\displaystyle \; } 1. 制約付き最小二乗問題
{\displaystyle \;\;\; } 1.1. 最小ノルム問題
{\displaystyle \; } 2. 解
{\displaystyle \;\;\; } 2.1. KKT方程式
{\displaystyle \;\;\; } 2.2. 制約付き最小二乗問題のただ一つの解


[ 0. 準備 ]

記号を準備します．

{\displaystyle \;\;\; \mathbf{R}^{n} \;\;\;\;\;\;\;\; } {\displaystyle \mathbf{R} } の要素を要素にもつ {\displaystyle n } 次元ベクトルの集合
{\displaystyle \;\;\; I \;\;\;\;\;\;\;\;\;\; } {\displaystyle n \times n } 単位行列
{\displaystyle \;\;\; x \;\;\;\;\;\;\;\;\;\; } {\displaystyle n } 次元ベクトル ( {\displaystyle x = [ x_1 \ \cdots \ x_n ]^T } )
{\displaystyle \;\;\; z \;\;\;\;\;\;\;\;\;\; } {\displaystyle p } 次元ベクトル
{\displaystyle \;\;\; A \;\;\;\;\;\;\;\;\;\; } {\displaystyle m \times n } 行列
{\displaystyle \;\;\; C \;\;\;\;\;\;\;\;\;\; } {\displaystyle p \times n } 行列
{\displaystyle \;\;\; b \;\;\;\;\;\;\;\;\;\; } {\displaystyle m } 次元ベクトル
{\displaystyle \;\;\; d \;\;\;\;\;\;\;\;\;\; } {\displaystyle p } 次元ベクトル ( {\displaystyle d = [ d_1 \ \cdots \ d_p ]^T } )
{\displaystyle \;\;\; \lambda \;\;\;\;\;\;\;\;\;\; } 正の実数

{\displaystyle \langle \cdot , \cdot \rangle \;\;\; } 通常の内積 {\displaystyle \langle x,y \rangle = y^T x \;\;\; } (性質は文献[2]にあります)
{\displaystyle \left\| \cdot \right\| \;\;\; } (ユークリッド)ノルム {\displaystyle \left\| x \right\| = \sqrt{ x^T x } = \sqrt{ x_1^2 + \cdots + x_n^2 } \;\;\; } (性質は文献[3]にあります)


本記事では以下を仮定します．

仮定.
(0.1) {\displaystyle \; C } は線形独立な行をもつ．

(0.2) {\displaystyle \; \begin{bmatrix} A \\ C \end{bmatrix} } は線形独立な列をもつ．

これより {\displaystyle C } は横長の行列あるいは正方行列( {\displaystyle \Leftrightarrow [ p \le n ] } )，{\displaystyle \; \begin{bmatrix} A \\ C \end{bmatrix} } は縦長の行列あるいは正方行列( {\displaystyle \Leftrightarrow [ m + p \ge n ] } )であることが必要です．冒頭の過去記事(最小二乗法)仮定.の一般化になっています．


[ 1. 制約付き最小二乗問題 ]

制約付き最小二乗問題のベースである最小二乗問題(least squares problem)は，目的関数 {\displaystyle \left\| Ax - b \right\|^2 } を最小にする {\displaystyle \hat{x} } を探索する問題です．冒頭の過去記事(最小二乗法)にあります．これに連立一次方程式 {\displaystyle C x = d } をみたすという制約を加えたものを，線形制約付き最小二乗問題(linearly constrained least squares problem)あるいは制約付き最小二乗問題(constrained least squares problem)といいます．

(1.1)
{\displaystyle \;\;\; \mathrm{minimize} \;\;\;\; \left\| Ax - b \right\|^2 }
{\displaystyle \;\;\; \mathrm{subject \; to} \;\;\ Cx=d }


行列 {\displaystyle A,\ C } とベクトル {\displaystyle b, \ d } は問題(1.1)のデータ(data)です．{\displaystyle \left\| Ax - b \right\|^2 } を目的関数(objective function)，線形方程式系 {\displaystyle Cx=d } を問題の制約(constraints)といいます．それらは {\displaystyle p} 本のスカラー方程式で書くことができます．{\displaystyle c_i^T } は {\displaystyle C } の {\displaystyle i } 番目の行です．

{\displaystyle \;\;\; c_i^T x = d_i, \;\;\; i=1,\ldots,p }

{\displaystyle Cx = d } をみたすとき {\displaystyle x } は実行可能(feasible)といいます．任意の実行可能な {\displaystyle x } について {\displaystyle \left\| A \hat{x} - b \right\|^2 \le \left\| A x - b \right\|^2 } となるとき，{\displaystyle \hat{x} } は制約付き最小二乗問題(1.1)の最適点(optimal point)あるいは解(solution)といいます．

制約付き最小二乗問題は連立一次方程式を解くという問題( {\displaystyle Cx=d } をみたす {\displaystyle x } を探索する問題)と最小二乗問題( {\displaystyle \left\| A x - b \right\|^2 } を最小化する {\displaystyle x } を探索する問題)を併せたものです．実際にそれらはそれぞれ制約付き最小二乗問題(1.1)の特別な場合と考えることができます．


制約付き最小二乗問題は冒頭の過去記事(多目的最小二乗法)にある多目的最小二乗問題において極限をとったものと考えることもできます．粗い議論になりますが，1つ目の目的関数 {\displaystyle \left\| A x - b \right\|^2 } と2つ目の目的関数 {\displaystyle \left\| C x - d \right\|^2 } の加重和をとった加重和目的関数において後者の重みを無限大にすると，{\displaystyle x } は {\displaystyle C x - d = 0 } をみたさなければなりません．以下の(加重和)目的関数において非常に大きな {\displaystyle \lambda } とすることに相当します．

{\displaystyle \;\;\; \left\| A x - b \right\|^2 + \lambda \left\| C x - d \right\|^2 }


[ 1.1. 最小ノルム問題 ]

制約付き最小二乗問題(1.1)の重要な場合は {\displaystyle A=I,b=0} として以下です．

(1.1.1)
{\displaystyle \;\;\; \mathrm{minimize} \;\;\;\; \left\| x \right\|^2 }
{\displaystyle \;\;\; \mathrm{subject \; to} \;\;\ Cx=d }

これは連立一次方程式 {\displaystyle Cx=d } をみたす最小のノルムをもつベクトルを探索する問題であり，最小ノルム問題(least norm problem)(minimum-norm problem)といいます．



[ 2. 解 ]
[ 2.1. KKT方程式 ]

以下の方程式系をKKT方程式(KKT equations)といいます．冒頭の過去記事(最小二乗法)にある正規方程式(2.1.1)の拡張です．この方程式をみたす解を {\displaystyle (x,z) = (\hat{x},\hat{z}) } とします．

(2.1.1){\displaystyle \;\;\; \begin{bmatrix} 2 A^T A & C^T \\ C & 0 \end{bmatrix} \begin{bmatrix} x \\ z \end{bmatrix} = \begin{bmatrix} 2 A^T b \\ d \end{bmatrix} \;\;\; ( (n + p) \times (n + p) ) \times ( (n + p) \times 1 ) = (n + p) \times 1 }

KKT方程式(2.1.1)の係数行列はKKT行列(KKT matrix)といいます．以下の事実が成り立ちます．

事実1.

KKT行列が正則 {\displaystyle \; \Longleftrightarrow \; } 仮定.(0.1)(0.2)が成り立つ

証明.

({\displaystyle \Longleftarrow })
KKT行列が正則でないと仮定する．このことは以下の方程式をみたす零ベクトルでないベクトル {\displaystyle (\bar{x},\bar{z}) } が存在することと同値である．

(※){\displaystyle \;\;\; \begin{bmatrix} 2 A^T A & C^T \\ C & 0 \end{bmatrix} \begin{bmatrix} \bar{x} \\ \bar{z} \end{bmatrix} = 0 }

(※)の上部の方程式について以下を得る．

{\displaystyle \;\;\; 2 A^T A \bar{x} + C^T \bar{z} = 0 }

{\displaystyle \;\;\; \Rightarrow 2 \; \bar{x}^T A^T A \bar{x} + \bar{x}^T C^T \bar{z} = 0 }
{\displaystyle \;\;\; \Leftrightarrow 2 \left\| A \bar{x} \right\|^2 + \bar{x}^T C^T \bar{z} = 0 }
{\displaystyle \;\;\; \Leftrightarrow 2 \left\| A \bar{x} \right\|^2 = 0 \;\;\;\;\; \because \; } (※)の下部の方程式 {\displaystyle C \bar{x} = 0 \Leftrightarrow \bar{x}^T C^T = 0 }
{\displaystyle \;\;\; \Leftrightarrow A \bar{x} = 0 }
{\displaystyle \;\;\; \Leftrightarrow \begin{bmatrix} A \\ C \end{bmatrix} \bar{x} = 0 \;\;\;\;\;\; \because \; } (※)の下部の方程式 {\displaystyle C \bar{x} = 0 }
{\displaystyle \;\;\; \Rightarrow \bar{x} = 0 \;\;\;\;\;\; \because } 仮定.(0.2)

再び(※)の上部の方程式について以下を得る．

{\displaystyle C^T \bar{z} = 0 \;\;\;\;\;\;\;\; \because \bar{x} = 0 }
{\displaystyle \;\;\; \Rightarrow \bar{z} = 0 \;\;\;\;\;\; \because } 仮定.(0.1)より {\displaystyle C^T } は線形独立な列をもつ．

したがって {\displaystyle (\bar{x},\bar{z}) = 0 } を得るがこれは矛盾である．


({\displaystyle \Longrightarrow })
{\displaystyle C } が線形独立な行をもたないと仮定する．{\displaystyle C^T \bar{z}=0 } をみたす零ベクトルでないベクトル {\displaystyle \bar{z} } が存在する．以下を得るが，KKT行列が正則でないことを示しており矛盾である．

{\displaystyle \;\;\;\;\;\; \begin{bmatrix} 2 A^T A & C^T \\ C & 0 \end{bmatrix} \begin{bmatrix} 0 \\ \bar{z} \end{bmatrix} = 0 }

{\displaystyle \begin{bmatrix} A \\ C \end{bmatrix} } が線形独立な列をもたないと仮定する．{\displaystyle \begin{bmatrix} A \\ C \end{bmatrix} \bar{x} = 0 } をみたす零ベクトルでないベクトル {\displaystyle \bar{x} } が存在する．以下を得るが，KKT行列が正則でないことを示しており矛盾である．

{\displaystyle \;\;\;\;\;\; \begin{bmatrix} 2 A^T A & C^T \\ C & 0 \end{bmatrix} \begin{bmatrix} \bar{x} \\ 0 \end{bmatrix} = 0 }

(証明終わり)


仮定.(0.1)(0.2)と事実1.よりKKT行列は正則です．(2.1.1)は以下で表されるただ一つの解をもちます．

(2.1.2){\displaystyle \;\;\; \begin{bmatrix} \hat{x} \\ \hat{z} \end{bmatrix} = \begin{bmatrix} 2 A^T A & C^T \\ C & 0 \end{bmatrix}^{-1} \begin{bmatrix} 2 A^T b \\ d \end{bmatrix} }

次節の事実2.にあるように(2.1.2)は制約付き最小二乗問題(1.1)のただ一つの解であり，この解は {\displaystyle \hat{x} } が {\displaystyle b } と {\displaystyle d } についての線形関数であることを示しています．


[ 2.2. 制約付き最小二乗問題のただ一つの解 ]

事実2.

KKT方程式(2.1.1)の解(2.1.2)は制約付き最小二乗問題(1.1)のただ一つの解である．

証明.

KKT方程式(2.1.1)のただ一つの解(2.1.2)の {\displaystyle \hat{x},\hat{z} } について以下が成り立つ．

(2.1.3){\displaystyle \;\;\; 2 A^T A \hat{x} + C^T \hat{z} = 2 A^T b }
(2.1.4){\displaystyle \;\;\; C \hat{x} = d }

{\displaystyle C x = d } をみたす任意の {\displaystyle x \neq \hat{x} } について {\displaystyle \left\| Ax - b \right\|^2 \gt \left\| A \hat{x} - b \right\|^2 } が成り立つことを示せばよい．
はじめに {\displaystyle \left\| Ax - b \right\|^2 \ge \left\| A \hat{x} - b \right\|^2 } を示す．

{\displaystyle \;\;\; \left\| Ax - b \right\|^2 = \left\| (Ax - A \hat{x} ) + ( A \hat{x} - b) \right\|^2 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left[ (Ax - A \hat{x} ) + ( A \hat{x} - b) \right]^T \left[ (Ax - A \hat{x} ) + ( A \hat{x} - b) \right] }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 + 2 (Ax - A \hat{x})^T (A \hat{x} - b) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 + 2 (A (x - \hat{x}) )^T (A \hat{x} - b) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 + 2 (x - \hat{x})^T A^T (A \hat{x} - b) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 + 2 (x - \hat{x})^T ( A^T A \hat{x} - A^T b) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 + (x - \hat{x})^T ( 2 A^T A \hat{x} - 2 A^T b) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 + (x - \hat{x})^T ( - C^T \hat{z}) \;\;\; \because } (2.1.3)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 - (x - \hat{x})^T C^T \hat{z} }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 - (C (x - \hat{x}))^T \hat{z} }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 - (C x - C \hat{x})^T \hat{z} }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 - (d - d)^T \hat{z} \;\;\; \because Cx=d, } (2.1.4)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 - 0^T \hat{z} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| Ax - A \hat{x} \right\|^2 + \left\| A \hat{x} - b \right\|^2 \;\;\;\;\;\; } (※※)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge \left\| A \hat{x} - b \right\|^2 \;\;\; \because \forall x \in \mathbf{R}^n , \ \left\| Ax - A \hat{x} \right\|^2 \ge 0 }

つぎに {\displaystyle x = \hat{x} } がただ一つの解であることを示す．

{\displaystyle \;\;\; \left\| Ax - b \right\|^2 = \left\| A \hat{x} - b \right\|^2 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\; \Rightarrow \ \left\| Ax - A \hat{x} \right\|^2 = 0 \;\;\; \because } (※※)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow \ \left\| A (x - \hat{x}) \right\|^2 = 0 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow \ A (x - \hat{x}) = 0 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow \ \begin{bmatrix} A \\ C \end{bmatrix} ( x - \hat{x} ) = 0 \;\;\; \because C x = d, } (2.1.4)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\; \Rightarrow \ x - \hat{x} = 0 \;\;\; \because } 仮定.(0.2)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow \ x = \hat{x} }

したがって {\displaystyle x = \hat{x} } は {\displaystyle \left\| Ax - b \right\|^2 = \left\| A \hat{x} - b \right\|^2 } となるただ一つの {\displaystyle x } であり，{\displaystyle C x = d } をみたす任意の {\displaystyle x \neq \hat{x} } について {\displaystyle \left\| Ax - b \right\|^2 \gt \left\| A \hat{x} - b \right\|^2 } が成り立つ．(証明終わり)

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

以上，制約付き最小二乗法の基礎をまとめました．



参考文献
[1] Boyd, S., and Vandenberghe, L. (2018), Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares, Cambridge University Press.
[2] Wolfram MathWorld Inner Product のページ http://mathworld.wolfram.com/InnerProduct.html
[3] Wikipedia Matrix norm のページ https://en.wikipedia.org/wiki/Matrix_norm

おまけ
[1] へのリンク http://vmls-book.stanford.edu/vmls.pdf