連続最適化(2)制約付き最適化

講義概要

等式制約付き最適化問題
不等式制約付き最適化問題

制約なし最適化問題への変換
双対問題

まとめ

制約付き最適化問題(constrained optimization problem) $\mathcal{X}\subset\mathbb{R}^d$ 上に定義される関数 $f:\mathcal{X}\rightarrow\mathbb{R}$ の最小値を求める。
$$ \begin{aligned} \underset{\mathbf{x}\in\mathcal{X}}{\text{minimization : }}&f(\mathbf{x})\\ \text{subject to : }&g(\mathbf{x})=\mathbf{0}\\ &h(\mathbf{x})\leq\mathbf{0} \end{aligned} $$
- "subject to"は、「…を条件として」 という意味。
- $g_i,h_i$ は互いに一次独立(linearly independent)であると仮定。
実行可能解(feasible solution)：全ての制約条件を満たす $\mathbf{x}$
凸最適化問題(convex optimization problem)：関数 $f$ が凸、集合 $\mathcal{X}$ が凸、制約条件 $\mathbf{g},\mathbf{h}$ が凸であれば、最適値が一意に定まる。

※ 以下、凸最適化問題を考える。

等式制約付き最適化問題

等式制約付き最適化問題
$$ \begin{aligned} \underset{\mathbf{x}\in\mathcal{X}}{\text{minimization : }}&f(\mathbf{x})\\ \text{subject to : }&g(\mathbf{x})=\mathbf{0}\\ \end{aligned} $$
$\mathbf{x}_k$ に設定して、勾配法や準ニュートン法などで以下の$$\mathbf{x}_{k+1} = \underset{\mathbf{x}\in\mathcal{X}}{\text{argmin}}f(\mathbf{x}) + c_k\|\mathbf{g}(x)\|^2$$

$c_k$ の値を徐々に増やしていく。

$$0 < c_1 < c_2 < \cdots$$

ラグランジュ未定乗数法

詳しくはラグランジュ未定乗数法に記載されているので、ここでは具体例を紹介する。

問題

$$ \begin{aligned} \underset{\mathbf{x}\in\mathcal{X}}{\text{min : }}&3x^2 + 2y^2\\ \text{subject to : }&x+y=1\\ \end{aligned} $$

解答

ラグランジュ関数は、

$$L(x,y,\lambda) = 3x^2 + 2y^2 + \lambda(x+y-1)$$

となるから、

$$ \begin{aligned} \frac{\partial L}{\partial x} &= 6x+\lambda=0 &\therefore x = -\frac{1}{6}\lambda\\ \frac{\partial L}{\partial y} &= 4y+\lambda=0 &\therefore y = -\frac{1}{4}\lambda\\ \frac{\partial L}{\partial \lambda} &= x+y-1=0 &\therefore \lambda = -\frac{12}{5}\\ \end{aligned} $$

よって、$(x,y) = (0.4,0.6)$

ラグランジュ双対問題

これも、詳しくはラグランジュ双対問題に記載されているので、ここでは具体例を紹介する。

問題

$$ \begin{aligned} \underset{\mathbf{x}\in\mathcal{X}}{\text{min : }}&3x^2 + 2y^2\\ \text{subject to : }&x+y=1\\ \end{aligned} $$

解答

ラグランジュ関数は、

$$L(x,y,\lambda) = 3x^2 + 2y^2 + \lambda(x+y-1)$$

となるから、

よって、これらを $L(x,y,\lambda)$ に代入して、

$$\omega(\lambda) = \underset{x,y\in\mathbb{R}}{\inf}L(x,y,\lambda) = -\frac{5}{24}\lambda^2-\lambda$$

したがって、 $\underset{\lambda\in\mathbb{R}}{\text{argmax}}\omega(\lambda) = -\frac{12}{5}\Longrightarrow(x,y) = (0.4,0.6)$

双対変数の最適化

上の問題では、双対変数 $\lambda$ の最適化問題を解析的に解けたが、解析的に解くことができない問題もある。その場合に使うのが双対上昇法や乗数法と呼ばれる双対変数の勾配上昇を行う手法である。

手法	数式	解説
双対上昇法	$$\begin{aligned}\mathbf{x}_{k+1} &= \underset{\mathbf{x}\in\mathcal{X}}{\text{argmin}}L(\mathbf{x},\boldsymbol{\lambda}_{k})\\\boldsymbol{\lambda}_{k+1} &= \boldsymbol{\lambda}_k + \varepsilon_k\nabla\omega(\mathbf{\boldsymbol{\lambda}}_k) \\&= \boldsymbol{\lambda}_k + \varepsilon_k\mathbf{g}(\mathbf{x}_{k+1})\end{aligned}$$	適当な初期値から，ラグランジュ関数の最小化と双対変数の勾配上昇を交互に実行
乗数法	$$\begin{aligned}\mathbf{x}_{k+1} &= \underset{\mathbf{x}\in\mathcal{X}}{\text{argmin}}L_c(\mathbf{x},\boldsymbol{\lambda}_{k})\\\boldsymbol{\lambda}_{k+1} &= \boldsymbol{\lambda}_k + c\nabla\omega(\mathbf{\boldsymbol{\lambda}}_k) \\&= \boldsymbol{\lambda}_k + c\mathbf{g}(\mathbf{x}_{k+1})\end{aligned}$$	適当な初期値から，拡張ラグランジュ関数の最小化と双対変数の勾配上昇を交互に実行

