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

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

凸最適化問題の等式制約の除去についてまとめる

数学 数理最適化

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

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

ムーア・ペンローズ逆行列による連立一次方程式の解表現について考える - エンジニアを目指す浪人のブログ


勉強を進めていて，凸最適化問題の等式制約を除去する方法について面白く感じたので，その内容をまとめておくことにしました．Boyd and Vandenberghe(2004)の4章1節(の3の一部)，4章2節(の4の一部)，10章1節(の2の一部)をベースにしています．

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

目次

{\displaystyle \; } 0. 準備
{\displaystyle \; } 1. 一般の等式制約の除去
{\displaystyle \; } 2. 線形等式制約の除去
{\displaystyle \; } 3. 線形制約を除去する行列の選択


[ 0. 準備 ]

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

標準的な(凸でなくてもよい)最適化問題は，冒頭の過去記事(ラグランジュ関数)[ 0. 準備 ](0.1)にあります．再掲します．

(0.1)
{\displaystyle \mathrm{minimize} \;\;\;\; f_0(x) }
{\displaystyle \mathrm{subject \; to} \;\;\ f_i(x) \le 0 , \;\;\; i=1,\ldots,m }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; h_i(x) = 0, \;\;\; i=1,\ldots,p }


行列 {\displaystyle A } の列空間(値域)を {\displaystyle \mathcal{R}(A) } とします(冒頭の過去記事(ムーア・ペンローズ逆行列による連立一次方程式)では {\displaystyle C(A) } を用いています)．

行列 {\displaystyle A } の零空間(核)を {\displaystyle \mathcal{N}(A) } とします(冒頭の過去記事(ムーア・ペンローズ逆行列による連立一次方程式)では {\displaystyle N(A) } を用いています)．


[ 1. 一般の等式制約の除去 ]

はじめに一般の等式制約の除去について考えます．

(1.1){\displaystyle \;\;\; h_i(x) = 0, \;\;\; i=1,\ldots,p }

等式制約(1.1)のすべての解をパラメータ {\displaystyle z \in \mathbb{R}^k } で表現できるとき，以下で説明するように等式制約を除去することができます．つぎの関数を考えます．

(1.2){\displaystyle \;\;\; \phi : \mathbb{R}^k \to \mathbb{R}^n \;\;\; \mathrm{s.t.} \;\;\; [ \; h_i(x) = 0, \;i=1,\ldots,p \; ] \Leftrightarrow [ \; \exists z \in \mathbb{R}^k, \; x = \phi (z) \; ] }

つぎの最適化問題は元の最適化問題(0.1)と等価です．

(1.3)
{\displaystyle \mathrm{minimize} \;\;\;\; \tilde{f}_0 (z) = f_0 (\phi(z)) }
{\displaystyle \mathrm{subject \; to} \;\;\ \tilde{f}_i (z) = f_i(\phi(z)) \le 0 , \;\;\; i=1,\ldots,m }

この変換した問題は変数 {\displaystyle z \in \mathbb{R}^k }，{\displaystyle m } 本の不等式制約からなり，等式制約はありません．{\displaystyle z } が変換した問題(1.3)の最適点ならば，{\displaystyle x = \phi(z) } は元の問題(0.1)の最適点です．逆に，{\displaystyle x } が元の問題(0.1)の最適点ならば，({\displaystyle x } は実行可能であり(1.1)をみたすので(1.2)より) {\displaystyle x = \phi (z) }　となる {\displaystyle z } が少なくとも一つ存在します．任意のそのような {\displaystyle z } は変換した問題(1.3)の最適点です．


[ 2. 線形等式制約の除去 ]

つぎに線形等式制約の除去について考えます．{\displaystyle p \times n } 行列 {\displaystyle A, \; b \in \mathbb{R}^p } とします．凸最適化問題は等式制約が線形でなければなりません(冒頭の過去記事(ラグランジュ関数)[ 0. 準備 ](0.8)にあります)．

(2.1){\displaystyle \;\;\; Ax = b }

