最適化理論と方法

WARNING

最適化問題

数学モデル

$$ \min f(\vec{x}),\vec{x}\in \vec{R^{n}} $$$$ \text{s.t.}{ \begin{cases} c_i(x)=0,& i \in E = {1,2,\cdots,l}\\ c_i(\vec{x})\ge 0,& i \in I = {l+1,\cdots,l+m}\\ \end{cases}} $$

ここで，

• $\vec{x}=(x_1,x_2,\cdots,x_n)^T$ は意思決定変数
• $f(\vec{x})$ は目的関数
• s.t.（subject to）は制約条件を表す

分類

1. 時間による分類
   1. 静的問題
   2. 動的問題
2. 制約条件による分類
   1. 制約付き問題
   2. 無制約問題
3. 目的関数と制約条件が線形かどうか
   1. 線形計画
   2. 非線形計画
4. 目的関数と制約条件が凸関数かどうか
   1. 凸最適化問題
   2. 非凸最適化問題

二次形式行列

二次形式：

$$ \begin{align} f &=x_1^2-3x_3^2-4x_1x_2+x_2x_3\\ &=(x_1,x_2,x_3) \begin{bmatrix} 1 & -2 & 0\\ -2 & 0 & \frac{1}{2}\\ 0 & \frac{1}{2} & -3\\ \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3\\ \end{bmatrix}\\ &= \vec{X^T} A \vec{X}\\ \end{align} $$

二次形式行列：

$$ \begin{bmatrix} 1 & -2 & 0\\ -2 & 0 & \frac{1}{2}\\ 0 & \frac{1}{2} & -3\\ \end{bmatrix} $$

Hessian 行列

二変数二次関数を例にすると：

$$ \nabla^2 f(x_1,x_2)= \begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2}\\ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2}\\ \end{bmatrix} $$

実行可能解

• 実行可能解：すべての制約条件を満たす解。
• 実行可能集合（許容集合、実行可能領域）：すべての実行可能解からなる集合。
• 最適化問題：実行可能集合の中から目的関数を最大または最小にする点を探す問題。
• 停留点：$\nabla f(x_0)=0$ を満たすとき，$x_0$ を停留点という。
• 鞍点：$x_0$ が停留点ではあるが極値点ではないとき，鞍点という。

凸集合

定義

平面において，図形内部の任意の二点を結ぶ線分がそのまま図形内部に含まれるとき，その図形を凸集合という。

性質

1. 凸集合の共通部分は凸集合である
2. 凸集合を比例拡大・縮小しても凸集合である
3. 凸集合の和集合ではなく和集合和 $D_1+D_2$ は凸集合である
   • $D_1,D_2$ を凸集合とすると，$D_1+D_2=\{z|z=x+y,x \in D_1,y \in D_2\}$ は凸集合である。
4. 凸集合の線形結合は凸集合である。

よくある凸集合

1. 空集合
2. ユークリッド空間全体 $\vec{R^n}$
3. 超平面 $H=\{x \in \vec{R^n} | a_1x_1+a_2x_2+\cdots +a_nx_n=b\}$
4. 半空間 $H^+=\{x \in \vec{R^n} | a_1x_1+a_2x_2+\cdots +a_nx_n \ge b\}$

凸結合

$x_i \in \vec{R^n},i=1,2,\cdots ,k$ とし，実数 $\lambda_i \ge 0,\sum^k_{i=1}\lambda_i=1$ のとき， $x=\sum^k_{i=1}\lambda_ix_i$ を $x_1,x_2,\cdots , x_k$ の凸結合という。
凸集合内の有限個の点の凸結合は，やはりその凸集合に属する。

極点

$D$ を凸集合，$x \in D$ とする。$D$ の中に異なる二点 $y,z$ と実数 $\alpha \in (0,1)$ が存在して $x=\alpha y+(1-\alpha)z$ と表せないとき，$x$ を $D$ の極点という。

平たく言えば，平面上の五角形なら極点は頂点であり，半円なら直径の両端点と円弧上の頂点に当たる。

凸関数

定義

凸集合上で定義された関数 $f(x)$ が，その凸集合内の任意の二点 $x_1,x_2$ に対して

$$ f(\alpha x_1+(1-\alpha)x_2) \le \alpha f(x_1)+(1-\alpha)f(x_2) $$

を満たすとき，$f$ を凸関数という。
不等号が厳密不等号 $\lt$ なら，厳密凸関数という。

判定

1. 多変数関数の Hessian 行列が半正定なら，その関数は凸関数である。
2. Hessian 行列が正定なら，その関数は厳密凸関数である。
3. 多変数線形関数は $\vec{R^n}$ 上の凸関数である。

凸最適化問題

定義

目的関数と制約関数がいずれも凸関数である最適化問題。

