数理最適化問題のチートシート的なもの (1) - 最適化問題の分類・非線形最適化の続きです。
3. 双対理論
3.1 凸集合と凸関数
3.1.1 凸集合
集合 $S \subseteq \mathbb{R}^n$ が凸集合であるとは、任意の点 $\boldsymbol{x},\boldsymbol{y}\in S$ に対して以下の条件が満たされることをいう。
\lambda\boldsymbol{x}+(1-\lambda)\boldsymbol{y}\in S,~~~~~\forall\lambda\in[0,1] \tag{3-1} \label{3.0}
直観的には、凹んでない集合。
また、点 $\boldsymbol{x}_1,\cdots,\boldsymbol{x}_k\in\mathbb{R}^n$ が与えられたとき、条件
\sum_{i=1}^k\lambda_i=1,~~~~~\lambda_1,\cdots,\lambda_k\geq0 \tag{3-2} \label{3.1}
を満たす実数 $\lambda_1,\cdots,\lambda_k$ を用いて、以下のように表せる点 $\boldsymbol{x}$ を $\boldsymbol{x}_1,\cdots,\boldsymbol{x}_k$ の凸結合と呼ぶ。
\boldsymbol{x}=\sum_{i=1}^k\lambda_k\boldsymbol{x}_i \tag{3-3} \label{3.1b}
3.1.2 錐
空でない集合 $C\subseteq\mathbb{R}^n$ のうち、任意の元 $\boldsymbol{x}\in C$ と任意の実数 $\lambda\geq 0$ に対して条件 $\lambda\boldsymbol{x}\in C$ を満たすものを錐と呼ぶ。凸集合であるような錐を凸錐といい、閉集合であるような凸錐を閉凸錐という。
点 $\boldsymbol{x}_1,\cdots,\boldsymbol{x}_k\in\mathbb{R}^n$ が与えられたとき、非負の実数 $\lambda_1,\cdots,\lambda_k\geq 0$ を用いて以下のように表せる点 $\boldsymbol{x}$ を点 $\boldsymbol{x}_1,\cdots,\boldsymbol{x}_k$ の錐結合と呼ぶ。
\boldsymbol{x}=\sum_{i=1}^{k}\lambda_i\boldsymbol{x}_i \tag{3-4} \label{3.3b}
また、以下の集合 $C_2$ は凸錐であり、2次錐と呼ぶ。
C_2= \left\{ (t,\boldsymbol{x})\in\mathbb{R}\times\mathbb{R}^n~|~t\geq\left(\sum_{j=1}^{n}|x_j|^2\right)^{1/2} \right\} \tag{3-5} \label{3.3c}
錐 $C\subseteq\mathbb{R}^n$ に対して、以下の集合 $C^\circ\subseteq\mathbb{R}^n$ は錐であり、極錐と呼ぶ。
C^\circ=\lbrace\boldsymbol{s}\in\mathbb{R}^n~|~\boldsymbol{s}^T\boldsymbol{x}\leq0,~~\forall\boldsymbol{x}\in C\rbrace \tag{3-6}
また、集合 $S$ の接ベクトルの集合を $S$ の点 $\boldsymbol{x}$ における接錐と呼び、$T_S(\boldsymbol{x})$ と書く。接錐 $T_S(\boldsymbol{x})$ の極錐 $T_S(\boldsymbol{x})^\circ$ を点 $\boldsymbol{x}$ における $S$ の法線錐と呼び、$N_S(\boldsymbol{x})$ で表す。
3.1.3 凸関数
関数 $f:\mathbb{R}^n→\mathbb{R}\cup \lbrace +\infty \rbrace$ が凸関数であるとは、任意の点 $\boldsymbol{x}, \boldsymbol{y}\in\mathbb{R}^n$ に対して以下の条件が成り立つことである。
\lambda f(\boldsymbol{x})+(1-\lambda)f(\boldsymbol{y})\geq f(\lambda\boldsymbol{x}+(1-\lambda)\boldsymbol{y}),~~~~~\forall\lambda\in [0,1] \tag{3-7} \label{3.4}
関数 $f$ が凸関数であるための必要十分条件は、$f$ のヘッセ行列 $\nabla^2f(\boldsymbol{x})$ が半正定値であること。
3.2 劣勾配
凸関数 $f$ と点 $\boldsymbol{x}$ に対して、以下の条件を満たす $\boldsymbol{s}\in\mathbb{R}^n$ を、$f$ の $\boldsymbol{x}$ における劣勾配と呼ぶ。
f(\boldsymbol{y})\geq f(\boldsymbol{x})+\boldsymbol{s}\cdot (\boldsymbol{y}-\boldsymbol{x}),~~~~~\forall\boldsymbol{y}\in\mathbb{R}^n \tag{3-8} \label{3.10}
また、劣勾配全体の集合を劣微分 $\partial f(\boldsymbol{x})$ と呼ぶ。
\partial f(\boldsymbol{x})= \left\{ \boldsymbol{s}\in\mathbb{R}^n~|~f(\boldsymbol{y})\geq f(\boldsymbol{x})+\boldsymbol{s}\cdot(\boldsymbol{y}-\boldsymbol{x}) \right\} \tag{3-9} \label{3.11}
$f$ が点 $\boldsymbol{x}$ において微分可能な場合には、$\partial f(\boldsymbol{x})= \lbrace \nabla f(\boldsymbol{x}) \rbrace$ が成り立つ。
$\boldsymbol{s}\in \partial f(\boldsymbol{x})$ が成り立つことは、$\boldsymbol{x}\in\arg\max_{\boldsymbol{y}}\lbrace\boldsymbol{s}\cdot\boldsymbol{y}-f(\boldsymbol{y})~|~\boldsymbol{y}\in\mathbb{R}^n\rbrace$ が成り立つことと同値。
「任意の $\boldsymbol{x}$ において $f(\boldsymbol{x})$ 以下となるような接超平面の勾配」というイメージ。
3.3 分離定理
ベクトル $\boldsymbol{h}\neq\boldsymbol{0}\in\mathbb{R}^n$ とスカラー $g\in\mathbb{R}$ を用いて定義される以下の集合 $H(\boldsymbol{h},g)$ を、$\boldsymbol{h}$ と $g$ が定める超平面と呼ぶ。
※ $\boldsymbol{h}$ と $\boldsymbol{x}$ の内積が一定 ＝ $\boldsymbol{h}$ への $\boldsymbol{x}$ の正射影が一定 ＝ 超平面
H(\boldsymbol{h},g)=\lbrace\boldsymbol{x}\in\mathbb{R}^n~|~\boldsymbol{h}^T\boldsymbol{x}=g\rbrace \tag{3-10} \label{3.12b}
また、以下の集合 $H^+(\boldsymbol{h}, g),~H^-(\boldsymbol{h},g)$ を、超平面 $H(\boldsymbol{h},g)$ が定義する半空間と呼ぶ。
\begin{align}
H^+(\boldsymbol{h}, g)=\lbrace\boldsymbol{x}\in\mathbb{R}^n~|~\boldsymbol{h}^T\boldsymbol{x}\geq g\rbrace \tag{3-10} \label{3.12c} \\
H^-(\boldsymbol{h}, g)=\lbrace\boldsymbol{x}\in\mathbb{R}^n~|~\boldsymbol{h}^T\boldsymbol{x}\leq g\rbrace \tag{3-11} \label{3.12d}
\end{align}
集合 $S_1,S_2$ に対して条件 $S_1\subseteq H^+(\boldsymbol{h}, g),~S_2\subseteq H^-(\boldsymbol{h}, g)$ が成り立つとき、超平面 $H(\boldsymbol{h}, g)$ を $S_1$ と $S_2$ の分離超平面という。
分離定理は以下。
2つの空でない凸集合 $S_1, S_2\subseteq\mathbb{R}^n$ が $S_1\cap S_2=\emptyset$ を満たすならば、$S_1$ と $S_2$ の分離超平面が存在する。すなわち、以下の条件を満たす $\boldsymbol{s}\in\mathbb{R}^n$ が存在する。
\inf\lbrace\boldsymbol{s}^T\boldsymbol{x}~|~\boldsymbol{x}\in S_1\rbrace \geq \sup\lbrace\boldsymbol{s}^T\boldsymbol{x}~|~\boldsymbol{x}\in S_2\rbrace \tag{3-12} \label{3.12e}
さらに、$S_1$ と $S_2$ が閉集合で少なくとも一方が有界なら、以下の条件を満たす $\boldsymbol{s}\in\mathbb{R}^n$ が存在する。
\inf\lbrace\boldsymbol{s}^T\boldsymbol{x}~|~\boldsymbol{x}\in S_1\rbrace > \sup\lbrace\boldsymbol{s}^T\boldsymbol{x}~|~\boldsymbol{x}\in S_2\rbrace \tag{3-13} \label{3.12f}
分離定理より、線形計画問題などの最適性条件において重要な役割を果たすファルカスの補題が得られる。
定行列 $A\in\mathbb{R}^{m\times n}$ と定ベクトル $\boldsymbol{b}\in\mathbb{R}^m$ に対して、次のいずれか一方のみが必ず成り立つ。
(a) $A\boldsymbol{x}=\boldsymbol{b},~\boldsymbol{x}\geq\boldsymbol{0}$ を満たす $\boldsymbol{x}\in\mathbb{R}^n$ が存在する。
(b) $A^T\boldsymbol{y}\geq \boldsymbol{0},~\boldsymbol{b}^T\boldsymbol{y}<0$ を満たす $\boldsymbol{y}\in\mathbb{R}^m$ が存在する。
3.4 ルシャンドル変換と共役関数
関数 $f$ に対して、以下で定義される関数 $f^* $ を $f$ の共役関数と呼ぶ。また、写像 $f→f^* $ をルシャンドル変換と呼ぶ。
f^*(\boldsymbol{s})= \sup\lbrace\boldsymbol{s}\cdot\boldsymbol{x}-f(\boldsymbol{x})~|~\boldsymbol{x}\in\mathbb{R}^n\rbrace \tag{3-14} \label{3.14}
普通に $\max_{\boldsymbol{x}}\lbrace\boldsymbol{s}\cdot\boldsymbol{x}-f(\boldsymbol{x})\rbrace$ を考えると分かりやすい。
$\nabla(\boldsymbol{s}\cdot\boldsymbol{x}-f(\boldsymbol{x}))=\boldsymbol{s}-\nabla f(\boldsymbol{x})=\boldsymbol{0}$ すなわち $\nabla f(\boldsymbol{x})=\boldsymbol{s}$ を満たす $\boldsymbol{x}$ が$f^* (\boldsymbol{s})$ の値。
幾何的には、勾配 $\boldsymbol{s}$ の $f(\boldsymbol{x})$ の接平面と $z$ 軸との交点が $-f^* (\boldsymbol{s})$。
凸関数と劣微分の間には、以下のような関係がある。次の3つの条件は互いに等価。
(a) $\boldsymbol{s}\in\partial f(\boldsymbol{x})$
(b) $f(\boldsymbol{x})+f^* (\boldsymbol{s})=\boldsymbol{s}\cdot\boldsymbol{x}$
(c) $\boldsymbol{x}\in\partial f^* (\boldsymbol{s})$
3.5 最適性条件
以下の問題を考える。
\begin{align}
&\min &f(\boldsymbol{x}) \\
&s.t. &\boldsymbol{x}\in S
\end{align} \tag{3-15} \label{3.24}
$f$ が微分可能とする。点 $\bar{\boldsymbol{x}}\in S$ が問題 $(\ref{3.24})$ の局所最適解ならば、以下が成立する。そのような $\bar{\boldsymbol{x}}$ を停留点という。
-\nabla f(\boldsymbol{x})\in N_S(\bar{\boldsymbol{x}}) \tag{3-16} \label{3.25}
以下のイメージ。制約条件が微分可能な場合は、法線錐 $N_S(\boldsymbol{x})$ が制約条件の勾配の1次結合で表せる範囲であることであり、KKT条件と一致することが分かる。
3.6 双対問題
3.6.1 Fenchel双対性
$f, g$ が閉真凸関数、$A$ を定行列としたとき、以下の凸計画問題を考える。
(P_F):~~~~\min_{\boldsymbol{x}}~f(\boldsymbol{x})+g(A\boldsymbol{x}) \tag{3-17} \label{3.25b}
このとき、以下の最大化問題をFenchel双対問題という。これも凸計画問題。
(D_F):~~~~\max_{\boldsymbol{w}}~-f^*(A^T\boldsymbol{w})-g^*(-\boldsymbol{w}) \tag{3-18} \label{3.25c}
以下の命題が成り立つ。
問題($P_F$)と問題(D_F)の双方に最適解が存在して以下が成り立つことを仮定する。
-\infty <\min (P_F)=\max (D_F)<\infty \tag{3-19} \label{3.30b}
このとき、$\bar{\boldsymbol{x}}\in\mathbb{R}^n$ および $\bar{\boldsymbol{w}}\in\mathbb{R}^m$ が問題($P_F$)と問題($D_F$)の最適解であるための必要十分条件は、以下が成り立つことである。
\begin{align}
A^T\bar{\boldsymbol{w}}\in\partial f(\bar{\boldsymbol{x}}) \\
-\bar{\boldsymbol{w}}\in\partial g(A\bar{\boldsymbol{x}})
\end{align} \tag{3-20} \label{3.30c}
3.6.2 Lagrange双対性
以下の問題を考える。
\begin{align}
&\min &f(\boldsymbol{x}) \\
&s.t. &g_i(\boldsymbol{x})\leq 0,~~~~~&i=1,\cdots,m \\
&&h_l(\boldsymbol{x})=0,~~~~~&l=1,\cdots,r
\end{align} \tag{3-21} \label{3.34b}
以下のとおりラグランジュ関数を定義。
L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\mu})=\left\{
\begin{array}{ll}
f(\boldsymbol{x})+\sum_{i=1}^{m}\lambda_ig_i(\boldsymbol{x})+\sum_{l=1}^{r}\mu_l h_l(\boldsymbol{x}) &\mathrm{if}~~\boldsymbol{\lambda}\geq\boldsymbol{0} \\
-\infty &\mathrm{otherwise}
\end{array}
\right. \tag{3-22} \label{3.35c}
定義より、以下が成り立つ。
\sup_{\boldsymbol{\lambda}}\lbrace L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\mu}~|~\boldsymbol{\lambda}\in\mathbb{R}^m)\rbrace=\left\{
\begin{array}{ll}
f(\boldsymbol{x}) &\mathrm{if}~~g_i(\boldsymbol{x})\leq 0 \\
\infty &\mathrm{otherwise}
\end{array}
\right. \tag{3-23} \label{3.32b}
そのため、問題($\ref{3.34b}$)は、以下の問題と等価である。
(P_L):~~~~~\min_{\boldsymbol{x}}\sup_{\boldsymbol{\lambda}}\lbrace L(\boldsymbol{x}, \boldsymbol{\lambda},\boldsymbol{\mu})~|~\boldsymbol{\lambda}\in\mathbb{R}^m\rbrace \tag{3-24} \label{3.32c}
これに対して、最小化と最大化の順序を入れ替えた以下の問題を考える。この問題を元の問題($D_L$)のラグランジュ双対問題という。
(D_L):~~~~~\max_{\boldsymbol{\lambda}}\inf_{\boldsymbol{x}}\lbrace L(\boldsymbol{x}, \boldsymbol{\lambda},\boldsymbol{\mu})~|~\boldsymbol{\lambda}\in\mathbb{R}^m\rbrace \tag{3-25} \label{3.33}
これらの問題に対して、
\sup_{\boldsymbol{\lambda}} L(\boldsymbol{x}, \boldsymbol{\lambda},\boldsymbol{\mu})\geq L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\mu})\geq \inf_{\boldsymbol{x}} L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\mu}) \tag{3-26} \label{3.33b}
が成り立つことから、主問題とラグランジュ双対問題の間には以下のとおり弱双対性が成り立つ。
\inf (P_L)\geq\sup (D_L) \tag{3-27} \label{3.34}
以下では等式制約を省いて議論する。鞍点定理が成り立つ。鞍点とは、$L(\bar{\boldsymbol{x}},\boldsymbol{\lambda})\leq L(\bar{\boldsymbol{x}},\bar{\boldsymbol{\lambda}})\leq L(\boldsymbol{x},\bar{\boldsymbol{\lambda}})$ が成り立つ点 $(\bar{\boldsymbol{x}},\bar{\boldsymbol{\lambda}})$ である。双対ギャップが0の点は鞍点であることと、その逆を主張している。
点 $(\bar{\boldsymbol{x}},\bar{\boldsymbol{\lambda}})$ において、$L(\bar{\boldsymbol{x}},\bar{\boldsymbol{\lambda}})$ は有限であるとする。このとき、$(\bar{\boldsymbol{x}},\bar{\boldsymbol{\lambda}})$ が $L$ の鞍点であるための必要十分条件は、$\bar{\boldsymbol{x}}$ および $\bar{\boldsymbol{\lambda}}$ がそれぞれ($P_L$)および($D_L$)の最適解であり $\min (P_L)=\min (D_L)$ が成り立つことである。
また、以下の命題も成り立つ。微分可能な凸計画問題において、ラグランジュ双対問題の最適解は主問題の下限を定義することを主張している。
主問題($P_L$)において、目的関数 $f$ と制約関数 $g_1,\cdots,g_m$ が微分可能な凸関数であるとする。さらに、$\inf (P_L)$ が有限でSlater制約想定が満たされるとする。このとき、双対問題($D_L$)に最適解が存在し、$\inf (P_L)=\max (D_L)$ が成立する。
ラグランジュ双対問題の $\inf\lbrace L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\mu}~|~\boldsymbol{x}\in\mathbb{R}^n)$ が扱いやすい形に書きくだせるかどうかは主問題の性質に依存する。下限値を厳密に求める代わりに1次の最適性条件を用いて得られる双対問題が、以下のウルフ双対問題である。
3.6.3 Wolfe双対問題
問題 ($\ref{3.34b}$) に対して以下の問題をウルフ双対問題という。
\begin{align}
&\min &L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\mu}) \\
&s.t. &\nabla_{\boldsymbol{x}} L(\boldsymbol{x}, \boldsymbol{\lambda},\boldsymbol{\mu})=\boldsymbol{0} \\
&&\boldsymbol{\lambda}\geq\boldsymbol{0},~~\boldsymbol{\mu}\geq\boldsymbol{0}
\end{align} \tag{3-28} \label{3.35b}
ラグランジュ双対問題では変数が $\boldsymbol{\lambda}$ のみであったのに対して、ウルフ双対問題では主問題の変数 $\boldsymbol{x}$ も変数として含む。
また、ウルフ双対問題はFenchel双対問題やラグランジュ双対問題のような対称性を持たない。
凸計画問題では、主問題とウルフ双対問題との間に双対性が成り立つ。
主問題 ($\ref{3.34b}$) において、$f, g_1,\cdots,g_m$ が連続微分可能な凸関数であり、Slater制約想定が満たされ、かつ最適解 $\bar{\boldsymbol{x}}$ が存在するものとする。このとき、KKT条件を満たす $(\bar{\boldsymbol{x}},\bar{\boldsymbol{\lambda}})$ はウルフ双対問題 ($\ref{3.35b}$) の最適解であり、主問題と双対問題の最適値は一致する。