最適化問題の分類とその解法等をまとめてみました。
第1弾では最適化問題の分類と非線形最適化を扱います。
自分用に作っているので、第三者的に分かりづらい可能性がある点、厳密性に欠く部分がある可能性がある点は悪しからず。
1. 最適化問題の分類
以下のように分類される (穴井・斉藤 (2015)をもとに作成)。
2. 非線形計画
凸とも限らない・線形とも限らない一般的な連続最適化問題を扱う理論と解法。
\begin{array}[lll]
&\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{array} \tag{2-1} \label{2.1}
2.1.無制約非線形計画
制約条件がない場合。
\min f(\boldsymbol{x}) \tag{2-2} \label{2.2}
2.1.1. 最適性条件
2.1.1.1. 1次の最適性条件
\nabla f(\boldsymbol{x})=\boldsymbol{0} \tag{2-3}
2.1.1.2. 2次の最適性必要条件
\nabla f(\boldsymbol{x})=\boldsymbol{0} \land \nabla^2 f(\boldsymbol{x}) \succeq O \tag{2-4}
2.1.1.3. 2次の最適性必要条件
\nabla f(\boldsymbol{x})=\boldsymbol{0} \land \nabla^2 f(\boldsymbol{x}) \succ O \tag{2-5}
2.1.2. 解法
2.1.2.1. 最急降下法
現在の点$\boldsymbol{x}$を以下の更新公式にしたがって点$\boldsymbol{x}_{k+1}$に更新する。
\begin{array}
~\boldsymbol{x}_{k+1}=\boldsymbol{x}_k +\alpha_k \boldsymbol{d}_k \\
\boldsymbol{d}_k = -\nabla f(\boldsymbol{x}_k)
\end{array} \tag{2-6}
ステップ幅$\alpha_k$は、直線探索 ($l_k(\alpha)=f(\boldsymbol{x}_k+\alpha\boldsymbol{d}_k)$を最小化する$\alpha$を求める) によって決定する。ただし厳密な最適解を求めることは難しいため、Armijoの条件やWolfeの条件といったより弱い条件が用いられる。直線探索の実装にはバックトラック法がよく用いられる。バックトラック法とは、まず大きめに$\alpha$を選び、徐々に$\alpha$を小さくして条件が最初に満たされるところをステップ幅$\alpha_k$とする方法である。
大域的収束性が保証される (大域的最適解への収束が保証されているわけではないため注意)。
2.1.2.2. Netwon法
現在の点$\boldsymbol{x}$を以下の更新公式にしたがって点$\boldsymbol{x}_{k+1}$に更新する。
\begin{array}
~\boldsymbol{x}_{k+1}=\boldsymbol{x}_k +\alpha_k \boldsymbol{d}_k \\
\nabla^2 f(\boldsymbol{x}_k)\boldsymbol{d}_k = -\nabla f(\boldsymbol{x}_k)
\end{array} \tag{2-7}
ステップ幅は$\alpha_k=1$とすることが多い。
以下で表される2次近似を最小化する方向、すなわち $\nabla f_k^Q(\boldsymbol{d})=\boldsymbol{0}$ が成り立つ $\boldsymbol{d}$ 方向に降下している。
f(\boldsymbol{x}_k+\boldsymbol{d})\approx f_k^Q(\boldsymbol{d})=f(\boldsymbol{x}_k)+\nabla f(\boldsymbol{x}_k)\cdot\boldsymbol{d}+\frac{1}{2}\nabla^2 f(\boldsymbol{x}_k)\boldsymbol{d}\cdot\boldsymbol{d}
ヘッセ行列$\nabla^2 f(\boldsymbol{x})$が正定値でないと大域的収束性がないという問題がある。
2.1.2.3. 準Newton法
Newton法のヘッセ行列$\nabla^2 f(\boldsymbol{x}_k)$を適当な正定値対称行列$B_k$に置き換える。
\begin{array}
~\boldsymbol{x}_{k+1}=\boldsymbol{x}_k +\alpha_k \boldsymbol{d}_k \\
B_k\boldsymbol{d}_k = -\nabla f(\boldsymbol{x}_k)
\end{array} \tag{2-8}
ステップ幅$\alpha_k$は、直線探索によって求める。
適当な正定値対称行列$B_k$は、BFGS公式やDFP公式のB公式などによって更新する場合や、逆行列$B_k^{-1}$を直接更新する場合 (H公式) がある。
大域的収束性が保証される。
2.1.2.4. 信頼領域法
更新量$\boldsymbol{s}_k$を、$f$の2次近似に関する以下の2次計画問題を解くことで求める。ただし、$\Delta_k>0$は信頼半径と呼ばれるハイパラで、2次近似がよい近似になる範囲を示す。
\begin{array}[ll]
&\min &f_k^Q(\boldsymbol{s})=f(\boldsymbol{x}_k)+\nabla f(\boldsymbol{x}_k) \cdot \boldsymbol{s}+\frac{1}{2}B_k\boldsymbol{s}\cdot\boldsymbol{s} \\
s.t. &\lVert\boldsymbol{s}\rVert \leq \Delta_k
\end{array} \tag{2-10} \label{2.44}
定数$c_1\in(0,1)$について、$\boldsymbol{s}_k$が以下の条件を満たすか考える (更新により関数値が十分に減少するか否かを調べている)。
f(\boldsymbol{x}_k+\boldsymbol{s}_k)\leq f(\boldsymbol{x}_k)+c_1(f_k^Q(\boldsymbol{s}_k)-f\left(\boldsymbol{x}_k)\right)
満たす場合、現在の点$\boldsymbol{x}$を以下の更新公式にしたがって点$\boldsymbol{x}_{k+1}$に更新する。
\boldsymbol{x}_{k+1}=\boldsymbol{x}_k +\boldsymbol{s}_k \tag{2-11} \label{2.45}
満たさない場合、$\Delta_k$をより小さい値に更新する。
大域的収束性が保証される。
2.2. 等式制約下での最適化
等式制約のみがある場合。
\begin{array}[lll]
&\min &f(\boldsymbol{x}) \\
s.t. &h_l(\boldsymbol{x})=0, &l=1,\cdots,r
\end{array} \tag{2-12} \label{2.48}
2.2.1. 最適性条件
Lagrangeの未定乗数法。最適解においては、$\nabla f(\boldsymbol{x})$は$\nabla h_1(\boldsymbol{x}),\cdots,\nabla h_l(\boldsymbol{x})$の1次結合で表される。1次結合で表せない場合、$h_k(\boldsymbol{x})=0$ に沿って少し進めば、解を改善できてしまう。
\begin{eqnarray}
&L(\boldsymbol{x}, \boldsymbol{\mu})=f(\boldsymbol{x})-\sum_{l=1}^r \mu_lh_l(\boldsymbol{x}) \\
&\frac{\partial L}{\partial \boldsymbol{\mu}}=\boldsymbol{0} \\
&\frac{\partial L}{\partial \boldsymbol{x}}=\boldsymbol{0}
\end{eqnarray} \tag{2-13} \label{2.54}
2.3. 不等式制約下での最適化
式(${\ref{2.1}}$)に示した一般的な形。下に再掲。
\begin{array}[lll]
&\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{array} \tag{2-14} \label{2.1a}
2.3.1. KKT条件
1次独立制約想定・Slaterの制約条件・Mangasarian-Fromovitz制約想定などのもとでの議論。
\begin{eqnarray}
&L(\boldsymbol{x},\boldsymbol{\lambda}, \boldsymbol{\mu})=f(\boldsymbol{x})+\sum_{i=1}^{m} \lambda_i g_i(\boldsymbol{x})+\sum_{l=1}^r \mu_lh_l(\boldsymbol{x}), \\
&\nabla L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\mu})=\boldsymbol{0}, \\
&g_i(\boldsymbol{x})\leq 0,~~\lambda_i \geq 0,~~\lambda_i g_i(\boldsymbol{x})=0,~~~~~i=1,\cdots,m, \\
&h_l(\boldsymbol{x})=0,~~~~~l=1,\cdots,r
\end{eqnarray} \tag{2-15} \label{2.60}
最適解においては、目的関数の勾配は、有効な不等式制約の勾配と等式制約の勾配との1次結合で表される。非有効な場合 ($g_i(\boldsymbol{x})<0$の場合) は$\lambda_i=0$とすることで、ラグランジュ関数に組み込まれないようになっている。
2.3.2. 解法
2.3.2.1. ペナルティ法
目的関数に制約のペナルティ関数 (制約が満たされる場合は0をとり、満たされない場合には正の値を取る関数) を加えた関数 $\phi_{\rho}(\boldsymbol{x})$ を考える。
\phi_{\rho}(\boldsymbol{x})=f(\boldsymbol{x})+\rho\sum_{i=1}^{m}\left(\max\left\{g_i(\boldsymbol{x}),0\right\}\right)^2+\rho\sum_{l=1}^r h_l(\boldsymbol{x})^2 \tag{2-16} \label{2.68}
各反復では固定した $\rho$ に対し式(${\ref{2.68}}$)を目的関数とする無制約最適化問題を解き、反復ごとに$\rho$の値を徐々に大きくしていく。
$\rho$が有限な限り正確な最適解は得られない。
$\rho$が大きくなるにしたがって$\phi_{\rho}$のヘッセ行列の条件数が非常に大きくなり、無制約最適化問題を解くことが困難になることが多い。これを解決したのが乗数法。
下の図は、以下の問題にペナルティ法を用いた例である。
\begin{array}
&\min &x+1 \\
s.t. &x\geq 0 \\
&\phi_{\rho}(x)=x+1+\rho(\max\lbrace -x,0\rbrace)^2
\end{array}
2.3.2.2. バリア関数法
目的関数に制約のバリア関数 (制約が満たされる点では有限の値をとり、制約の境界で無限大になる関数) を加えた関数 $\psi_\nu(\boldsymbol{x})$ を考える。
\psi_\nu(\boldsymbol{x})=f(\boldsymbol{x})-\nu\sum_{i=1}^{m}\log(-g_i(\boldsymbol{x})) \tag{2-17} \label{2.69}
下の問題の実行可能領域の内点を初期点として、各反復では固定した $\nu>0$ に対して $\psi_\nu(\boldsymbol{x})$ の無制約最小化問題を解き、反復ごとに $\nu$ の値を徐々に小さくすることで、最終的にもとの問題の最適解を得る。
初期点として必要な実行可能領域の内点が必ずしも容易に得られないことや、実行可能領域の境界に近づくにつれて $\psi_\nu(\boldsymbol{x})$ が悪条件となり解くことが難しいなどの欠点がある。主双対内点法が洗練され再び注目を集めている。
2.3.2.3. 逐次2次計画法
各反復において以下の2次最適化問題 (部分問題) を解き、その最適解 $\Delta\boldsymbol{x}$ を探索方向とする。$B_k$ はラグランジュ関数のヘッセ行列、あるいはその適当な近似行列。
\begin{array}[ll]
&\min &\frac{1}{2}B_k\Delta\boldsymbol{x}\cdot\Delta\boldsymbol{x}+\nabla f(\boldsymbol{x}_k)\cdot\Delta\boldsymbol{x} \\
s.t. &g_i(\boldsymbol{x}_k)+\nabla g_i(\boldsymbol{x}_k)\cdot\Delta\boldsymbol{x}\leq0, &i=1,\cdots,m \\
&h_l(\boldsymbol{x}_k)+\nabla h_l(\boldsymbol{x}_k)\cdot\Delta\boldsymbol{x}=0, &l=1,\cdots,r
\end{array} \tag{2-18} \label{2.71}
部分問題(${\ref{2.71}}$)のKKT条件が、もとの問題のKKT条件を $(\boldsymbol{x}_k, \boldsymbol{\lambda_k}, \boldsymbol{\mu}_k)$ において近似したものとなることが理論的根拠。
なお、ステップ幅 $\alpha_k$ はメリット関数を用いた直線探索によって決定する。メリット関数には、ペナルティ関数を用いた関数がしばしば用いられる。
2.3.2.4. 主双対内点法
$k$ 回目の探索において、以下の非線形方程式を適当な精度 (多くは1次近似) で満たす近似解 $(\Delta\boldsymbol{x}_k, \Delta\boldsymbol{\lambda}_k, \Delta\boldsymbol{\mu}_k)$ を探索方向とする。直線探索でステップ幅を求めて解を更新したら、$k+1$ 回目の反復では $\nu>0$ を小さい値に更新して同様の探索を行う。バリア関数の軌跡を近似的に辿るイメージ。
\begin{array}
~\nabla f(\boldsymbol{x}) - \boldsymbol{\lambda} + \sum_{i=1}^{r}\mu_l ~
\nabla h_l(\boldsymbol{x})=\boldsymbol{0} \\
h_l(\boldsymbol{x})=0, &l=1,\cdots,r \\
x_j\lambda_j=\nu,&j=1,\cdots,n \\
x_j>0,~~~~\lambda_j>0, &j=1,\cdots,n
\end{array} \tag{2-19} \label{2.75}
理論的根拠は以下。元の問題(${\ref{2.1a}}$)にスラック変数などを導入し、等式制約のみの問題に変換する。
\begin{array}[ll]
&\min &f(\boldsymbol{x}) \\
s.t. &h_l(\boldsymbol{x})=0, &l=1,\cdots,r \\
&\boldsymbol{x}\geq\boldsymbol{0}
\end{array} \tag{2-20} \label{2.74}
さらに、非負制約に関してバリア関数を導入し、以下の問題に変換する。
\begin{array}[ll]
&\min &f(\boldsymbol{x})-\nu\sum_{j=1}^{n}\log x_j \\
s.t. &h_l(\boldsymbol{x})=0, &l=1,\cdots,r \\
&\boldsymbol{x}>\boldsymbol{0}
\end{array} \tag{2-21} \label{2.74b}
この問題のKKT条件が、解くべき非線形方程式(${\ref{2.75}}$)である。$\nu→0$のとき、元の問題のKKT条件と一致する。
線形計画問題・半正定値計画問題に対しては、大域的最適解への収束が保証された多項式時間アルゴリズムである。一般の非線形計画問題に対しては、局所最適解への大域的収束性と局所的に十分速い収束のみが理論的に保証されている。
最適解の近くでもそれほど悪条件とならないことが、内点法からの改善点。
2.3.2.5. 乗数法 (拡張ラグランジュ関数法)
スラック変数等の導入により等式制約のみとした問題を考える。$k$ 回目の反復において、以下のとおり定義した拡張ラグランジュ関数の無制約最小化問題を、ラグランジュ乗数 $\boldsymbol{\mu}_k$ を固定して解いて解 $\boldsymbol{x}_k$ を得る。
L_{\sigma}(\boldsymbol{x}, \boldsymbol{\mu})=f(\boldsymbol{x})+\sum_{l=1}^{r}\mu_lh_l(\boldsymbol{x})+\frac{\sigma}{2}\sum_{l=1}^{r}h_l(\boldsymbol{x})^2 \tag{2-22} \label{2.78}
$k+1$ 回目の反復では $\boldsymbol{\mu}_{k+1}$ を以下のように更新して固定し、再度拡張ラグランジュ関数の無制約最小化問題を解く。
\boldsymbol{\mu}_{k+1}=\boldsymbol{\mu}_k+\sigma\boldsymbol{h}(\boldsymbol{x}_k) \tag{2-23} \label{2.79b}
また、等式制約の残差が1つ前の反復と比べて十分に減少しなかった場合は、$\sigma$ をより大きな値にする。
以下の命題が理論的根拠。十分大きい $\sigma$ をとれば、元の問題の局所最適解を求める問題を、$L_{\sigma}(\boldsymbol{x}, \bar{\boldsymbol{\mu}})$ の極小解を求める問題に変換できると主張している。
点 $\bar{\boldsymbol{x}}$ を元の問題の局所最適解とし、対応するラグランジュ乗数を $\bar{\boldsymbol{\mu}}$ とおく。$\bar{\boldsymbol{x}}$ において線型独立制約想定が成り立ち、$\bar{\boldsymbol{x}}$ と $\bar{\boldsymbol{\mu}}$ が2次の最適性条件を満たすことを仮定する。このとき、実数 $\hat{\sigma}>0$ が存在して、$\sigma \geq\hat{\sigma}$ を満たす任意の $\sigma$ に対して $\bar{\boldsymbol{x}}$ は $L_{\sigma}(\boldsymbol{x}, \bar{\boldsymbol{\mu}})$ の極小解である。
なお、式(${\ref{2.79b}}$)は、拡張ラグランジュ関数の1次の最適性条件と元の問題の1次の最適性条件を比較することで得られる。$\boldsymbol{\mu}_k$ を上の命題の $\bar{\boldsymbol{\mu}}$ に近づけるための操作。
2.4. 変分不等式
KKT条件は相補性問題の形で表されるため、相補性問題や変分不等式問題は最適化問題を一般化した問題とみなせる。
2.4.1. 相補性問題
以下の条件を満たすベクトル $\boldsymbol{x}$ を求める問題。
\boldsymbol{x}\geq\boldsymbol{0},~~~~~\boldsymbol{F}(\boldsymbol{x})\geq\boldsymbol{0}~~~~~\boldsymbol{F}(\boldsymbol{x}) \cdot\boldsymbol{x}=0 \tag{2-24} \label{2.87}
$\boldsymbol{x}\geq\boldsymbol{0}$ より、3つ目の条件は、以下の条件と等価。
F_j(\boldsymbol{x})x_j=0,~~~~~j=1, \cdots,n \tag{2-25} \label{2.87b}
以下のように記述することもある。
\boldsymbol{0}\leq\boldsymbol{x}\perp\boldsymbol{F}(\boldsymbol{x})\geq\boldsymbol{0} \tag{2-26} \label{2.87c}
$\boldsymbol{F}$ が線形のとき線形相補性問題、そうでないとき非線形相補性問題と呼ぶ。
一部の変数のみに非負制約と相補性条件を課す問題を混合相補性問題と呼ぶ。非線形計画問題のKKT条件は、$(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu})$ を変数とする混合相補性問題である。また、線形計画問題や凸2次計画問題の最適性条件は、(混合) 線形相補性問題である。
2.4.2. 変分不等式問題
以下の条件を満たす $\boldsymbol{x}$ を求める問題。
\boldsymbol{x}\in S,~~~~~\boldsymbol{F}(\boldsymbol{x}) \cdot(\boldsymbol{y}-\boldsymbol{x})\geq 0~~~~\forall y\in S \tag{2-27} \label{2.91}
$S=K(\boldsymbol{x})$ と書ける場合は凖変分不等式という。さらに $\boldsymbol{F}(\boldsymbol{x})=\boldsymbol{0}$ の場合は条件 $\boldsymbol{x}\in K(\boldsymbol{x})$を満たす $\boldsymbol{x}$、すなわち $K$ の不動点を求める問題に帰着する。
また、$S=\mathbb{R}^n$ の場合は、非線形方程式 $\boldsymbol{F}(\boldsymbol{x})=\boldsymbol{0}$ の解 $\boldsymbol{x}$ を求める問題になる ($\boldsymbol{y}=\boldsymbol{x}-\boldsymbol{F}(\boldsymbol{x})$ を選ぶと、2つ目の条件が $-\boldsymbol{F}(\boldsymbol{x})^T\boldsymbol{F}(\boldsymbol{x})\geq 0$ となるため)。
また、$S= \lbrace \boldsymbol{x}\in\mathbb{R}^n~| ~\boldsymbol{x}\geq\boldsymbol{0} \rbrace$ のとき、$\boldsymbol{x}$ が変分不等式問題 (${\ref{2.91}}$) の解であることと、相補性問題 (${\ref{2.87}}$) の解であることとは、同値である。すなわち、変分不等式問題は相補性問題を一般化した問題。
2.4.3. 方程式への再定式化
以下の条件を満たす関数 $\psi$ を相補性関数と呼び、相補性問題を非線形方程式へ再定式化できる。
\psi(x_j,s_j)=0~~\Leftrightarrow~~ x_j\geq0,~s_j\geq0,~x_js_j=0 \tag{2-28} \label{2.95b}
相補性関数の例としては、以下のフィッシャー・ブアマイスター関数がある。
\psi_{FB}(a,b)=\sqrt{a^2+b^2}-(a+b) \tag{2-29} \label{2.96}
また、閉凸集合 $S$ に対して、$S$ に属する点のうちで点 $\boldsymbol{z}$ からの距離が最小になるものを $\boldsymbol{z}$ の $S$ への射影と呼び、$\boldsymbol{P}_S(\boldsymbol{z})$ で表す。変分不等式問題は、射影を用いて以下のように再定式化できる。
\boldsymbol{x}-\boldsymbol{P}_S(\boldsymbol{x}-\boldsymbol{F}(\boldsymbol{x}))=\boldsymbol{0} \tag{2-30} \label{2.100}
理論的根拠は以下。$S$ が空でない閉凸集合であるとき、任意の点 $\boldsymbol{z}$ に対して $\boldsymbol{P}_S(\boldsymbol{z})$ は一意的に存在し、以下の条件を満たす。
(\boldsymbol{y}-\boldsymbol{P}_S(\boldsymbol{z}))^T(\boldsymbol{P}_S(\boldsymbol{z})-\boldsymbol{z})\geq0~~~~~\forall\boldsymbol{y}\in S \tag{2-31} \label{2.98}
$\boldsymbol{z}=\boldsymbol{x}-\boldsymbol{F}(\boldsymbol{x})$ とおいて、元の変分不等式問題と比べることで導かれる。
相補性問題や変分不等式問題を再定式化することで導かれる非線形方程式は、一般に微分不可能な点を含む。そのため、通常のNewton法を用いることはできず、工夫が必要である。