• 凸最適化の実行可能集合は凸集合である
• 任意の局所最適解は大域最適解である
• 目的関数が厳密凸関数なら，局所最適解は存在しかつ一意である

線形計画

形式

非標準形

• 目的関数：$\max z=\sum^{n}_{j=1}c_jx_j=CX$
• 係数行列： $$ A= \begin{bmatrix} a_{11} & \cdots & a_{1n}\\ \vdots & \ddots & \vdots\\ a_{m1} & \cdots & a_{mn}\\ \end{bmatrix} =(P_1,P_2,\cdots,P_n) $$
• 資源ベクトル：$b=\begin{bmatrix} b_1\\ \vdots \\ b_m\\ \end{bmatrix}$
• 意思決定変数ベクトル：$X=(x_1,x_2,\cdots , x_n)^T$
• 制約条件： $$ \begin{cases} \sum^{n}_{j=1}a_{ij}x_j=b_i,&i=1,2,\cdots,m\\ x_j \ge 0,& j=1,2,\cdots,n\\ \end{cases} $$ $$ \begin{cases} AX=b\\ X \ge \vec{0} \end{cases} $$

標準形

1. 最大化問題を最小化問題へ変換する
2. スラック変数：$\le$ 制約に対して導入し，等式にする
3. 余剰変数：$\ge$ 制約に対して導入し，等式にする
4. 自由変数：実際の問題で自由に値を取れる変数で，$x_i=x'-x''$ と表す

$$ \begin{cases} \min f(x_1,x_2,\cdots , x_n)\\ \text{s.t.} \begin{cases} h_j(x_1,x_2,\cdots,x_n)=0&(j=1,2,\cdots)\\ x_j \ge 0\\ \end{cases} \end{cases} $$

基底行列

• 基底（基底行列）：係数行列の中の最大正則部分行列。
  • 係数行列 $A$ が $m \times n$ 行列で，$rank(A)=m$ のとき，任意の $m \times m$ 正則部分行列が基底行列となる。
• 基底変数：基底に含まれる列ベクトルに対応する未知数。
• 非基底変数：基底変数でない未知数。
• 基本解：非基底変数をすべて 0 として得られる解。
• 非退化基本解：基本解における非零成分の個数が制約式の本数に等しいもの。そうでなければ退化基本解。
• 基本実行可能解：$\text{s.t.}$ の非負条件を満たす基本解。
• 最適基底実行可能解：すべての基本実行可能解のうち，目的関数値を最適にするもの。

線形計画解の性質

1. 線形計画の実行可能集合は凸集合である
2. 最適解が存在するなら，実行可能集合の頂点で達成される

単体法

判定数（検定数）

各未知数には一つの判定数が対応する

$$ \sigma_j=C^T_J \vec{P_j}-c_j=\sum^{m}_{i=1}c_ia_{ij}-c_j $$

• $C^T$ は目的関数の係数行
• $C^T_J$ は基底変数の目的関数係数
• $P_j$ は行列 $A$ の第 $j$ 列
• $c_i$ は第 $i$ 個の基底変数の目的関数係数
• $c_j$ は目的関数中の第 $j$ 個の変数の係数で，$c_i$ とは無関係

すべての判定数が 0 以下なら，その基底実行可能解は最適解である。

一般に，基底変数の判定数は 0 である。

基底変換

基底行列の選択

最初は単位行列を基底行列として選ぶのが望ましい。初期基底実行可能解と判定数を計算する。

初期単体表の作成

	$P_1$	$P_2$	$\cdots$	$P_n$	$\vec{b}$
係数行列	$a_{11}$	$a_{12}$	$\cdots$	$a_{1n}$	$b_1$
	$a_{21}$	$a_{22}$	$\cdots$	$a_{2n}$	$b_2$
	$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$
	$a_{m1}$	$a_{m2}$	$\cdots$	$a_{mn}$	$b_m$
判定数	$\sigma_1$	$\sigma_2$	$\cdots$	$\sigma_n$	最適値

入る列の選択

判定数が正なら，その列には改良の余地があるので，その列 $P_j$ を入る列とし，対応する変数 $x_j$ を入る変数とする。

主元の選択

入る列の中で正の成分 $a_{ij}$ を取り，対応する $b$ の要素をそれで割って比を求め，最小のものを与える $a_{ij}$ を主元とする。
判定数が正であっても，その列の要素がすべて負なら，その線形計画には最適解が存在しない。

初等行変換

主元を 1 にし，その列の他の成分を 0 にする。
幾何学的には，実行可能領域の頂点を移ることを意味する。

出る列

更新後の係数行列に応じて新しい基底行列を選ぶ。元の基底行列から置き換えられた列が出る列であり，その対応変数が出る変数である。
その後，判定数を再計算し，新しい単体表を作る。

