# 制約付き最適化問題
## 2次の最適性条件
---
## 目次
- 定理9.3 2次の必要条件
- 定理9.4 2次の十分条件
---
等式制約付き最適性問題
$min_{x \in R^n}f(x)~s.t.~g_i(x)=0~~(i=1,\cdots,p)$
Note:
g(x)の式を満たすxの集合の範囲でf(x)の値を最小化することについて考える
ここでp<nを仮定し、f,gは全て微分可能とする
---
### 定理9.1(1次の必要条件)
関数$f,g_1,\cdots,g_p$は1回連続微分可能とする。最適性問題の局所最適解を$x^*\in R^n$とする。また$\nabla g_i(x^*)$は1次独立とする。
---
このとき、$\lambda^*_1,\cdots,\lambda^*_p\in R$が存在して
$\nabla f(x^*)+\Sigma^p_{i=1}\lambda^*_i\nabla g_i(x^*)=0$
$g_i(x^*)=0~i=1,\cdots,p$
が成り立つ。
---
### ラグランジュ乗数
方程式
$\nabla f(x)+\Sigma^p_{i=1}\lambda_i\nabla g_i(x)=0$
$g_i(x)=0~~(i=1,\cdots,p)$
の変数$\lambda=(\lambda_1,\cdots,\lambda_p)\in R^p$をラグランジュ乗数という。
---
## 定理9.3(2次の必要条件)
関数$f,g_1,\cdots,g_p$は2回連続微分可能とする。最適性問題の局所最適解を$x^*\in R^n$とする。
また、制約式の勾配$\nabla g_i(x^*)$は1次独立とし、$\lambda^*_1,\cdots,\lambda^*_p$をラグランジュ乗数とする。
---
さらに部分空間Sを
$S=\left\{y\in R^n|\nabla g_i(x^*)^Ty=0,i=1,\cdots,p\right\}$
とし、行列$L\in R^{n×n}$を
$L=\nabla^2f(x^*)+\Sigma^m_{i=1}\lambda^*_i\nabla^2g_i(x^*)$
とする
---
このとき、任意の$y\in S$に対し
$y^TLy\geq0$
が成り立つ
---
### 定理3.2(制約なし最適化問題の2次の必要条件)
関数$f:R^n\to R$は2回連続微分可能とし$x^*\in R^n$を局所最適解とする。
このとき
$\nabla^2f(x^*)\succeq O$
---
### 定理9.3 証明
実行可能領域に値をとる1変数関数$t\mapsto x(t)$に対してf(x(t))に関する制約なし最適化の2次の必要条件を計算する。
---
関数x(t)は2回微分可能で$x(0)=x^*$とする
このとき
$\nabla^2f(x(0))=\nabla^2f(x^*)\succeq O$
より
$\frac{d^2}{dt^2}f(x(t))|_{t=0}\geq0$
---
ここで
$\frac{d^2}{dt^2}f(x(t))$
$=\frac{dx(t)}{dt}^T\nabla^2f(x(t))\frac{dx(t)}{dt}+\nabla f(x(t))\frac{d^2x(t)}{dt^2}$
---
よりt=0を代入すると
$\frac{dx(0)}{dt}^T\nabla^2f(x^*)\frac{dx(0)}{dt}+\nabla f(x^*)\frac{d^2x(0)}{dt^2}\geq0~~~\cdots(*)$
---
さらに$g_i(x(t))=0$が恒等的に成り立つので、fのときと同様に
$\frac{dx(0)}{dt}^T\nabla^2g(x^*)\frac{dx(0)}{dt}+\nabla g(x^*)\frac{d^2x(0)}{dt^2}=0~~~\cdots(**)$
となる。
---
等式(**)に$\lambda^*_i$を乗じ、不等式(*)を加えると
$\frac{dx(0)}{dt}^T\left(\nabla^2f(x^*)+\Sigma\lambda^*_i\nabla^2g_i(x(*)\right)\frac{dx(0)}{dt}$
$+\left(\nabla f(x^*)+\Sigma\lambda^*_i\nabla g_i(x(*)\right)\frac{d^2x(0)}{dt^2}\geq0$
となる。
---
定理9.1より
$\nabla f(x^*)+\Sigma\lambda^*_i\nabla g(x^*)=0$
なので
$\frac{d}{dt}x(0)^TL\frac{d}{dt}x(0)\geq0$
が成り立つ。
---
また(**)の導出と同様に
$\frac{d}{dt}g_i(x(0))=\nabla g(x^*)\frac{d}{dt}x(0)=0$
となるので
$y^TLy\geq0~~(y\in S)$
---
## 定理9.4(2次の十分条件)
関数$f,g_1,\cdots,g_p$は2回微分可能とする。点$x^*$が$g_i(x^*)=0~~~(i=1,\cdots,p)$を満たし、さらに$\lambda=(\lambda^*_1,\cdots,\lambda^*_p)\in R^p$が存在して
$\nabla f(x^*)+\Sigma^p_{i=0}\lambda^*_i\nabla g_i(x^*)=0$
とする。
---
また、定理9.3で定義されるS,Lに対して$y\in S,y≠0$なら
$y^TLy>0$
とすると、$x^*$は局所最適解
---
### コンパクト
位相空間$(X,O_X)$の部分集合Fは次の条件を満たすときコンパクトという。
Fの任意の開被覆$\{U_λ\}_{λ∈Λ}$から有限個$U_{λ_1},\cdots,U_{λ_r}~~~(λ_i\in Λ)$を適当に選んで$\{U_{λ_1} ,...,U_{λ_r}\}$をFの開被覆とすることができる。
参考文献:[連続性とコンパクト性](http://www.math.nagoya-u.ac.jp/~miyachi/courses/2W11_files/miyachi-2W11-08.pdf)
note:
定義
---
### Bolzano-Weierstrassの定理
ユークリッド空間$R^n$の部分集合Fに対して、次の2つの条件は互いに同値である。
1. Fは有界な閉集合である。
2. Fの任意の開被覆$\{U_λ\}_{λ∈Λ}$から有限個$U_{λ_1},\cdots,U_{λ_r}~~~(λ_i\in Λ)$を適当に選んで$\{U_{λ_1} ,...,U_{λ_r}\}$をFの開被覆とすることができる。
参考文献:[連続性とコンパクト性](http://www.math.nagoya-u.ac.jp/~miyachi/courses/2W11_files/miyachi-2W11-08.pdf)
---
### 点列コンパクト
集合Kが点列コンパクト$\Leftrightarrow$Kに含まれる任意の点列$(x_n)_{n\in N}$がKの中の点に収束する部分列をもつ。
参考文献:[有界閉とコンパクト](http://www.misojiro.t.u-tokyo.ac.jp/~murota/lect-kisosuri/compactRn041202.pdf)
note:定義
---
### 定理9.4の証明
背理法で示す。
実行可能領域内に$x_k\to x(k\to\infty)$かつ$f(x_k)\leq f(x^*)$となる点列$\{x_k\}$が存在すると仮定する。
---
ここで
$x_k=x^*+\epsilon_k\delta_k$
$\epsilon_k\to +0$
$\|\delta_k\|=1$
とおくと超球面のコンパクト性より一般性を失うことなく
$\delta_k\to\delta,\|\delta\|=1$
とすることができる。
このとき$c_i\in(0,1),c\in(0,1)$が存在して
---
$0=g_i(x^*+\epsilon_k\delta_k)$
$=\epsilon_k\nabla g_i(x^*)^T\delta_k+\frac{\epsilon_k^2}{2}\delta_k^T\nabla^2g_i(x^*+c_i\epsilon_k\delta_k)\delta_k$
---
$f(x^*)\geq f(x^*+\epsilon_k\delta_k)$
$=f(x^*)+\epsilon_k\nabla f(x^*)^T\delta_k+\frac{\epsilon^2}{2}\delta_k^T\nabla^2f(x^*+c\epsilon_k\delta_k)\delta_k$
となる。
---
よって定理9.3と同様に
$f(x^*)\geq f(x^*+\epsilon_k\delta_k)+\Sigma\nabla^*_ig_i(x^*+\epsilon_k\delta_k)$
$=f(x^*)+\epsilon_k\left(\nabla f(x^*)+\Sigma\nabla g_i(x^*)\right)^T\delta_k$
$~~~~~~+\frac{\epsilon^2}{2}\delta_k^T\left(\nabla^2f(x^*+c\epsilon_k\delta_k)+\Sigma\nabla^2g_i(x^*+c_i\epsilon_k\delta_k)\right)\delta_k$
---
仮定より$\nabla f(x^*)+\Sigma\nabla g_i(x^*)=0$なので
$0\geq\delta_k^T\left(\nabla^2f(x^*+c\epsilon_k\delta_k)+\Sigma\nabla^2g_i(x^*+c_i\epsilon_k\delta_k)\right)\delta_k$
---
よって$k\to\infty$とすると
(右辺)$\to\delta^T\left(\nabla^2f(x^*)+\Sigma\nabla^2g_i(x^*)\right)\delta=\delta^TL\delta$
---
一方$g_i$のテイラー展開より$k\to\infty$とすると
$0=\nabla g_i(x^*)^T\delta_k+\frac{\epsilon_k}{2}\delta_k^T\nabla^2g_i(x^*+c_i\epsilon_k\delta_k)\delta_k$
$\to\nabla g_i(x^*)^T\delta+\frac{+0}{2}\delta^T\nabla^2g_i(x^*)\delta=\nabla g_i(x^*)^T\delta$
---
よって$\delta\in S$となるがこれは$\delta^TL\delta>0$に矛盾する。
証明終了
$\Leftrightarrow$
{"metaMigratedAt":"2023-06-15T09:04:50.940Z","metaMigratedFrom":"Content","title":"制約付き最適化問題","breaks":true,"contributors":"[{\"id\":\"ae419421-6ce9-495c-8bc1-2660a5a9cb07\",\"add\":5534,\"del\":732}]"}