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

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

最適化問題の摂動と感度分析をまとめる

数学 数理最適化

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

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

弱双対性の幾何的な解釈と，凸最適化問題における強双対性とスレーターの条件の幾何的な解釈をまとめる - エンジニアを目指す浪人のブログ


最適化問題における制約の摂動(perturbation)と感度分析(sensitivity analysis)について，強双対性が成り立つときの双対問題の最適解の意味を考える上で重要に感じたので，その内容をまとめておくことにしました．Boyd and Vandenberghe(2004)の5章6節をベースにしています．

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

目次

{\displaystyle \; } 0. 準備
{\displaystyle \; } 1. 摂動を考慮した不等式
{\displaystyle \; } 2. 大域的な感度
{\displaystyle \;\;\; } 2.1. 大域的な不等式
{\displaystyle \;\;\; } 2.2. 大域的な感度の解釈
{\displaystyle \; } 3. 局所的な感度
{\displaystyle \;\;\; } 3.1. 局所感度分析
{\displaystyle \;\;\; } 3.2. 潜在価格としての解釈


[ 0. 準備 ]

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

同記事にある標準的な最適化問題を再掲します．{\displaystyle x \in \mathbb{R}^n } です．

(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 \lambda \in \mathbb{R}^m ,\nu \in \mathbb{R}^p } をラグランジュ乗数(Lagrange multiplier)といいます．

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

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


同記事にある(0.1)のラグランジュ双対問題を再掲します．

(0.3)
{\displaystyle \mathrm{maximize} \;\;\;\; g(\lambda,\nu) }
{\displaystyle \mathrm{subject \; to} \;\;\ \lambda \succeq 0 }


以下の記号を準備します．

(0.4){\displaystyle \;\;\; \mathcal{D}= \bigcap_{i=0}^m \mathrm{dom} \ f_i \; \cap \; \bigcap_{i=1}^p \mathrm{dom} \ h_i }

(0.5){\displaystyle \;\;\; x \in \mathbb{R}^n , \ x \preceq 0 \ \Leftrightarrow \ x_i \le 0, \ i = 1, \ldots,n }



[ 1. 摂動を考慮した不等式 ]

元の最適化問題(0.1)について，以下の摂動を考慮した最適化問題を考えます:

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

{\displaystyle u = 0,\ v= 0 } とすると元の最適化問題(0.1)と同じです．{\displaystyle u_i \gt 0 } のとき {\displaystyle i } 番目の不等式制約を緩和する(relaxed)ことを意味します; {\displaystyle u_i \lt 0 } のとき {\displaystyle i } 番目の不等式制約を強化する(tightened)ことを意味します．したがって摂動を考慮した最適化問題(1.1)は元の問題(0.1)の等式制約を {\displaystyle u_i } により強化あるいは緩和することと等式制約の右辺を {\displaystyle v_i } に変更することの結果です．

最適化問題(1.1)の最適値を以下で定義します:

(1.2){\displaystyle \;\;\; p^*(u,v) = \inf \{ f_0(x) \ | \ \exists x \in \mathcal{D},\ f_i(x) \le u_i, \ i=1,\ldots,m, \ h_i(x) = v_i, \ i=1,\ldots,p \} }

摂動により実行不可能となる場合 {\displaystyle p^*(u,v) = \infty } を得ます．元の問題(0.1)の最適値は {\displaystyle p^*(0,0) = p^* } です．大雑把に言えば，関数 {\displaystyle p^* : \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R} } は制約の右辺への摂動の関数として問題の最適値を与えます．

元の問題(0.1)が凸最適化問題のとき，関数 {\displaystyle p^*(u,v) } は以下であり {\displaystyle u,v } の凸関数です; 実際にエピグラフは冒頭の過去記事(弱双対性の幾何的な解釈)(1.2.1)にある集合 {\displaystyle \mathcal{A} } の閉包(文献[2]にあります)であり，凸集合です．