なお、拡張ラグランジュ関数(augmented Lagrangian)は、以下で表される関数で、二次の項を加えることで凸性を増している。

$$L_c(\mathbf{x},\boldsymbol{\lambda}) = f(\mathbf{x}) + \boldsymbol{\lambda}^T\mathbf{g}(\mathbf{x}) + \frac{c}{2}\|\mathbf{g}(\mathbf{x})\|^2$$

※実装はレポート課題3に記載。

不等式制約付き最適化問題

$$ \begin{aligned} \underset{\mathbf{x}\in\mathcal{X}}{\text{minimization : }}&f(\mathbf{x})\\ \text{subject to : }&h(\mathbf{x})\leq\mathbf{0}\\ \end{aligned} $$

実行可能解 $\mathbf{x}$ において $h_i(\mathbf{x}) = 0$ の時、この制約を有効制約(active constraint)と呼ぶ。
実行可能解 $\mathbf{x}$ においてそれ以外の時、この制約を無効制約(inactive constraint)と呼ぶ。

制約なし最適化問題への変換

障壁法(barrier method)
- 初期値を $\mathbf{x}_k$ に設定して、勾配法や準ニュートン法などで以下の制約なし最適化問題を解く。
  $$\mathbf{x}_{k+1} = \underset{\mathbf{x}\in\mathcal{X}}{\text{argmin}}f(\mathbf{x}) - c_k\log(-h(\mathbf{x}))$$
- $c_k$ の値を徐々に減らしていく。
- 途中の解 $\mathbf{x}_{k+1}$ が常に $h(\mathbf{x}_{k+1})\leq0$ を満たす（つまり、実行可能領域の内側にある）ことから、内点法(interior-point method)ともよばれる。
- $c_k$ の決め方が難しい。
罰則法(penalty method)
- 初期値を $\mathbf{x}_k$ に設定して、勾配法や準ニュートン法などで以下の制約なし最適化問題を解く。
  $$\mathbf{x}_{k+1} = \underset{\mathbf{x}\in\mathcal{X}}{\text{argmin}}f(\mathbf{x}) + c_k\max(0,h(\mathbf{x}))^2$$
- $c_k$ の値を徐々に増やしていく。
- 途中の解 $\mathbf{x}_{k+1}$ が一般に $h(\mathbf{x}_{k+1})>0$ を満たす（つまり、実行可能領域の外側にある）ことから、外点法(exterior-point method)ともよばれる。
- $c_k$ の決め方が難しい。
射影勾配法(projected gradient method)
- 勾配降下（$\tilde{\mathbf{x}}_{k+1} = \mathbf{x}_k-\varepsilon_k\nabla f(\mathbf{x}_k)$）と実行可能領域への射影（$\mathbf{x}_{k+1} = \mathbf{P}_k\tilde{\mathbf{x}}_{k+1}$）を繰り返す。
- まとめると
  $$\mathbf{x}_{k+1} = \mathbf{P}_k\left(\mathbf{x}_k - \varepsilon_k\nabla f(\mathbf{x}_k)\right)$$
- 射影が簡単に計算できる時、効率が良い。

双対問題

詳しくはラグランジュ未定乗数法に記載。

まとめ

制約付き最適化問題：
$$ \begin{aligned} \underset{\mathbf{x}\in\mathcal{X}}{\text{minimization : }}&f(\mathbf{x})\\ \text{subject to : }&g(\mathbf{x})=\mathbf{0}\\ &h(\mathbf{x})\leq\mathbf{0} \end{aligned} $$
ラグランジュ関数：
$$L\left(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\mu}\right) = f(\mathbf{x}) + \boldsymbol{\lambda}^Tg(\mathbf{x}) + \boldsymbol{\mu}^Th(\mathbf{x})$$
双対問題：
$$ \begin{aligned} \underset{\boldsymbol{\lambda,\mu},\ \mathbf{x}\in\mathcal{X}}{\text{maximization : }}&L\left(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\mu}\right)\\ \text{subject to : }&\boldsymbol{\mu}\geq\mathbf{0}\\ \end{aligned} $$
KKT条件：
$$ \begin{aligned} \begin{cases} \nabla_{\mathbf{x}}L\left(\mathbf{x}^{\ast},\boldsymbol{\lambda}^{\ast},\boldsymbol{\mu}^{\ast}\right) = \mathbf{0}\\ \nabla_{\boldsymbol{\lambda}}L\left(\mathbf{x}^{\ast},\boldsymbol{\lambda}^{\ast},\boldsymbol{\mu}^{\ast}\right) = \mathbf{0} & \boldsymbol{\mu}^{\ast}\geq\mathbf{0}\\ \nabla_{\boldsymbol{\mu}}L\left(\mathbf{x}^{\ast},\boldsymbol{\lambda}^{\ast},\boldsymbol{\mu}^{\ast}\right) \leq \mathbf{0} & \mu_i^{\ast}h_i(\mathbf{x}^{\ast}) = 0,\ \forall i \end{cases} \end{aligned} $$

hidden

Published

Oct 17, 2019

Last Updated