---
lang: ja
tags: lecture, nonlinear programming, convex programming
---
# 非線形計画問題(2) 制約あり問題の最適性条件
[非線形計画問題ポータルへ戻る | Back to LP Portal](https://hackmd.io/@nagae/NLP)

## 非負制約つき最適化問題
### 未知変数が1次元の場合
非負制約つきの1次元最適化問題:
$$\begin{align}
\min_{x} &f(x)\\
\text{s.t.} & x\geq 0
\end{align}$$
の最適性条件(必要条件)は，下図のように，最適解$x^{\ast}$が正か0かによって場合分けされる：

<div style="text-align:center">


</div>

すなわち，
- 左図のように最適解が正($x^{\ast} > 0$)ならば，最適解において$f'(x^{\ast}) = 0$
- 右図のように最適解が0($x^{\ast} = 0$)ならば，最適解において$f'(x^{\ast}) \geq 0$

となる．この条件は，
- $x^{\ast} \geq 0$ かつ $f'(x^{\ast}) \geq 0$であり，少なくとも一方が等式で成立する

という命題と等価である．この条件は以下の**相補性条件**(complementarity condition)として記述できる：
$$
\begin{cases}
x^{\ast} \cdot f'(x^{\ast}) = 0\\
x^{\ast} \geq 0, \quad f'(x^{\ast}) \geq 0
\end{cases}
$$
相補性条件は，下記のように記述することもできる：
$$\begin{cases}
x^{\ast} > 0 &\rightarrow f'(x^{\ast}) = 0\\
x^{\ast} = 0 &\leftarrow f'(x^{\ast}) > 0
\end{cases}$$

### 未知変数が多次元の場合
$N$次元状態変数$\boldsymbol{x} = (x_{1}, \cdots, x_{N})$の非負制約つき最適化問題：
$$\begin{align}
\min_{\boldsymbol{x}} &f(\boldsymbol{x})\\
\text{s.t.} & \boldsymbol{x}\geq \boldsymbol{0}
\end{align}$$
の最適性条件(必要条件)は，$x\rightarrow \boldsymbol{x}$，$f' \rightarrow \nabla f$と置き換えれば容易に想像できるように，
$$
\begin{cases}
{\boldsymbol{x}^{\ast}}^{\top} \nabla f(\boldsymbol{x}^{\ast}) = 0\\
\boldsymbol{x}^{\ast} \geq \boldsymbol{0}, \quad \nabla f(x^{\ast}) \geq \boldsymbol{0}
\end{cases}
$$
と記述できる．$\boldsymbol{x}^{\top} \nabla f(\boldsymbol{x}) = \sum_{i=1}^{N} x_{i} \frac{\partial f}{\partial x_{i}}(\boldsymbol{x})$であり，$\boldsymbol{x}$と$\nabla f(\boldsymbol{x})$の非負性より，この条件は，任意の$i=1, \cdots, N$について$x_{i} \frac{\partial f}{\partial x_{i}} (\boldsymbol{x}) = 0$ が成立することと等価である．従って，相補性条件は，下記のように記述することもできる：
$$\begin{cases}
x_{i}^{\ast} > 0 &\rightarrow \frac{\partial f}{\partial x_{i}}(x^{\ast}) = 0\\
x_{i}^{\ast} = 0 &\leftarrow \frac{\partial f}{\partial x_{i}}(x^{\ast}) > 0
\end{cases} \quad i = 1, \cdots, N$$

## 一般的な制約つき最適化問題
### 制約つき最適化問題とその許容領域
$M$本の不等式制約をもつ次の最適化問題を考えよう:
$$\begin{align}
\min_{\boldsymbol{x}} &f(\boldsymbol{x}) \\
\text{s.t.} & g_{j}(\boldsymbol{x}) \geq 0 \quad j = 1, \cdots, M
\end{align}$$
ここで，全ての不等式制約を満足する領域
$$
\Omega = \left\{\boldsymbol{x}: g_{j}(\boldsymbol{x}) \geq 0, \quad j = 1, \cdots, M\right\}
$$
を**許容領域**と呼ぶ．以下では，許容領域が凸であると仮定する．

下記の図は，以下の3つの不等式で構成される許容領域を表している：
- $g_{1}(\boldsymbol{x}) = -\left(\frac{x_{1}}{4}\right)^{2}-x_{2}+6 \geq 0$
- $g_{2}(\boldsymbol{x}) = -\left(\frac{x_{1}+2}{5}\right)^{2}+x_{2}+2 \geq 0$
- $g_{3}(\boldsymbol{x}) = x_{1} \geq 0$

<div style="text-align:center">

</div>

### 制約つき最適化問題の最適性条件の幾何学的理解
制約つき最適化問題の最適性条件は「どの制約条件が効いているか」に依存して決まる．ある解$\boldsymbol{x}$において，$j$番目の制約条件が等式で満足されているとき(i.e. $g_{i}(\boldsymbol{x})=0$)，この制約を**有効(active)** あるいは**束縛的(binding)** と呼ぶ．

最適解が許容領域の内側にある場合，最適解で有効な制約条件は存在しない．この場合の最適性条件(必要条件)は，無制約の場合と同様，降下方向$-\nabla f(\boldsymbol{x})$が大きさを持たないことであるから，
$$
-\nabla f(\boldsymbol{x}^{\ast}) = \boldsymbol{0}
$$
となる．一方，最適解が許容領域の境界上にある場合，最適性条件は，
$$
-\nabla f(\boldsymbol{x}^{\ast}) = -\sum_{j} \lambda_{j} \nabla g_{j}(\boldsymbol{x}^{\ast})
$$
と表される．ここで，$\lambda_{j}$は，最適解$\boldsymbol{x}^{\ast}$において$j$番目の制約条件が有効である($g_{j}(\boldsymbol{x}^{\ast})=0$)ならば非負の値を取り，そうでなければ0となる変数である．このことは，$\lambda_{j}>0$ならば$j$番目制約条件は有効（$g_{j}(\boldsymbol{x}^{\ast})= 0$）であり，$j$番目制約条件が有効でない$g_{j}(\boldsymbol{x}^{\ast})>0$）ならば$\lambda_{j}=0$であることと等価である．

$\boldsymbol{\lambda} = (\lambda_{1}, \cdots, \lambda_{M})$が満たすべきこの条件は，
$$\begin{cases}
\lambda_{j} > 0 &\rightarrow g_{j}(\boldsymbol{x}^{\ast}) = 0\\
\lambda_{j} = 0 &\leftarrow g_{j}(\boldsymbol{x}^{\ast}) > 0
\end{cases} \quad j = 1, \cdots, M
$$とまとめて記述できる．任意の$j$について$\lambda_{j}=0$と$g_{j}(\boldsymbol{x}^{\ast})=0$の少なくとも一方が成立するから，この条件は，以下のようにも記述できる
$$
\begin{cases}
\lambda_{j} \cdot g_{j}(\boldsymbol{x}^{\ast}) = 0\\
\lambda_{j} \geq 0, \quad g_{j}(\boldsymbol{x}^{\ast}) \geq 0
\end{cases} \quad j = 1, \cdots, M
$$
あるいは，ベクトル$\boldsymbol{g}(\boldsymbol{x}) = (g_{1}(\boldsymbol{x}), \cdots, g_{M}(\boldsymbol{x}))$ を用いて
$$
\begin{cases}
\boldsymbol{\lambda}^{\top} \boldsymbol{g}(\boldsymbol{x}^{\ast}) = 0\\
\boldsymbol{\lambda} \geq \boldsymbol{0}, \quad \boldsymbol{g}(\boldsymbol{x}^{\ast}) \geq \boldsymbol{0}
\end{cases}
$$
としてもよい．この条件は**相補性条件(complementarity condition)** と呼ばれる．

上記の最適性条件は，黒丸で表される最適解$\boldsymbol{x}^{\ast}$において，目的関数の降下方向$-\nabla f$が，有効な制約の降下方向$-\nabla g_{j}$の合成で表される，すなわち，下記の図のように$-\nabla f$が$-\nabla g_{j}$で構成される錐(cone)の中に入っていることを意味している．この図では，最適解$\boldsymbol{x}^{\ast}$において有効な(等式で成立する)制約が$g_{1}$(青の曲線)と$g_{2}$(赤の曲線)の2つであり，それぞれの降下方向$-\nabla g_{1}$と$-\nabla g_{2}$の2つのベクトルの間に$-\nabla f$が「入って」いる．

<div style="text-align:center">

</div>

### Karush-Kuhn-Tucker条件と Lagrange関数
一般に，非線形最適化問題:
$$\begin{align}
\min_{\boldsymbol{x}} &f(\boldsymbol{x})\\
\text{s.t.} & g_{j}(\boldsymbol{x}) \geq 0, \quad j = 1, \cdots, M
\end{align}$$
の最適性条件は，
$$\begin{align}
&-\nabla f(\boldsymbol{x}^{\ast}) = -\sum_{j=1}^{M} \lambda_{j} \nabla g_{j}(\boldsymbol{x}^{\ast})\\
&\begin{cases}
\lambda_{j} > 0 \rightarrow g_{j}(\boldsymbol{x}^{\ast}) = 0\\
\lambda_{j} = 0 \leftarrow g_{j}(\boldsymbol{x}^{\ast}) > 0
\end{cases} \quad j = 1, \cdots, M
\end{align}
$$
で表され，提唱者の名前に基づいて **Karush-Kuhn-Tucker条件 (KKT条件)** と呼ばれる．

KKT条件において，各制約条件の「重み」に相当する$\boldsymbol{\lambda}=(\lambda_{j}: j = 1, \cdots, M)$は， **Lagrange乗数** (あるいは**双対変数**)と呼ばれる．KKT条件は，Lagrange 乗数を用いた以下の **Lagrange関数(Lagrangian)**:
$$\begin{align}
L(\boldsymbol{x}, \boldsymbol{\lambda}) &= f(\boldsymbol{x}) - \sum_{j=1}^{M} \lambda_{j} g(\boldsymbol{x})\\
&= f(\boldsymbol{x}) - \boldsymbol{\lambda}^{\top} \boldsymbol{g}(\boldsymbol{x})
\end{align}$$
を，$\boldsymbol{x}$について最小化すると同時に$\boldsymbol{\lambda}$について最大化する問題の最適性条件としても解釈できる．すなわち，無制約最適性条件：
$$
\nabla_{\boldsymbol{x}} L(\boldsymbol{x}^{\ast}, \boldsymbol{\lambda}^{\ast}) = \nabla f(\boldsymbol{x}^{\ast}) - \sum_{j=1}^{M} \lambda_{j}^{\ast} \nabla g_{j}(\boldsymbol{x}^{\ast}) = \boldsymbol{0}
$$
に，相補性条件：
$$
\begin{cases}
\lambda_{j}^{\ast} > 0 \rightarrow g_{j}(\boldsymbol{x}^{\ast}) = 0\\
\lambda_{j}^{\ast} = 0 \leftarrow g_{j}(\boldsymbol{x}^{\ast}) > 0
\end{cases} \quad j = 1, \cdots, M
\quad \Leftrightarrow
\quad \begin{cases}
{\boldsymbol{\lambda}^{\ast}}^{\top}
\boldsymbol{g}(\boldsymbol{x}^{\ast}) = 0\\
\boldsymbol{\lambda}^{\ast} \geq \boldsymbol{0}, \quad \boldsymbol{g}(\boldsymbol{x}^{\ast}) \geq \boldsymbol{0}
\end{cases}
$$
を加えたものと見なせる．$\nabla_{\boldsymbol{\lambda}} L(\boldsymbol{x}, \boldsymbol{\lambda}) = -\boldsymbol{g}(\boldsymbol{x})$であることに注意すれば，KKT条件は，
$$\begin{align}
&\nabla_{\boldsymbol{x}} L(\boldsymbol{x}^{\ast}, \boldsymbol{\lambda}^{\ast}) = \boldsymbol{0}\\
&
\begin{cases}(\boldsymbol{\lambda}^{\ast})^{\top}
\nabla_{\boldsymbol{\lambda}} L(\boldsymbol{x}^{\ast}, \boldsymbol{\lambda}^{\ast}) = 0, \\
\boldsymbol{\lambda}^{\ast} \geq \boldsymbol{0}, \quad \nabla_{\boldsymbol{\lambda}} L(\boldsymbol{x}^{\ast}, \boldsymbol{\lambda}^{\ast})\leq \boldsymbol{0}
\end{cases}
\end{align}$$
と簡潔に表せる．

なお，$\boldsymbol{g}(\boldsymbol{x}) = (g_{j}(\boldsymbol{x}): j = 1, \cdots, M)$の Jacobian を
$$
\nabla \boldsymbol{g} = \begin{bmatrix}
\frac{\partial g_{1}}{\partial x_{1}} & \cdots & \frac{\partial g_{1}}{\partial x_{N}}\\
\vdots & \ddots & \vdots \\
\frac{\partial g_{M}}{\partial x_{1}} & \cdots & \frac{\partial g_{M}}{\partial x_{N}}
\end{bmatrix} \in \mathcal{R}^{M\times N}
$$
で表せば，Lagrangianの勾配は以下のように表せる：
$$\begin{align}
\nabla_{\boldsymbol{x}} L(\boldsymbol{x}, \boldsymbol{\lambda}) &=
\nabla_{\boldsymbol{x}} \left\{f(\boldsymbol{x}) - \boldsymbol{\lambda}^{\top} \boldsymbol{g}(\boldsymbol{x})\right\}\\
&= \nabla f(\boldsymbol{x}) - \nabla \boldsymbol{g}(\boldsymbol{x})^{\top} \boldsymbol{\lambda}
\end{align}$$
## いくつかの特殊ケースの最適性条件
ここまでは汎用的な最適性条件について述べたが，いくつかのよく使われる特殊ケースについての最適性条件を整理しておこう．なお，以下では，簡単のため，最適解であることを表す${\ast}$を省略している．

### 非負制約+不等式制約の場合
$M$本の不等式制約$g_{j}(\boldsymbol{x}) \geq 0\ (j = 1, \cdots, M)$に非負制約$\boldsymbol{x} \geq \boldsymbol{0}$が加わった問題：
$$\begin{align}
\min_{\boldsymbol{x}} & f(\boldsymbol{x}) \\
\text{s.t.} & \boldsymbol{g}(\boldsymbol{x}) \geq \boldsymbol{0} \\
& \boldsymbol{x} \geq \boldsymbol{0}
\end{align}$$
の最適性条件は，各制約条件に対応した Lagrange乗数を$\boldsymbol{\lambda} = (\lambda_{j}: j=1, \cdots, M)$とし， Lagrangian を
$$
L(\boldsymbol{x}, \boldsymbol{\lambda}) = f(\boldsymbol{x}) - \sum_{j=1}^{M} \lambda_{j} g_{j}(\boldsymbol{x})
$$
と定義すると，以下のように表せる：
$$\begin{align}
&\begin{cases}
\boldsymbol{x}^{\top} \nabla_{\boldsymbol{x}} L(\boldsymbol{x}, \boldsymbol{\lambda}) = 0\\
\boldsymbol{x} \geq \boldsymbol{0}, \quad \nabla_{\boldsymbol{x}} L(\boldsymbol{x}, \boldsymbol{\lambda}) \geq \boldsymbol{0}
\end{cases}\\
&\begin{cases}\boldsymbol{\lambda}^{\top}\nabla_{\boldsymbol{\lambda}} L(\boldsymbol{x}, \boldsymbol{\lambda}) = 0, \\
\boldsymbol{\lambda} \geq \boldsymbol{0}, \quad \boldsymbol{\lambda}^{\top}\nabla_{\boldsymbol{\lambda}} L(\boldsymbol{x}, \boldsymbol{\lambda})\leq \boldsymbol{0}
\end{cases}
\end{align}
$$
要素ごとに書き下せば，
$$\begin{align}
&\begin{cases}
x_{i} > 0 & \rightarrow \frac{\partial f}{\partial x_{i}}(\boldsymbol{x}) - \sum_{j=1}^{M}\lambda_{j} \frac{\partial g_{j}}{\partial x_{i}}(\boldsymbol{x}) = 0\\
x_{i} = 0 & \leftarrow \frac{\partial f}{\partial x_{i}}(\boldsymbol{x}) - \sum_{j=1}^{M}\lambda_{j} \frac{\partial g_{j}}{\partial x_{i}}(\boldsymbol{x}) > 0\\
\end{cases} && i = 1, \cdots, N\\
&\begin{cases}
\lambda_{j} > 0 &\rightarrow g_{j}(\boldsymbol{x}) = 0\\
\lambda_{j} = 0 &\leftarrow g_{j}(\boldsymbol{x}) > 0
\end{cases} && j = 1, \cdots, M
\end{align}$$

### 等式制約のみの場合
制約条件が等式のみの最適化問題：
$$\begin{align}
\min_{\boldsymbol{x}} &f(\boldsymbol{x})\\
\text{s.t.} & g_{j}(\boldsymbol{x}) = 0, \quad j = 1, \cdots, M
\end{align}$$
については，その最適性条件が(非線形)連立方程式となる．

等式制約の場合は**常に全ての制約条件が有効**となるため，最適性条件を「制約条件が有効か否か」で場合分けする必要がない．従って，最適解においては，目的関数の降下方向$-\nabla f$が，全ての制約条件の降下方向$-\nabla g_{j} \ (j = 1, \cdots, M)$の合成に一致する：
$$
-\nabla f(\boldsymbol{x}) = - \sum_{j=1}^{M} \lambda_{j} \nabla g_{j}(\boldsymbol{x}) = - \nabla \boldsymbol{g}(\boldsymbol{x})^{\top} \boldsymbol{\lambda}
$$
従って，最適性条件は，$\boldsymbol{x}$と$\boldsymbol{\lambda}$に関する以下の連立方程式として表される：
$$\begin{align}
& \nabla f(\boldsymbol{x}) - \nabla \boldsymbol{g}(\boldsymbol{x})^{\top} \boldsymbol{\lambda} = \boldsymbol{0}\\
& \boldsymbol{g}(\boldsymbol{x}) = \boldsymbol{0}
\end{align}$$

最適化問題の中でも，特に下記の等式制約つき二次計画問題は，最適解が解析的に得られることで知られている：
$$\begin{align}
\min_{\boldsymbol{x}} &f(\boldsymbol{x}) = \frac{1}{2} \boldsymbol{x}^{\top} \boldsymbol{Q} \boldsymbol{x} + \boldsymbol{c}^{\top} \boldsymbol{x}\\
\text{s.t.} & \boldsymbol{g}(\boldsymbol{x}) = - \boldsymbol{A} \boldsymbol{x} + \boldsymbol{b} = \boldsymbol{0}
\end{align}$$
ただし，$\boldsymbol{Q}$および$\boldsymbol{c}$は，それぞれ，$N$次元の対称半正定値行列および$N$次元列ベクトルである．$\boldsymbol{A}$および$\boldsymbol{b}$は，それぞれ，$M$行$N$列の行列および$M$次元列ベクトルである．

> $\boldsymbol{g}(\boldsymbol{x}) = \boldsymbol{A} \boldsymbol{x} - \boldsymbol{b}$としても等価だが，ここでは，後述する最適性条件が対称になるように符号を揃えている．
<!--
$$\begin{align}
\boldsymbol{A} &= \begin{bmatrix}
a_{11} & \cdots & a_{1N}\\
\vdots & \ddots & \vdots \\
a_{M1} & \cdots & a_{MN}
\end{bmatrix}
&
\boldsymbol{b} &= \begin{bmatrix}b_{1} \\ \vdots \\ b_{M}\end{bmatrix}
\end{align}$$
$$
\boldsymbol{g}(\boldsymbol{x}) = \boldsymbol{A} \boldsymbol{x} - \boldsymbol{b}
$$
-->

この場合， 目的関数の勾配$\nabla f(\boldsymbol{x})$および制約条件左辺$\boldsymbol{g}(\boldsymbol{x})$のJacobian$\nabla \boldsymbol{g}(\boldsymbol{x})$は，それぞれ，
$$\begin{align}
\nabla \boldsymbol{f}(\boldsymbol{x}) &= \boldsymbol{Q} \boldsymbol{x} + \boldsymbol{c}\\
\nabla \boldsymbol{g}(\boldsymbol{x}) &= - \boldsymbol{A}
\end{align}$$
であるから，最適性条件は，以下の線形連立方程式となる：
$$\begin{align}
& \boldsymbol{Q} \boldsymbol{x} + \boldsymbol{c} - \boldsymbol{A}^{\top} \boldsymbol{\lambda} = \boldsymbol{0}\\
& - \boldsymbol{A} \boldsymbol{x} + \boldsymbol{b} = \boldsymbol{0}
\end{align}$$
あるいはまとめて
$$
\begin{bmatrix}
\boldsymbol{Q} & - \boldsymbol{A}^{\top}\\
-\boldsymbol{A} & \boldsymbol{0}
\end{bmatrix}
\begin{bmatrix}\boldsymbol{x} \\ \boldsymbol{\lambda}
\end{bmatrix}
= - \begin{bmatrix}\boldsymbol{c}\\\boldsymbol{b}
\end{bmatrix}
$$
と記述できる．

$\boldsymbol{Q}$が逆行列を持つなら，1つ目の方程式より
$$
\boldsymbol{x} = \boldsymbol{Q}^{-1}\left(\boldsymbol{A}^{\top} \boldsymbol{\lambda} - \boldsymbol{c}\right)
$$
であるから，これを2つ目に代入すれば
$$
\boldsymbol{A} \boldsymbol{Q}^{-1} \boldsymbol{A}^{\top} \boldsymbol{\lambda} - \boldsymbol{A}\boldsymbol{Q}^{-1}\boldsymbol{c} - \boldsymbol{b} = \boldsymbol{0}
$$
を得る．以上を整理すれば，最適解は以下のように解析的に求められる：
$$\begin{align}
\boldsymbol{x} &= \boldsymbol{Q}^{-1} \boldsymbol{A}^{\top}\left[\boldsymbol{A} \boldsymbol{Q}^{-1} \boldsymbol{A}^{\top}\right]^{-1}
\left(\boldsymbol{b} + \boldsymbol{A} \boldsymbol{Q}^{-1}\boldsymbol{c}\right)- \boldsymbol{Q}^{-1} \boldsymbol{c}\\
\boldsymbol{\lambda} &= \left[\boldsymbol{A} \boldsymbol{Q}^{-1} \boldsymbol{A}^{\top}\right]^{-1}\left(\boldsymbol{b} + \boldsymbol{A} \boldsymbol{Q}^{-1}\boldsymbol{c}\right)
\end{align}$$

### 線形等式制約と非負制約
道路ネットワーク均衡モデルなど，経済モデルの多くでは「経済主体の総数は一定であり，各戦略を選択する主体数は非負」という状態空間を持つことが多い．

$N$次元の未知変数$\boldsymbol{x} = (x_{1}, \cdots, x_{N})$について，
$M$本の線形等式制約および非負制約を持つ最適化問題を考える：
$$\begin{align}
\min_{\boldsymbol{x}} & f(\boldsymbol{x}) \\
\text{s.t.} & \boldsymbol{A} \boldsymbol{x} = \boldsymbol{b}\\
& \boldsymbol{x} \geq \boldsymbol{0}
\end{align}$$
ここで，$\boldsymbol{A} \in \mathcal{R}^{M\times N}, \boldsymbol{b} \in \mathcal{R}^{M}$は既知の行列・ベクトルである．この問題の最適性条件は，Lagrange乗数を$\boldsymbol{\lambda} = (\lambda_{1}, \cdots, \lambda_{M})$とし，Lagrangianを
$$
L(\boldsymbol{x}, \boldsymbol{\lambda}) = f(\boldsymbol{x}) - \boldsymbol{\lambda}^{\top} \left(\boldsymbol{A} \boldsymbol{x} - \boldsymbol{b}\right)
$$
と定義すると，$\nabla_{\boldsymbol{x}} L(\boldsymbol{x}, \boldsymbol{\lambda}) = \nabla f(\boldsymbol{x}) - \boldsymbol{A}^{\top} \boldsymbol{\lambda}$より，最適性条件は以下の式で表される：
$$\begin{align}
&\begin{cases}
\boldsymbol{x}^{\top} \left\{\nabla f(\boldsymbol{x}) - \boldsymbol{A}^{\top} \boldsymbol{\lambda}\right\} = 0\\
\boldsymbol{x} \geq \boldsymbol{0}, \quad \nabla f(\boldsymbol{x}) - \boldsymbol{A}^{\top} \boldsymbol{\lambda} \geq \boldsymbol{0}
\end{cases}
\\
& \boldsymbol{A} \boldsymbol{x} - \boldsymbol{b} = \boldsymbol{0}
\end{align}$$
要素ごとに書き下せば，
$$\begin{align}
&\begin{cases}
x_{i} > 0 & \rightarrow \frac{\partial f}{\partial x_{i}}(\boldsymbol{x}) - \sum_{j=1}^{M} \lambda_{j} a_{ji} = 0\\
x_{i} = 0 & \leftarrow \frac{\partial f}{\partial x_{i}}(\boldsymbol{x}) - \sum_{j=1}^{M} \lambda_{j} a_{ji} > 0
\end{cases}
&& i = 1, \cdots, N
\\
&\sum_{i=1}^{N} a_{ji} x_{i} = b_{j} && j = 1, \cdots, M
\end{align}$$
となる．

## 練習問題
次のように1対の起点(O)・終点(D)ペアを3本のリンクが結ぶ道路ネットワークを考える．

<div style="text-align: center;">


</div>

リンク$a=1,2,3$について，交通量（各リンクの利用者数）を$v_{a}$で表し，交通量に対する所要時間を線形関数$t_{a}(v_{a}) = d_{a} v_{a} + e_{a}$で表す．ただし，$d_{a}, e_{a}$は，それぞれ，リンクごとに定められた非負の定数とする．

以下では，状態変数を3次元ベクトル$\boldsymbol{v} = (v_1, v_2, v_3)$で表し，それに対応するリンク所要時間を
$$\begin{align}
\boldsymbol{t}(\boldsymbol{v}) &= \boldsymbol{D} \boldsymbol{v} + \boldsymbol{e}\\
&= \begin{bmatrix}
d_{1} \\
& d_{2}\\
& & d_{3}
\end{bmatrix}
\begin{bmatrix}
v_{1} \\ v_{2} \\ v_{3}
\end{bmatrix} +
\begin{bmatrix}
e_1 \\ e_2 \\ e_3
\end{bmatrix}
\end{align}$$
で表すことにする．

起点から終点まで移動する利用者数(交通需要)を所与の定数$Q$で表す．このとき，リンク交通量は以下の制約を満たす必要がある：
- フロー保存則(利用者の総数は一定)：
$$\sum_{a=1,2,3} v_{a} = Q$$
あるいは$\boldsymbol{1}^{\top} = \begin{bmatrix} 1& 1& 1\end{bmatrix}$とすれば，
$$\boldsymbol{1}^{\top} \boldsymbol{v} = Q$$
- 非負制約：
$$v_{a} \geq 0, \quad a=1, 2, 3 \quad \Leftrightarrow \quad \boldsymbol{v} \geq \boldsymbol{0}$$

ネットワーク全体での総走行時間（ie. 各リンクの交通量と所要時間の積の総和）を
$$\begin{align}
f(\boldsymbol{v}) &= \sum_{a=1,2,3} v_{a} t_{a}(v_{a})\\
&= \sum_{a=1,2,3} \left(D_{a}v_{a}^{2} + e_{a} v_{a}\right)\\
&= \boldsymbol{v}^{\top} \boldsymbol{D} \boldsymbol{v} + \boldsymbol{v}^{\top} \boldsymbol{e}
\end{align}$$ で表す．

このとき，以下の問に答えよ．
1. 以下の総走行時間最小化問題の最適性条件を書き下せ：
$$\begin{align}
\min_{\boldsymbol{v}} \quad & f(\boldsymbol{v}) = \boldsymbol{v}^{\top} \boldsymbol{D} \boldsymbol{v} + \boldsymbol{v}^{\top} \boldsymbol{e}\\
\text{s.t.} \quad &\boldsymbol{1}^{\top} \boldsymbol{v} = Q\\
& \boldsymbol{v} \geq \boldsymbol{0}
\end{align}$$
2. 定数$\boldsymbol{D}, \boldsymbol{e}, Q$が以下のように与えられるとき，最適な交通量パターン$\boldsymbol{v}^{\ast}$および最適値$f(\boldsymbol{v}^{\ast})$を求めよ．その際， ad hoc に$\boldsymbol{v}^{\ast} > \boldsymbol{0}$を仮定して良い：
$$\begin{align}\boldsymbol{D} &= \begin{bmatrix}1\\& 2\\ & & 3\end{bmatrix},& \boldsymbol{e} &= \begin{bmatrix}2 \\ 1 \\ 0\end{bmatrix},& Q&= 4\end{align}$$
3. 交通量が$\boldsymbol{v} = \left(\frac{17}{11}, \frac{14}{11}, \frac{13}{11}\right)$であるとき，どのリンクの所要時間も等しくなる． この時の交通量と総走行時間を，上で求めた総走行時間最小化問題の解と比較し， どのような交通量の調整によって総走行時間が減少させられているのかを考察せよ．