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

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

等式制約あり凸最適化問題の基礎をまとめる

数学 数理最適化

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

ラグランジュ関数，ラグランジュ双対問題，最適性条件(KKT条件)のあらすじをまとめる - エンジニアを目指す浪人のブログ

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

対称行列を係数行列とする連立一次方程式が解をもつための必要十分条件は定数ベクトルが係数行列の零空間の要素と直交することであることを証明する - エンジニアを目指す浪人のブログ

凸最適化問題の等式制約の除去についてまとめる - エンジニアを目指す浪人のブログ

双対問題を解くことを経て主問題を解くことの概要をまとめる - エンジニアを目指す浪人のブログ


等式制約あり凸最適化問題の基礎をまとめておくことにしました．Boyd and Vandenberghe(2004)の10章1節をベースにしています．

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

目次

{\displaystyle \; } 0. 準備
{\displaystyle \; } 1. 等式制約あり凸最小化問題
{\displaystyle \; } 2. 等式制約あり凸二次最小化問題
{\displaystyle \; } 3. 等式制約の除去
{\displaystyle \; } 4. 双対問題を経由して等式制約あり問題を解くこと



[ 0. 準備 ]

冒頭の過去記事(ラグランジュ関数)の内容を必要とします．


[ 1. 等式制約あり凸最小化問題 ]

以下の凸最適化問題を考えます．{\displaystyle f : \mathbb{R}^n \to \mathbb{R}}，{\displaystyle p \times n } 行列 {\displaystyle A, \ x \in \mathbb{R}^n, \ b \in \mathbb{R}^p } です．

(1.1)
{\displaystyle \mathrm{minimize} \;\;\;\; f(x) }
{\displaystyle \mathrm{subject \; to} \;\;\ Ax=b }

{\displaystyle f } は凸で二階微分可能とします．{\displaystyle A } は行フルランクとします．すなわち変数の数よりも等式制約の方程式の数の方が少なく，{\displaystyle p } 本の等式制約はそれぞれ独立です．

(1.2){\displaystyle \;\;\; \mathrm{rank}A = p \lt n }

最適点(optimal point) {\displaystyle x^* } が存在すると仮定します．最適値(optimal value) {\displaystyle p^* } は以下です．

(1.3){\displaystyle \;\;\; p^* = \inf \{ f(x) \ | \ Ax=b \} }

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

{\displaystyle f } の定義域を {\displaystyle \mathrm{dom} \ f } とします．KKT条件より以下が成り立ちます．

(1.4){\displaystyle \;\;\; [ \ x^* \in \mathrm{dom} \ f \ は最適点 \ ] \ \Leftrightarrow [ \ \exists \nu^* \in \mathrm{R}^p, \;\; A x^* = b, \;\; \nabla f(x^*) + A^T \nu^* = 0 \ ] }

以下をそれぞれ主実行方程式(primal feasibility equations)，双対実行方程式(dual feasibility equations)といい，あわせてKKT方程式(KKT equations)といいます．前者は線形，後者は一般に非線形です．KKT方程式は {\displaystyle n + p } 個の変数 {\displaystyle x^*, \nu^* } と {\displaystyle p + n } 本の方程式からなります．

(1.5){\displaystyle \;\;\; A x^* = b }

(1.6){\displaystyle \;\;\; \nabla f(x^*) + A^T \nu^* = 0 }

(1.4)より，凸最適化問題(1.1)を解くことはKKT方程式(1.5)(1.6)を解くことと等価です．これらの最適性条件を解析的に解くことができるいくつかの問題があります．最も重要な例は目的関数が二次関数のときです．次章で扱います．

任意の等式制約あり凸最適化問題は等式制約を除去することにより等価な制約なし問題に縮約(reduce)することができます．そのとき制約なし問題に対する勾配法，ニュートン法などを用いて問題を解くことができます．もう一つの方法は(双対関数は二階微分可能であるときは)双対問題を解くことを利用することです．双対問題の解を用いて元の問題の解を復元することができます．