次の基底変換

判定数行が更新されて新たに正の判定数が現れたら，その列を新しい入る列とし，主元を選んで再び初等行変換を行う。

結果

すべての判定数が 0 以下になったとき，$\vec{b}$ の値が基底変数の値であり，非基底変数は 0 となる。これらをまとめたものが最適解であり，目的関数に代入すると最小値が得られる。

単体法の適用条件

1. 非同次項がすべて非負である
2. 実行可能解が存在する
3. スラック変数と非基底変数の値の積の和が 0 である
4. 問題が凸な実行可能領域上の線形計画問題である
5. 実行可能解集合が有限である

人工変数法

係数行列に単位行列が含まれない場合，人工変数を導入して人為的に単位行列を構成することが多い。

線形計画問題の制約条件が $\sum^{n}_{j=1}a_{ij}=b_i(i=1,2,\cdots ,m)$ の形で与えられているとする。それぞれの制約に人工変数 $x_{n+1},x_{n+2},\cdots,x_{n+m}$ を加え，それらを基底変数とし，それ以外を 0 と置けば，$x^{(0)}=(0,0,\cdots,0,b_1,b_2,\cdots,b_m)^T$ という実行可能解が得られる。
この解から基底変換を進め，人工変数を含まない最適解へと到達する。

すべての判定数が負になってもなお非零の人工変数が残っている場合，元の問題には実行可能解が存在しない。

Big-M 法

最小化問題では，制約条件に人工変数を入れた後，人工変数の目的関数係数を $M$（$M \in \vec{R^+}$）とする。
最小目的関数値を得るには，人工変数が 0 になるよう基底変換を繰り返す。最大化問題では $M \in \vec{R^-}$ とする。

退化の場合

単体法が循環に陥る場合でも，問題に最適解が存在するなら，以下の方法で循環を避けられる。

摂動法

改良単体法

線形計画の双対理論

線形計画の双対問題の形式

対称形式

元問題

$$ \begin{cases} \min f=\vec{c^T}\vec{x}\\ \text{s.t.} \begin{cases} \vec{A}\vec{x} \ge \vec{b}\\ \vec{x} \ge \vec{0} \end{cases} \end{cases} $$

双対問題

$$ \begin{cases} \max w=\vec{b^T}\vec{y}\\ \text{s.t.} \begin{cases} \vec{A^T}\vec{y} \le \vec{c}\\ \vec{y} \ge \vec{0}\\ \end{cases} \end{cases} $$

対応関係：

• （1）元問題の制約条件数は，双対問題の変数の個数に等しい
• （2）元問題の目的関数係数は，双対問題の制約条件の右辺になる
• （3）元問題が最小化なら，双対問題は最大化になる
• （4）元問題の制約が「$\ge$」なら，双対問題の制約は「$\le$」になる

非対称形式

元問題

$$ \begin{cases} \min f=\vec{c^T}\vec{x}\\ \text{s.t.} \begin{cases} \vec{A}\vec{x} = \vec{b}\\ \vec{x} \ge \vec{0} \end{cases} \end{cases} $$

双対問題

$$ \begin{cases} \max w=\vec{b^T}\vec{y}\\ \text{s.t.} \begin{cases} \vec{A^T}\vec{y} \le \vec{c}\\ \vec{y} \text{は自由変数} \end{cases} \end{cases} $$

一般の場合

元問題に $\le,\ge,=$ が混在している場合は，まずスラック変数と余剰変数を導入して等式にそろえ，その後で非対称形式を使って双対問題を作る。

双対単体法

• 単体法：まず $\vec{b} \ge 0$ を満たし，その後で判定数 $\le 0$ に基づいて反復する
• 双対単体法：まず判定数 $\le 0$ を満たし，その後で $\vec{b} \ge 0$ に基づいて反復する

判定数 $\le 0$ を確保する

出る変数の選択

$b_i \lt 0$ が存在する場合，その中で最小の $\min b_i$ をもつ行を出る行とし，対応する変数を出る変数とする。

入る変数の選択

判定数を出る行の負の係数 $a_{ij} \lt 0$ で割り，その結果が最小となる列を入る列とし，対応する変数を入る変数とする。

行変換

行変換によって入る列を基底行列に対応する単位列へ変形する。このとき $\vec{b}$ も更新される。
その後，判定数を再計算し，依然として 0 以下であることを確認する。

次の基底変換

まだ負の $b_i \lt 0$ が残っていれば，最小の $\min b_i$ を選んで次の基底変換を行う。

結果

すべての $b_i \ge 0$ となったとき，$\vec{b}$ は基底変数の最適解部分を与え，非基底変数は 0 となる。
それを目的関数に代入すれば，最大値または最小値が得られる。

感度分析