(1.3){\displaystyle \;\;\; p^*(u,v) = \inf \{ f_0(x) \ | \ \exists x \in \mathcal{D},\ f_i(x) \le u_i, \ i=1,\ldots,m, \ Ax-b=v \} }



[ 2. 大域的な感度 ]

[ 2.1. 大域的な不等式 ]

強双対性が成り立ち，ラグランジュ双対問題の最適値が存在すると仮定します(これは元の最適化問題(0.1)が凸最適化問題ならばスレーターの条件をみたすときです)．{\displaystyle (\lambda^*,\nu^*) } を(元の問題の)ラグランジュ双対問題(0.3)の最適値とします．

摂動を考慮した最適化問題(1.1)の実行可能な任意の点 {\displaystyle x } について以下を得ます．

(2.1.1){\displaystyle \;\;\; p^*(0,0) = g(\lambda^*,\nu^*) \;\;\; \because } 強双対性

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

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le f_0(x) + \sum_{i=1}^{m} \lambda_i^* f_i(x) + \sum_{i=1}^{m} \nu_i^* h_i(x) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le f_0(x) + \lambda_i^{*T} u + \nu^{*T} v \;\;\; \because \lambda^* \succeq 0 }

{\displaystyle \;\;\;\;\;\;\;\;\; \Leftrightarrow \ f_0(x) \;\;\; \ge p^*(0,0) - \lambda^{*T} u - \nu^{*T} v }

{\displaystyle \;\;\;\;\;\;\;\;\; \Rightarrow \ p^*(u,v) \ge p^*(0,0) - \lambda^{*T} u - \nu^{*T} v \;\;\;\;\;\; } (2.1.1)(※)


[ 2.2. 大域的な感度の解釈 ]

強双対性が成り立つとき，最適なラグランジュ乗数 {\displaystyle \lambda^*,\nu^* } の様々な解釈は不等式(2.1.1)(※)から直接したがいます．いくつかの結果は以下です:

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

・{\displaystyle \lambda_i^* } が大きく({\displaystyle \lambda_i^* \gt 0 }) {\displaystyle i } 番目の不等式制約を強化する(すなわち {\displaystyle u_i \lt 0 } を選ぶ)とき，最適値 {\displaystyle p^*(u,v) } は大きく増加することが保証される

・{\displaystyle \lambda_i^* } が小さく({\displaystyle \lambda_i^* \gt 0 }) {\displaystyle i } 番目の不等式制約を緩和する(すなわち {\displaystyle u_i \gt 0 } を選ぶ)とき，最適値 {\displaystyle p^*(u,v) } は過度に減少しない

・{\displaystyle \nu_i^* } が大きく正の数({\displaystyle \nu_i^* \gt 0 })で {\displaystyle v_i \lt 0 } を選ぶ，あるいは {\displaystyle \nu_i^* } が大きく負の数({\displaystyle \nu_i^* \lt 0 })で {\displaystyle v_i \gt 0 } を選ぶとき，最適値 {\displaystyle p^*(u,v) } は大きく増加することが保証される

・{\displaystyle \nu_i^* } が小さく正の数({\displaystyle \nu_i^* \gt 0 })で {\displaystyle v_i \gt 0 } を選ぶ，あるいは {\displaystyle \nu_i^* } が小さく負の数({\displaystyle \nu_i^* \lt 0 })で {\displaystyle v_i \lt 0 } を選ぶとき，最適値 {\displaystyle p^*(u,v) } は過度に減少しない

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

不等式(2.1.1)(※)と上の4つの結論は摂動を考慮した問題の最適値の下界の与えます．上界は与えません．この理由により結果は制約の緩和あるいは強化に関して非対称です．たとえば，{\displaystyle \lambda_i^* } が大きく {\displaystyle i } 番目の不等式制約を少し緩和します(すなわち小さい {\displaystyle u_i \gt 0 } をとります)．この場合不等式(2.1.1)(※)は役に立ちません; たとえば，最適値はかなり減少することを意味しません．