多くの場合，等式制約を直接扱う方法は，(制約なし問題に)縮約した問題を扱う方法よりも好ましいです．一つの理由は，スパース性のような問題の構造が等式の除去(あるいは双対問題を構成すること)により破壊されてしますからです; 対照的に，等式制約を直接扱う方法は問題の構造を利用することができます．もう一つの理由は，概念的なものです; 等式制約を直接扱う方法は，KKT条件(最適性条件)(1.5)(1.6)を直接解く方法と考えることができます．



[ 2. 等式制約あり凸二次最小化問題 ]

等式制約あり凸二次最小化問題を考えます．{\displaystyle n \times n } 行列 {\displaystyle P } は半正定値，{\displaystyle p \times n } 行列 {\displaystyle A } とします．また {\displaystyle x \in \mathbb{R}^n, \ q \in \mathbb{R}^n, \ r \in \mathbb{R}, \ b \in \mathbb{R}^p } です．冒頭の過去記事(係数行列が対称行列の二次関数)定理1.よりこの問題は凸最適化問題です．

(2.1)
{\displaystyle \mathrm{minimize} \;\;\;\; f(x) = (1/2) x^T P x + q^T x + r }
{\displaystyle \mathrm{subject \; to} \;\;\ Ax=b }

この問題のKKT方程式(1.5)(1.6)は以下となります．

(2.2){\displaystyle \;\;\; A x^* = b }

(2.3){\displaystyle \;\;\; P x^* + q + A^T \nu^* = 0 }

以下のように表現できます．これは {\displaystyle n + p } 個の変数 {\displaystyle x^*, \nu^* } と {\displaystyle p + n } 本の線形方程式からなり，等式制約あり凸二次最小化問題(2.1)のKKT系(KKT system)といい，係数行列はKKT行列(KKT matrix)といいます．KKT行列は対称行列であることに注意します．

(2.4){\displaystyle \;\;\; \begin{bmatrix} P & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} x^* \\ \nu^* \end{bmatrix} = \begin{bmatrix} -q \\ b \end{bmatrix} }

(2.5){\displaystyle \;\;\; M_{\mathrm{KKT}} = \begin{bmatrix} P & A^T \\ A & 0 \end{bmatrix} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = (M_{\mathrm{KKT}})^T \;\;\; \because P = P^T }

KKT行列が正則のとき，ただ一つの {\displaystyle (x^*,\nu^*) } が存在します．KKT行列が正則ではないがKKT系を解くことができるとき，無数の {\displaystyle (x^*,\nu^*) } が存在します．KKT系を解くことができないとき，問題(2.1)の下界が存在しない，あるいは実行不可能です．このとき，冒頭の過去記事(対称行列を係数行列とする連立一次方程式)事実.より以下が成り立ちます．行列の列空間(像)，零空間(核)をそれぞれ {\displaystyle \mathcal{R}(\cdot),\mathcal{N}(\cdot) } とします．

(2.6){\displaystyle \;\;\; \begin{bmatrix} -q \\ b \end{bmatrix} \notin \mathcal{R}(M_{\mathrm{KKT}}) }

{\displaystyle \;\;\;\;\;\; \Leftrightarrow \ \begin{bmatrix} -q \\ b \end{bmatrix}^T y \neq 0, \;\;\; y \in \mathcal{N}(M_{\mathrm{KKT}}) }

したがって，以下をみたす {\displaystyle y = \begin{bmatrix} v & w \end{bmatrix}^T, \; v \in \mathbb{R}^n, \ w \in \mathbb{R}^p }　が存在します．

(2.7){\displaystyle \;\;\; Pv + A^T w = 0, \;\;\; Av=0, \;\;\; - q^T v + b^T w \gt 0 }　

任意の実行可能な点を {\displaystyle \hat{x} } とすると，点 {\displaystyle x = \hat{x} + tv, \; t \in \mathbb{R} } は実行可能です．以下が成り立ち，たしかに問題(1.1)の下界が存在しないことがわかります．