等式制約(1.1)がすべて線形，すなわち(2.1)のとき，変数を除去する過程はより明示的に記述でき，数値的に容易に実行できます．(2.1)が解を持たない，すなわち {\displaystyle b \notin \mathcal{R}(A) } のとき，元の問題(0.1)は実行不可能です．そうではなく(2.1)が解を持つ，すなわち {\displaystyle b \in \mathcal{R}(A) } のときを考えます．{\displaystyle \hat{x} \in \mathbb{R}^n } を等式制約 {\displaystyle A x = b } の解とします．つぎに {\displaystyle \mathcal{R}(F)=\mathcal{N}(A) } となる {\displaystyle n \times k } 行列 {\displaystyle F } とします．すると連立一次方程式(2.1)の一般解は {\displaystyle Fz + \hat{x}, \; z \in \mathbb{R}^k } です．
(冒頭の過去記事(ムーア・ペンローズ逆行列による連立一次方程式)の内容を用います．{\displaystyle x_0, \ Fz } はそれぞれ同記事定理 6.3.の {\displaystyle A^+ b, \ (I - A^+ A) y } に対応するものと考えることができます．)
({\displaystyle k = n - \mathrm{rank} A } のとき {\displaystyle F } は {\displaystyle n \times (n - \mathrm{rank} A) } 行列であり，このとき {\displaystyle F } を列フルランクすなわち {\displaystyle \mathrm{rank} F = n - \mathrm{rank} A \ \Leftrightarrow \ \mathrm{dim} \ \mathcal{R}(F) = \mathrm{dim} \ \mathcal{N}(A) } に選ぶことができます．)

{\displaystyle x = Fz + \hat{x} } を元の問題(0.1)に代入して得る変数 {\displaystyle z } についての以下の最適化問題は元の問題(0.1)に等価であり，等式制約はありません．目的関数と不等式制約関数 {\displaystyle f_0,\ldots,f_m } が凸関数のとき，アフィン関数と凸関数の合成は凸関数なので(文献[2]にあります)，この問題は(元問題と同様に)凸最適化問題です．

(2.2)
{\displaystyle \mathrm{minimize} \;\;\;\; f_0 (Fz + \hat{x}) }
{\displaystyle \mathrm{subject \; to} \;\;\ f_i (Fz + \hat{x}) \le 0 , \;\;\; i=1,\ldots,m }


{\displaystyle A} が行フルランクであれば，変数の数よりも等式制約の方程式の数の方が少なく，等式制約はそれぞれ独立です．ここまでの内容より，以下の事実が成り立ちます．

'--------------------------------------------------------------------------------------------------------------------------------------------
事実.

{\displaystyle A} が行フルランク，すなわち {\displaystyle \mathrm{rank} A = p \lt n } のとき，{\displaystyle n \times (n-p) } 行列 {\displaystyle F } の列を {\displaystyle \mathcal{N}(A) } の基底とすることで，{\displaystyle \mathcal{R}(F)=\mathcal{N}(A) } となる列フルランクの {\displaystyle F } をとることができる．このとき以下が成り立つ．

{\displaystyle \;\;\; \{ x \in \mathbb{R}^n \ | \ Ax = b \} = \{ Fz + \hat{x} \ | \ z \in \mathbb{R}^{n-p},\ A \hat{x} = b \} }

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


[ 3. 線形制約を除去する行列の選択 ]

{\displaystyle A} は行フルランクとします．{\displaystyle \mathcal{R}(F) = \mathcal{N}(A) } となる {\displaystyle n \times (n-p) } 行列 {\displaystyle F } は多くの選択があります．{\displaystyle F } をそのような行列の一つ，{\displaystyle (n-p) \times (n-p) } 行列 {\displaystyle T } を正則とすると，{\displaystyle \tilde{F} = FT } は以下をみたす行列です．

(3.1){\displaystyle \;\;\; \mathcal{R}(\tilde{F}) = \mathcal{R}(F) = \mathcal{N}(A) }

逆に，{\displaystyle F, \ \tilde{F} } が(3.1)をみたすとき，{\displaystyle \tilde{F} = FT } をみたす正則行列 {\displaystyle T } が存在します．

簡単のため，不等式制約がない場合を考えます．線形変換を導入すると最適化問題(2.2)は以下の等価な問題に変換できます．いいかえると，行列 {\displaystyle F } を変換することは最適化問題を変数変換することであるといえます．

(3.2){\displaystyle \;\;\; z = T \tilde{z} }

(3.3)
{\displaystyle \mathrm{minimize} \;\;\;\; f_0 (Fz + \hat{x}) = f_0 (F T \tilde{z} + \hat{x}) = f_0 ( \tilde{F} \tilde{z} + \hat{x}) }

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

以上，凸最適化問題の等式制約の除去についてまとめました．



参考文献
[1] Boyd, S., and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.
[2] Wikipedia Convex function のページ https://en.wikipedia.org/wiki/Convex_function