不等式制約一つのみのときの凸最適化問題のときの不等式(2.1.1)(※)について以下に示します．不等式はアフィン関数 {\displaystyle p^*(0) - \lambda^* u } が凸関数 {\displaystyle p^* } の下界であることを意味します．

f:id:seetheworld1992:20210208130244p:plain



[ 3. 局所的な感度 ]

[ 3.1. 局所感度分析 ]

以下の事実が成り立ちます．

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

事実.

摂動を考慮した最適化問題(1.1)の強双対性が成り立つ，また最適値 {\displaystyle p^*(u,v) } が {\displaystyle u = 0, v = 0 } で微分可能であることを仮定する．このとき以下が成り立つ．

(3.1.1){\displaystyle \;\;\; \lambda_i^* = - \frac{\partial p^*(0,0)}{\partial u_i} }

(3.1.2){\displaystyle \;\;\; \nu_i^* = - \frac{\partial p^*(0,0)}{\partial v_i} }


証明.

{\displaystyle e_i} は {\displaystyle i} 番目の要素の単位ベクトルとする．{\displaystyle u = t e_i, v = 0 } とする摂動について考える．

{\displaystyle t \gt 0 } について以下を得る．

{\displaystyle \;\;\;\frac{\partial p^*(0,0) }{\partial u_i} = \lim_{t \to 0} \frac{p^*(te_i,0)-p^*(0,0) }{t-0} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge \lim_{t \to 0} \frac{ - \lambda^{*T} (te_i) - \nu^{*T} v }{t} \;\;\; \because } (2.1)(※)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = - \lambda_i^* }

{\displaystyle t \lt 0 } について以下を得る．

{\displaystyle \;\;\;\frac{\partial p^*(0,0) }{\partial u_i} = \lim_{t \to 0} \frac{p^*(te_i,0)-p^*(0,0) }{t-0} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \lim_{t \to 0} \frac{ - \lambda^{*T} (te_i) - \nu^{*T} v }{t} \;\;\; \because } (2.1)(※)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = - \lambda_i^* }

{\displaystyle u = 0 } で微分可能であると仮定しているので，左微分係数と右微分係数が等しくなければならない(文献[3]にあります)．したがって以下を得る．

{\displaystyle \;\;\; \frac{\partial p^*(0,0) }{\partial u_i} = - \lambda_i^* }


同様に以下を得ることができる．

{\displaystyle \;\;\; \frac{\partial p^*(0,0) }{\partial v_i} = - \nu_i^* }

(証明終わり)

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


事実.は最適なラグランジュ乗数 {\displaystyle \lambda^*, \ \nu^* } と {\displaystyle u = 0, v = 0 } での {\displaystyle p^*(u,v) } の勾配の関係を表すものです．Figure 5.10では {\displaystyle - \lambda^* } は {\displaystyle u = 0 } のまわりの {\displaystyle p^*(u) } の傾きになっています．これは(3.1.1)の例です．

このように，{\displaystyle p^*(u,v) } が {\displaystyle u = 0, v = 0 } で微分可能かつ強双対性が成り立つとき，最適なラグランジュ乗数 {\displaystyle \lambda^*, \ \nu^* } はまさに制約の摂動に対する最適値の局所的な感度です．微分不可能なとき(大域的な感度の解釈)と対照的に，この解釈は対称的です: {\displaystyle i } 番目の不等式制約を小さく強化する(すなわち小さい {\displaystyle u_i \lt 0 } をとる)ことは近似的に {\displaystyle - \lambda_i^* u_i } による {\displaystyle p^* } の増加をもたらします; {\displaystyle i } 番目の不等式制約を小さく緩和する(すなわち小さい {\displaystyle u_i \gt 0 } をとる)ことは近似的に {\displaystyle \lambda_i^* u_i } による {\displaystyle p^* } の減少をもたらします．