(2.8){\displaystyle \;\;\; f(\hat{x}+tv) = r + q^T (\hat{x}+tv) + (1/2) (\hat{x}+tv)^T P \ (\hat{x}+tv) \;\;\; \because } (2.1)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = r + q^T \hat{x} + (1/2) \hat{x}^T P \ \hat{x} + t (q^T v) + (1/2) t^2 v^T P v + t v^T P \hat{x} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f(\hat{x}) + t (q^T v) + (1/2) t^2 v^T P v + t v^T P \hat{x} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f(\hat{x}) + t ( v^T P \hat{x} + q^T v) + (1/2) t^2 v^T P v }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f(\hat{x}) + t (- \hat{x}^T A^T w + q^T v) - (1/2) t^2 w^T A v \;\;\; \because } (2.7)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f(\hat{x}) + t (- \hat{x}^T A^T w + q^T v) \;\;\; \because } (2.7)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f(\hat{x}) + t (- (A \hat{x})^T w + q^T v) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f(\hat{x}) + t (- b^T w + q^T v) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \to - \infty, \;\;\; t \to \infty }


{\displaystyle P \succeq 0, \ \mathrm{rank} ( A ) = p \lt n } の仮定の下で，KKT行列(2.5)の正則性について成り立つ事実を(証明なしで)示します．

(2.9){\displaystyle \;\;\; \mathrm{rank} \begin{bmatrix} P & A^T \\ A & 0 \end{bmatrix} = n + p}

{\displaystyle \;\;\;\;\;\; \Leftrightarrow \ \mathcal{N} (P) \cap \mathcal{N} (A) = \{ 0 \} }

{\displaystyle \;\;\;\;\;\; \Leftrightarrow \ [ \ \mathcal{N} (A) \in x \ \Rightarrow \ x^T P x \gt 0 \ ] }

{\displaystyle \;\;\;\;\;\; \Leftrightarrow \ F^T P F \succ 0, \;\;\;\;\;\;\;\;\; F \in \mathbb{R}^{n \times (n-p)}, \; \mathcal{R} (F) = \mathcal{N} (A) }

特別な場合として，以下の事実を(証明なしで)示します．

(2.10){\displaystyle \;\;\; P \succ 0 \ \Rightarrow \ \mathrm{rank} \begin{bmatrix} P & A^T \\ A & 0 \end{bmatrix} = n + p }



[ 3. 等式制約の除去 ]

等式制約あり凸最適化問題(1.1)を解く一般的な方法の一つは，等式制約を除去して制約なし問題として解くことです．冒頭の過去記事(凸最適化問題の等式制約の除去)事実.より(1.1)を以下の制約なし凸最適化問題に変換することができます．{\displaystyle n \times (n-p) } 行列 {\displaystyle F } の列は {\displaystyle \mathcal{N}(A) } の基底です．

(3.1)
{\displaystyle \mathrm{minimize} \;\;\;\; \tilde{f} (z) = f (Fz + \hat{x}) \;\;\;\;\;\; \left( \{ x \in \mathbb{R}^n \ | \ Ax = b \} = \{ Fz + \hat{x} \ | \ z \in \mathbb{R}^{n-p},\ A \hat{x} = b \} \right) }

この問題の最適点 {\displaystyle z^* } から元の問題の最適点を得ることができます．

(3.2){\displaystyle \;\;\; x^* = F z^* + \hat{x} }


つぎに {\displaystyle \nu^* } を構成します．{\displaystyle n \times (n-p) } 行列 {\displaystyle F } の列が {\displaystyle \mathcal{N}(A) } の基底であることから，{\displaystyle n \times n } 行列 {\displaystyle X } は正則行列です．

(3.3){\displaystyle \;\;\; X = \begin{bmatrix} F^T \\ A \end{bmatrix} }

{\displaystyle z^* } は最適点なので以下が成り立ちます．

(3.4){\displaystyle \;\;\; 0 = \nabla \tilde{f} (z^*) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = F^T \nabla f(x^*) \;\;\; \because } 連鎖律(文献[3]にあります)

{\displaystyle n \times (n-p) } 行列 {\displaystyle F } の列は {\displaystyle \mathcal{N}(A) } の基底なので以下が成り立ちます．

(3.5){\displaystyle \;\;\; AF = 0 }

