---
lang: ja
tags: lecture, nonlinear programming, convex programming
---
# 非線形計画問題(1) 制約なし問題の最適性条件と解法
[非線形計画問題ポータルへ戻る](https://hackmd.io/@nagae/NLP)

# 制約なし問題の最適性条件
## 未知変数が一次元の場合
ある1次元凸関数$f:\mathcal{R}\rightarrow \mathcal{R}$の最小化問題：
$$
\min_{x} f(x)
$$
を考える．$x$に制約がない時，最適解$x$において
$$
\frac{{\rm d} f}{{\rm d} x}(x^{\ast}) = 0
$$
が成立する．この条件は**必要条件**(i.e. $x^{\ast}$が最適解であるためには$\frac{\partial f}{\partial x}(x^{\ast})=0$であることが必要)でしかなく，$f$が最適解において凸である時，すなわち
$$
\frac{{\rm d}^{2} f}{{\rm d} x^{2}}(x^{\ast}) > 0, \quad \forall x \in \mathcal{R}
$$
である時に**必要十分条件**となる．

## 未知変数が多次元の場合
状態変数が$N$次元ベクトル$\boldsymbol{x}=(x_{1}, \cdots, x_{N})$であるとき，変数関数$f:\mathcal{R}^{N}\rightarrow \mathcal{R}$の最小化問題：
$$
\min_{\boldsymbol{x}} f(\boldsymbol{x})
$$
の最適性条件($\boldsymbol{x}^{\ast}$が最適解であるための必要条件)は，勾配
$$
\nabla f(\boldsymbol{x}) =
\begin{bmatrix}
\frac{\partial f}{\partial x_{1}}(\boldsymbol{x}) \\ \vdots \\ \frac{\partial f}{\partial x_{N}}(\boldsymbol{x})
\end{bmatrix} = \boldsymbol{0}
$$
を用いて
$$
\nabla f(\boldsymbol{x}^{\ast}) = \boldsymbol{0}
$$
と書ける．この条件が必要十分となる(i.e. $f(\boldsymbol{x})$が凸となる)のは，$f$のHessian(ヘッセ行列)
$$\nabla^{2} f(\boldsymbol{x}) = \begin{bmatrix}\frac{\partial^{2} f}{\partial x_1^{2}}(\boldsymbol{x}) & \cdots & \frac{\partial^{2} f}{\partial x_{1} \partial x_{N}}(\boldsymbol{x}) \\ \vdots & \ddots & \vdots \\ \frac{\partial^{2} f}{\partial x_{N} \partial x_{1}}(\boldsymbol{x}) & \cdots & \frac{\partial^{2} f}{\partial x_{N}^{2}}(\boldsymbol{x})\end{bmatrix}$$
が最適解において**正定値**(positive definiteness)であるとき，すなわち
$$
\boldsymbol{y}^{\top} \nabla^{2} f(\boldsymbol{x}^{\ast}) \boldsymbol{y} > 0, \quad \forall \boldsymbol{y} \in \mathcal{R}^{N}
$$
であるとき．以下では，記述を簡潔にするために$H(\boldsymbol{x}) = \nabla^{2} f(\boldsymbol{x})$と表すことがある．

### 最適性条件の例(1)
2次元未知変数$\boldsymbol{x}=(x_1, x_2)$についての最小化問題
$$\min_{\boldsymbol{x}} f(\boldsymbol{x}) = 3(x_{1}-2)^{2} + 3(x_{2}-3)^{2}-2x_{1}x_{2}$$
の最小化問題を考える．目的関数$f(\boldsymbol{x})$の3次元プロットおよび等高線は以下の図のようになる：
目的関数の勾配は
$$
\nabla f(\boldsymbol{x}) = \begin{bmatrix}
6x_{1} - 2x_{2} - 12\\
-2x_{1} + 6 x_{2} - 18
\end{bmatrix}
$$
であり，最適性条件$\nabla f(\boldsymbol{x}) = \boldsymbol{0}$の解は以下で得られる（上図の赤い点に相当）：
$$
(x_{1}, x_{2}) = \left(\frac{27}{8}, \frac{33}{8}\right)
$$

### 最適性条件の例(2)
2次元未知変数$\boldsymbol{x}=(x_1, x_2)$についての最小化問題
$$\min_{\boldsymbol{x}} f(\boldsymbol{x}) = \frac{1}{2}(x_{1}-1)^{2} + 5(x_{1}^{2}-x_{2})^{2}$$
の最小化問題を考える．目的関数$f(\boldsymbol{x})$の3次元プロットおよび等高線は以下の図のようになる：
目的関数の勾配は
$$
\nabla f(\boldsymbol{x}) = \begin{bmatrix}
20x_{1}(x_{1}^{2}-x_{2}) + x_{1}-1\\
-10(x_{1}^{2}-x_{2})
\end{bmatrix}
$$
であり，最適性条件$\nabla f(\boldsymbol{x}) = \boldsymbol{0}$の解は$(x_{1}, x_{2})=(1,1)$で得られる（上図の赤い点に相当）.

# 制約なし問題の解法
## 最急降下法
勾配$\nabla f(\boldsymbol{x})$は目的関数を増加させる方向であるため，その逆方向(**最急降下方向**と呼ぶ)$\boldsymbol{d} = -\nabla f(\boldsymbol{x})$に進めば目的関数を減少させられる．このことを利用し，
$$\begin{align}
\boldsymbol{x} &:= \boldsymbol{x} + \alpha \boldsymbol{d} \\&= \boldsymbol{x} - \alpha \nabla f(\boldsymbol{x})
\end{align}$$
と解を改訂するのが**最急降下法**である．ここで$\alpha > 0$は移動する大きさを決定するスカラであり，**ステップ・サイズ**と呼ばれる．

ステップ・サイズを決定する問題は**直線探索問題** (line search problem)と呼ばれる:
$$
\min_{\alpha > 0} f\Bigl(\boldsymbol{x} + \alpha \boldsymbol{d}\Bigr)
$$
直線探索問題の解法は後述する．

**最急降下法**のアルゴリズムは下記のように整理される：

- [Step 0] 初期解$\boldsymbol{x}^{(0)}$を選ぶ．$n:=0$とする．
- [Step 1] $\boldsymbol{x}^{(n)}$が最適解と判断できるなら終了(収束判定)．
- [Step 2] $\boldsymbol{x}^{(n)}$における勾配から降下方向を$\boldsymbol{d}^{(n)}: = - \nabla f(\boldsymbol{x}^{(n)})$とする．
- [Step 3] 直線探索問題を問いてステップ・サイズ$\alpha^{(n)}$を決定する．
- [Step 4] 解を$\boldsymbol{x}^{(n+1)} := \boldsymbol{x}^{(n)} + \alpha^{(n)} \boldsymbol{d}^{(n)}$と改訂する．$n:=n+1$として [Step 1]へ．

### 最急降下法の例(1)
上述の例題：
$$\min_{\boldsymbol{x}} f(\boldsymbol{x}) = 3(x_{1}-2)^{2} + 3(x_{2}-3)^{2}-2x_{1}x_{2}$$
に対して,$\boldsymbol{x}^{(0)} = (4, 8)$を初期解として勾配法を適用した時の収束パターンを下に示す．この図の左の2つの図は，解軌道およびその最適解付近での拡大図を表す．一番右の図は，各繰返しにおける目的関数値と最適値との差を対数プロットしたものである：

### 最急降下法の例(2)
もう一つの例題：
$$\min_{\boldsymbol{x}} f(\boldsymbol{x}) = \frac{1}{2}(x_{1}-1)^{2} + 5(x_{1}^{2}-x_{2})^{2}$$
に対して，$\boldsymbol{x}^{(0)}=(0, 0.5)$を初期解として勾配法を適用した場合，収束状況は大きく異なってくる．この例では，最急降下法による収束は非常に緩慢であり，100回繰返しても最適解には到達せず，200回，300回，500回と繰返しても依然最適解から若干ズレた点にしか収束しないことが判る．これは，後述するように，最急降下法が**一次微分しか使わない**ためである．

### Newton 法
目的関数の Hessian $\nabla^{2} f(\boldsymbol{x})$が逆行列を持ち，効率的に計算できる場合，**Newton法**を用いることで，より高速な求解が期待できる．その基本的発想は以下の通りである．まず，現在の解$\boldsymbol{x}$の周りで目的関数を Taylor 展開し，三次以上の項を無視すれば，$\boldsymbol{x}$から少し離れた点$\boldsymbol{y}$における目的関数の値は以下の式で近似できる：
$$
f(\boldsymbol{y}) \approx f(\boldsymbol{x}) + \nabla f(\boldsymbol{x})^{\top}(\boldsymbol{y}-\boldsymbol{x}) + \frac{1}{2}
(\boldsymbol{y}-\boldsymbol{x})^{\top} \nabla^{2} f(\boldsymbol{x}) (\boldsymbol{y}-\boldsymbol{x})
$$
この式の右辺は，解の差分を$\boldsymbol{d} = \boldsymbol{y}-\boldsymbol{x}$とし，Hessian を $H(\boldsymbol{x}) = \nabla^{2}f(\boldsymbol{x})$とすれば，以下のように簡潔に表せる：
$$
Z(\boldsymbol{d}) = f(\boldsymbol{x}) + \nabla f(\boldsymbol{x})^{\top} \boldsymbol{d} + \frac{1}{2}
\boldsymbol{d}^{\top} H(\boldsymbol{x}) \boldsymbol{d}
$$
これは差分$\boldsymbol{d}$についての二次式だから，
$$
\nabla_{\boldsymbol{d}} Z(\boldsymbol{d}) = \nabla f(\boldsymbol{x}) + H(\boldsymbol{x}) \boldsymbol{d} = \boldsymbol{0}
$$
で最小化される．これを$\boldsymbol{d}$について解けば，以下の **Newton方向** を得る：
$$
\boldsymbol{d} = - H^{-1}(\boldsymbol{x}) \nabla f(\boldsymbol{x})
$$
ここで，$H^{-1}(\boldsymbol{x})$は Hessian $H(\boldsymbol{x}) = \nabla^{2} f(\boldsymbol{x})$の逆行列である．この Newton 方向$\boldsymbol{d}$を使って解を
$$\begin{align}
\boldsymbol{x} &:= \boldsymbol{x} + \alpha \boldsymbol{d} \\ &= \boldsymbol{x} - \alpha H^{-1}(\boldsymbol{x}) \nabla f(\boldsymbol{x})
\end{align}$$
と改訂するのが Newton 法である．ただし，Newton法では基本的に直線探索は必要なく，ステップ・サイズを$\alpha=1$としても問題ないことが知られている．

Newton法のアルゴリズムは下記のように整理される：

- [Step 0] 初期解$\boldsymbol{x}^{(0)}$を選ぶ．$n:=0$とする．
- [Step 1] $\boldsymbol{x}^{(n)}$が最適解と判断できるなら終了(収束判定)．
- [Step 2] $\boldsymbol{x}^{(n)}$におけるNewton方向を$\boldsymbol{d}^{(n)}: = - \boldsymbol{H}^{-1}(\boldsymbol{x}^{(n)}) \nabla f(\boldsymbol{x}^{(n)})$とする．
- [Step 3] 解を$\boldsymbol{x}^{(n+1)} := \boldsymbol{x}^{(n)} + \boldsymbol{d}^{(n)}$と改訂する．$n:=n+1$として [Step 1]へ．

### Newton方向の計算に関する注意
Newton方向を計算する際には，Hessian の逆行列$H^{-1}(\boldsymbol{x}) = (\nabla^{2} f(\boldsymbol{x}))^{-1}$を**直接計算するのではなく**，以下の線形連立方程式：
$$
H(\boldsymbol{x}) \boldsymbol{d} = - \nabla f(\boldsymbol{x})
$$
を$\boldsymbol{d}$について([SOR法](https://ja.wikipedia.org/wiki/SOR%E6%B3%95)などを用いて)解く方が，通常，圧倒的に効率的である．[[参考1](https://opqrstuvcut.github.io/blog/posts/%E5%AE%89%E6%98%93%E3%81%AB%E9%80%86%E8%A1%8C%E5%88%97%E3%82%92%E6%95%B0%E5%80%A4%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B%E3%81%AE%E3%81%AF%E3%82%84%E3%82%81%E3%82%88%E3%81%86/)][[参考2](https://math.stackexchange.com/questions/1975610/why-is-solving-linear-equation-more-stable-than-directly-computing-matrix-invers)]

### Newton法の例
最急降下法での収束が緩慢だった例題
$$\min_{\boldsymbol{x}} f(\boldsymbol{x}) = \frac{1}{2}(x_{1}-1)^{2} + 5(x_{1}^{2}-x_{2})^{2}$$
に対して，$\boldsymbol{x}^{(0)}=(0.5,0)$を初期解とした結果を示す．この場合，Hessianは
$$
H (\boldsymbol{x}) = \begin{bmatrix}
60x_{1}^{2} - 20x_{2} + 1 & - 20x_{1}\\
-20x_{1} & 10
\end{bmatrix}
$$
となり，各繰返しでこれを用いて Newton方向を計算できる．

このケースでは，わずか8回の計算で最適解$\boldsymbol{x}^{\ast}=(1,1)$に到達している．特に，$\boldsymbol{x}^{(4)})$以降は目的関数が著しく減少していることが読み取れる

## Newton法の限界
上述したように Newton 法は極めて高速だが，以下の限界がある：
- $\boldsymbol{H}(\boldsymbol{x})$が退化している（$\boldsymbol{H}(\boldsymbol{x})$の全ての行が互いに線形独立ではなく，逆行列が存在しない）場合にはNewton方向が計算できない．
- $\boldsymbol{H}(\boldsymbol{x})$が正定値でない場合にはNewton方向へ進んでも目的関数が減少しない．

たとえば$\boldsymbol{x} = (0, 1/20)$においては，
$$
\boldsymbol{H}(\boldsymbol{x}) = \begin{bmatrix}
0 & 0 \\ 0 & 10
\end{bmatrix}
$$となって$\boldsymbol{H}^{-1}(\boldsymbol{x})$が存在しないため，Newton方向が計算できない．

また，$\boldsymbol{x} = (0,1/10)$においては，
$$\boldsymbol{H}(\boldsymbol{x}) = \begin{bmatrix}
-1 & 0 \\ 0 & 10
\end{bmatrix}$$
で正定値ではない．このとき，Newton 方向は$\boldsymbol{d} = (-1, -1/10)$と求められるが，その方向にわずかでも進むと，目的関数が増加してしまう．

## 準Newton法
Newton法は極めて高速だが，対象とする問題が Hessian $\nabla^{2} f(\boldsymbol{x})$ が逆行列を持ち，かつ正定値である場合に限られる（逆行列を持たなければ Newton方向そのものが計算できないし，正定値でなければ Newton 方向に進んだ時に目的関数が増加し得る）．

そこで，Hessian を何らかの正定値対称行列で近似するのが**準 Newton 法**である．準Newton方では，反復のたびに状態変数$\boldsymbol{x}^{(n)}$と正定値対称行列$\boldsymbol{B}^{(n)}$の両方を改訂する．そして，これを用いて，
$$\begin{align}
\boldsymbol{x} &:= \boldsymbol{x} + \alpha \boldsymbol{d} \\ &= \boldsymbol{x} - \alpha {\boldsymbol{B}^{(n)}}^{-1}\nabla f(\boldsymbol{x})
\end{align}$$
と解を改訂する．

準Newton法のアルゴリズムは下記のように整理される：

- [Step 0] 初期解$\boldsymbol{x}^{(0)}$と初期正定値行列$\boldsymbol{B}^{(0)}$を選ぶ．$n:=0$とする．
- [Step 1] $\boldsymbol{x}^{(n)}$が最適解と判断できるなら終了(収束判定)．
- [Step 2] $\boldsymbol{x}^{(n)}$におけるNewton方向を$\boldsymbol{d}^{(n)}: = - {\boldsymbol{B}^{(n)}}^{-1} \nabla f(\boldsymbol{x}^{(n)})$とする．
- [Step 3] 直線探索問題を問いてステップ・サイズ$\alpha^{(n)}$を決定する．
- [Step 4] 解を$\boldsymbol{x}^{(n+1)} := \boldsymbol{x}^{(n)} + \alpha^{(n)} \boldsymbol{d}^{(n)}$と改訂する．
- [Step 5] 正定値行列$\boldsymbol{B}^{(n+1)}$を求める．
- [Step 6] $n:=n+1$として [Step 1]へ．

#### 正定値行列$\boldsymbol{B}^{(n)}$の更新の仕方
$\boldsymbol{B}^{(n)}$の更新には，状態変数の差分$\boldsymbol{s}^{(n)}=\boldsymbol{x}^{(n+1)}-\boldsymbol{x}^{(n)}$および勾配の差分$\boldsymbol{y}^{(n)} = \nabla f(\boldsymbol{x}^{(n+1)}) - \nabla f(\boldsymbol{x}^{(n)})$を用いる．

未知変数が1次元の場合，$|s^{(n)}|$があまり大きくなければ，二階微分は
$$
f''(x^{(n+1)}) \approx \frac{f'(x^{(n+1)})-f'(x^{(n)})}{x^{(n+1)}-x^{(n)}} = \frac{y^{(n)}}{s^{(n)}}
$$
と近似できる．$N$次元の場合を考えると，Hessian $H(\boldsymbol{x}^{(n)})$の近似として
$$
\boldsymbol{B}^{(n+1)} \boldsymbol{s}^{(n)} = \boldsymbol{y}^{(n)}
$$
を満たすものを採用するのは自然であろう．この条件は **セカント条件(secant condition)** と呼ばれる．セカント条件だけでは未知行列$\boldsymbol{B}^{(n)}$は一意には決まらないため，$\boldsymbol{B}^{(n)}$が正定値対称であることが保証され，直前に用いた$\boldsymbol{B}^{(n)}$を修正することで求められる，といった方法が考えられる．そうした方法の中で最もよく知られるのが，次の**BFGS法**である：
$$
\boldsymbol{B}^{(n+1)} := \boldsymbol{B}^{(n)} + \frac{1}{\beta^{(n)}} \boldsymbol{y}^{(n)}(\boldsymbol{y}^{(n)})^{\top} - \frac{1}{\gamma^{(n)}}
\boldsymbol{B}^{(n)} \boldsymbol{s}^{(n)} (\boldsymbol{s}^{(n)})^{\top} \boldsymbol{B}^{(n)}
$$
ただし，
$$\begin{align}
\beta^{(n)} &= (\boldsymbol{y}^{(n)})^{\top}\boldsymbol{s}^{(n)}, &
\gamma^{(n)} &= (\boldsymbol{s}^{(n)})^{\top}\boldsymbol{B}^{(n)} \boldsymbol{s}^{(n)}
\end{align}$$
この方法は，以下の3つの望ましい性質を満足することが知られている：
1. $\boldsymbol{B}^{(n+1)}$はセカント条件を満たす
2. $\boldsymbol{B}^{(n)}$が対称ならば$\boldsymbol{B}^{(n+1)}$も対称である
3. $\boldsymbol{B}^{(n)}$が正定値かつ$\beta^{(n)}>0$なら$\boldsymbol{B}^{(n+1)}$も正定値である

## 準 Newton 法の例
初期解を$\boldsymbol{x}^{(0)} = (0, 0.5)$とし，初期正定値行列を単位行列$\boldsymbol{B}^{(0)} = \boldsymbol{I}$とし，準 Newton法を適用した場合の収束パターンを示す． Newton法より幾分遅いが， 最急降下法に比べると極めて早く最適解に収束していることが判る．

準 Netwon 法では，Newton法では Newton方向が計算できない初期解$\boldsymbol{x}^{(0)} = (1, 1/20)$とした場合も正しく最適解に収束する．

## 直線探索の方法
最急降下法や準Newton法などでステップ・サイズを決定(直線探索)する問題は，現在の解を$\boldsymbol{x}$，解の改訂方向(降下方向)を$\boldsymbol{d}$とすれば，
$$
\min_{\alpha \geq 0} g(\alpha) = f(\boldsymbol{x} + \alpha \boldsymbol{d})
$$
と定式化できる．目的関数が二次凸関数であれば最適なステップ・サイズは解析的に求められる(後注参照)が，そうでない場合は数値計算によって求める必要がある．後者の場合でも，直線探索問題を精度良く解くよりも，適当な精度で打ち切って降下方向を計算し直すほうが効率が良いことが知られている．

### 目的関数が二次関数の場合
:::warning
目的関数が二次関数の場合，制約なし問題の最適解は解析的に求められる(繰返し計算を必要としない)ため，ステップ・サイズもわざわざ計算する必要はない．ここで紹介する考え方は，次の制約つきの問題に利用するものとして理解して欲しい．
:::
目的関数が二次凸関数：
$$
f(\boldsymbol{x}) = \frac{1}{2} \boldsymbol{x}^{\top} \boldsymbol{Q} \boldsymbol{x} + \boldsymbol{c}^{\top} \boldsymbol{x}
$$
の場合を考える．ただし，$\boldsymbol{Q}$および$\boldsymbol{c}$は，それぞれ，$N$次元の半正定値対称行列および列ベクトルとする．ステップ・サイズを$\alpha$とした時の目的関数値もまた$\alpha$についての二次凸関数：
$$
g(\alpha) = \frac{1}{2} (\boldsymbol{x} + \alpha \boldsymbol{d})^{\top} \boldsymbol{Q} (\boldsymbol{x} + \alpha \boldsymbol{d}) + \boldsymbol{c}^{\top} (\boldsymbol{x} + \alpha \boldsymbol{d})
$$
であり，その一次導関数は
$$
g'(\alpha) = \boldsymbol{d}^{\top} \boldsymbol{Q} (\boldsymbol{x} + \alpha \boldsymbol{d}) + {\boldsymbol{d}}^{\top} \boldsymbol{c}
$$
ある．$\alpha=0$における勾配$g'(\alpha)$が正の場合，すなわち
$$
{\boldsymbol{d}}^{\top} (\boldsymbol{c} + \boldsymbol{Q} \boldsymbol{x}) > 0
$$
の場合，正のステップ・サイズを選ぶ限り目的関数は増加するため，最適ステップ・サイズは$\alpha^{\ast}= 0$である．そうでない場合，最適ステップ・サイズ$\alpha^{\ast}$において
$$
g'(\alpha^{\ast}) = {\boldsymbol{d}}^{\top} \boldsymbol{Q} (\boldsymbol{x} + \alpha^{\ast} \boldsymbol{d}) + {\boldsymbol{d}}^{\top} \boldsymbol{c} = 0
$$
が成り立つ．これを$\alpha^{\ast}$について解けば，
$$
\alpha^{\ast} = - \frac{{\boldsymbol{d}}^{\top}(\boldsymbol{c} + \boldsymbol{Q}\boldsymbol{x})}{{\boldsymbol{d}}^{\top}\boldsymbol{Q} \boldsymbol{d}} (>0)
$$
を得る．

### Armijo の規則による方法
直線探索においては，計算を繰返して厳密なステップ・サイズを求めるより，適当な回数で繰り返しを打ち切ってステップ・サイズを近似する方が，求解アルゴリズム全体としては効率が良いことが，経験的に知られている．そうした近似解法の一つとして **Armijo (アルミホ) の基準 (Armijo rule)** を用いた方法が知られている．

この方法は，直線探索問題の目的関数：
$$
g(\alpha) = f(\boldsymbol{x} + \alpha \boldsymbol{d})
$$
の$\alpha=0$における接線は，
$$
h(\alpha) = f(\boldsymbol{x}) + \alpha {\nabla f(\boldsymbol{x})}^{\top} \boldsymbol{d}
$$
と書ける．$\boldsymbol{d}$は目的関数の降下方向なので，明らかに${\nabla f(\boldsymbol{x})}^{\top} \boldsymbol{d} < 0$．$h(\alpha)$は$\alpha$についての線形関数だから，$\alpha$を大きくするほど無限に小さくなる．一方，$g(\alpha)$は，最適解が存在するなら，どこかで増加に転じる．そのため，$h(\alpha)$の傾きを少し「緩めた」直線
$$
\hat{h}(\alpha) = f(\boldsymbol{x}) + \xi \alpha {\nabla f(\boldsymbol{x})}^{\top} \boldsymbol{d} \quad (0 < \xi < 1)
$$
を考えると$\hat{h}(\alpha) \geq g(\alpha)$となるような$\alpha$が存在する（$\xi$は傾きを緩める度合いに相当）．この基準，すなわち
$$
f(\boldsymbol{x} + \alpha \boldsymbol{d}) \leq f(\boldsymbol{x}) + \xi \alpha {\nabla f(\boldsymbol{x})}^{\top} \boldsymbol{d}
$$
は **Armijo の基準** と呼ばれる．$\xi < 1$であるから，$\alpha$が十分に小さければ Armijo の基準は必ず満たされる．

Armijo の基準の考え方は以下のように図示できる．この図において，オレンジ色の曲線は$g(\alpha)$を表す．点線は$\alpha=0$における$g(\alpha)$の接線$h(\alpha)$を表し，青い直線はこの接線の傾きを「緩めた」直線$\hat{h}(\alpha)$を表す．Armijo の基準を満たす$\alpha$の領域は，青い直線$\hat{h}(\alpha)$よりもオレンジの曲線$g(\alpha)$が小さくなる区間であり，赤い矢印で表される．

Armijoの基準を満たす$\alpha$を求めるシンプルな方法の1つとして，$\alpha$を適当な初期値から次々と半分にしていく**2分割法**が知られている．その手続きは以下のように整理される：

- [Step 0] 初期解$\alpha^{(0)}$を選ぶ．$n:=0$とする．
- [Step 1] Armijo の基準: $$f(\boldsymbol{x} + \alpha^{(n)} \boldsymbol{d}) \leq f(\boldsymbol{x}) + \xi \alpha^{(n)} {\nabla f(\boldsymbol{x})}^{\top} \boldsymbol{d} $$が ` 満たされれば終了．
- [Step 2] $\alpha^{(n+1)} := \alpha^{(n)}/2$
- [Step 3] $n:=n+1$として [Step 1]へ．

なお，上述の[Step 2]における$\alpha$の改訂は，任意の定数$\gamma \in (0,1)$を用いて，$\alpha^{(n+1)} := \gamma \alpha^{(n)}$としてもよい． $\gamma$が1に近いほど$\alpha$の縮小は緩慢になり， Armijoの基準を満たすまでの繰返しは多くなるが，より大きなステップ・サイズが得られることが期待できる．

# 練習問題
## 練習問題1
次の二次計画問題:
$$
\min_{x_1, x_2} f(x_1, x_2) = 3(x_1-6)^2 + 5(x_2-4)^2 + 6x_1 x_2
$$
について，以下の問に答えよ：

1. 目的関数の勾配$\nabla f(\boldsymbol{x})$および Hessian $\nabla^{2} f(\boldsymbol{x})$ を求めよ．
2. 最適性条件$\nabla f(\boldsymbol{x}^{\ast})=\boldsymbol{0}$を解いて最適解$\boldsymbol{x}^{\ast}$を求めよ.
3. Hessian $\nabla^{2} f(\boldsymbol{x})$が半正定値対称行列であることを示せ．

## 練習問題2
次の非線形計画問題:
$$
\min_{x_1, x_2} f(x_1, x_2) =
((x_1-4)^2+2x_2)^2+(x_1-x_2)^2
$$
について，以下の問に答えよ：
1. 目的関数の勾配$\nabla f(\boldsymbol{x})$ および Hessian $\nabla^{2} f(\boldsymbol{x})$ を求めよ．
2. 最急降下法，Newton法，準Newton法のいずれかを用いて最適解を求めよ．
3. 最適解において Hessian $\nabla^{2} f(\boldsymbol{x}^{\ast})$ が半正定値対称行列であることを示せ．