双対問題の最適解である最適なラグランジュ乗数(の要素)すなわち局所的な感度 {\displaystyle \lambda_i^*, \ \nu_i^* } は制約が最適点 {\displaystyle x^* } でどのくらい有効であるかを意味する定量的な尺度です．

{\displaystyle f_i(x^*) \lt 0 } のとき，対応する {\displaystyle i } 番目の不等式制約は(無くてもよいということであり)無効であり，最適値 {\displaystyle p^*} に影響を与えることなしに小さな量 {\displaystyle u_i} による制約の強化や緩和が可能です．相補性条件(冒頭の過去記事(ラグランジュ関数)(3.3)')より {\displaystyle \lambda_i^* = 0} なので(3.1.1)よりこのことが確認できます．

しかしいま {\displaystyle f_i(x^*) = 0 } と仮定します．したがって対応する {\displaystyle i } 番目の不等式制約は(存在意義があるということであり)最適点で有効です．{\displaystyle i } 番目の最適なラグランジュ係数 {\displaystyle \lambda_i^* } は制約がどのように有効であるかを教えてくれます; {\displaystyle \lambda_i^* } が小さいとき，最適値に対する大きな影響なしに不等式制約を少し強化あるいは緩和できることを意味します; {\displaystyle \lambda_i^* } が大きいとき，不等式制約を少し強化あるいは緩和すると最適値に対する影響は大きいものになります．


[ 3.2. 潜在価格としての解釈 ]

事実.(3.1.1)(3.1.2)について，経済学の観点における解釈を得ることができます．

(簡単のため)等式制約のないスレーターの条件が成り立つ凸最適化問題を考えます．変数 {\displaystyle x \in \mathbb{R}^n } は会社をどのように経営するかを決定し，目的関数 {\displaystyle f_0(x) } は損失，すなわち {\displaystyle - f_0(x) } は利益です．各不等式制約 {\displaystyle f_i(x) \le 0 } は労働力，鉄，倉庫の容量のような資源の限界を表します．摂動を考慮した(負の)損失関数 {\displaystyle - p^*(u) } は，会社の各資源の利用可能(限界)量がより多くなるあるいは少なくなるときにどの程度の利益を得ることができるかを意味します．{\displaystyle - p^*(u) } が {\displaystyle u=0 } のまわりで微分可能のとき以下を得ます．いいかえると，{\displaystyle \lambda_i^* } は，資源 {\displaystyle i } の利用可能(限界)量の小さい増加によって会社がどのくらいの利益を得ることが可能であるかの近似的な量を意味します．

(3.2.1){\displaystyle \;\;\; \lambda_i^* = - \frac{\partial p^*(0)}{\partial u_i} }


{\displaystyle \lambda_i^* } は会社が資源 {\displaystyle i } を購入あるいは売却できるときの資源 {\displaystyle i } の自然な価格です．これを潜在価格(shadow price)あるいは均衡価格(equilibrium price)といいます．たとえば，会社は資源 {\displaystyle i } を {\displaystyle \lambda_i^* } 未満の価格で購入可能であるとします．この場合，資源 {\displaystyle i } をいくらか購入します．そうすることで資源 {\displaystyle i } を購入するコストよりも大きい利益を得ることができます．逆に，資源 {\displaystyle i } の価格が {\displaystyle \lambda_i^* } よりも大きいとき，会社は保有する資源 {\displaystyle i } の一部を売却し，正味の利益を得ることができます．資源 {\displaystyle i } の一部を売却することによる収入が(売却する量の分だけ)資源を利用できないことによる利益の減少よりも大きいからです．　　　


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

以上，最適化問題の摂動と感度分析をまとめました．



参考文献
[1] Boyd, S., and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.
[2] Wikipedia Closure (topology) のページ https://en.wikipedia.org/wiki/Closure_(topology)
[3] Wikipedia Semi-differentiability のページ https://en.wikipedia.org/wiki/Semi-differentiability