{\displaystyle \;\;\;\;\;\; \Leftrightarrow \ (AF)^T = 0 }

{\displaystyle \;\;\;\;\;\; \Leftrightarrow \ F^T A^T = 0 }

ここで(3.4)(3.5)より以下を得ます．

(3.6){\displaystyle \;\;\; \begin{bmatrix} F^T \\ A \end{bmatrix} \left( \nabla f(x^*) - A^T (AA^T)^{-1} A \nabla f(x^*) \right) = 0 }

{\displaystyle \;\;\;\;\;\;\;\;\; \Rightarrow \ \nabla f(x^*) - A^T (AA^T)^{-1} A \nabla f(x^*) = 0 \;\;\; \because X \ は正則 }

{\displaystyle \;\;\;\;\;\;\;\;\; \Leftrightarrow \ \nabla f(x^*) + A^T \left[ - (AA^T)^{-1} A \nabla f(x^*) \right] = 0 }

{\displaystyle \;\;\;\;\;\;\;\;\; \Leftrightarrow \ \nu^* = - (AA^T)^{-1} A \nabla f(x^*) \;\;\; \because } (1.6)



[ 4. 双対問題を経由して等式制約あり問題を解くこと ]

等式制約あり凸最適化問題(1.1)を解く別の方法は，双対問題を解くことを経て主問題の最適点 {\displaystyle x^* } を再構成することです．

ラグランジュ双対関数は以下です．{\displaystyle f^* (\cdot) } は関数 {\displaystyle f (\cdot) } の共役関数(conjugate function)です(文献[2]にあります)．

(4.1){\displaystyle \;\;\; g(\nu) = \inf_{x \in \mathcal{D}} L(x,0, \nu) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \inf_{x \in \mathcal{D}} \left( f(x)+\sum_{i=1}^m 0 \ f_i(x) +\sum_{i=1}^p \nu_i h_i(x) \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \inf_{x \in \mathcal{D}} \left( f(x)+\sum_{i=1}^p \nu_i h_i(x) \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \inf_{x \in \mathcal{D}} \left( f(x)+\sum_{i=1}^p \nu_i (a_i^T x - b_i) \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = - \sum_{i=1}^p \nu_i b_i + \inf_{x \in \mathcal{D}} \left( f(x)+\sum_{i=1}^p \nu_i a_i^T x \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = - b^T \nu + \inf_{x \in \mathcal{D}} \left( f(x)+\nu^T A x \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = - b^T \nu + \inf_{x \in \mathcal{D}} \left( (A^T \nu)^T x + f(x) \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = - b^T \nu - \sup_{x \in \mathcal{D}} \left( - (A^T \nu)^T x - f(x) \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = - b^T \nu - f^* (A^T \nu) }


ラグランジュ双対問題は以下です．
(4.2)
{\displaystyle \mathrm{maximize} \;\;\;\; - b^T \nu - f^* (A^T \nu) }

最適点 {\displaystyle x^* } が存在すると仮定しているので，KKT条件よりスレーターの条件が成り立っていなければなりません．したがって強双対性が成り立ち，以下が成り立ちます．

(4.3){\displaystyle \;\;\; \exists \nu^*, \; g(\nu^*)= d^* = p^* }

{\displaystyle g } が二階微分可能ならば，この制約なし問題は( {\displaystyle f^* } は凸関数なので)勾配降下法やニュートン法などの方法を適用することで {\displaystyle g } を最大化することができます．(一般に {\displaystyle f } が二階微分可能であっても {\displaystyle g } がそうであるとは限りません．)

最適点 {\displaystyle \nu^* } を得ることができれば {\displaystyle x^* } を得ることができます(冒頭の過去記事(双対問題を解くことを経て主問題)にあります)．


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

以上，等式制約あり凸最適化問題の基礎をまとめました．



参考文献
[1] Boyd, S., and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.
[2] Wikipedia Convex conjugate のページ https://en.wikipedia.org/wiki/Convex_conjugate
[3] Stanford University Stephen Boyd先生のノート http://210.43.0.57/moocresource/data/20100601/U/stanford201001009/review7_single.pdf