最適化問題を解く（その03/X） - 「大人の教養・知識・気付き」を伸ばすブログ

　不等式で書かれる制約条件は、上界を考えていくと、その不等式制約を等式制約に書き換えた新たな問題を考えることができる。このように等式問題に書き換えた問題は、元の問題に対して双対問題という。また元の問題を主問題と呼ぶ。主問題を双対問題に書き換えるための変数変換をスラック変換という。双対問題の双対問題は主問題である。
　具体的には、主問題

$\begin{aligned} \mathrm{Minimize}\ \ &{}^{t}\boldsymbol{c}\boldsymbol{x}\\ \mathrm{subject\ to}\ \ &A\boldsymbol{x}=\boldsymbol{b},\\ &\boldsymbol{x}\geq\boldsymbol{0} \end{aligned}$

に対して、

$\begin{aligned} \mathrm{Maximize}\ \ &{}^{t}\boldsymbol{b}\boldsymbol{y}\\ \mathrm{subject\ to}\ \ &{}^{t}A\boldsymbol{y}\leq\boldsymbol{c} \end{aligned}$

を双対問題という*3。

2.2.2　双対定理

　主問題と双対問題には密接な関係がある。

定理2.2　弱双対定理　主問題

$\begin{aligned} \mathrm{Minimize}\ \ &{}^t{}\boldsymbol{c}\boldsymbol{x}\\ \mathrm{subject\ to}\ \ &A\boldsymbol{x}=\boldsymbol{b},\\ &\boldsymbol{x}\geq\boldsymbol{0} \end{aligned}$

の任意の実行可能解 $\boldsymbol{x}$ および双対問題

$\begin{aligned} \mathrm{Maximize}\ \ &{}^t{}\boldsymbol{b}\boldsymbol{y}\\ \mathrm{subject\ to}\ \ &{}^t{}A\boldsymbol{y}+\boldsymbol{s}=\boldsymbol{c},\\ &\boldsymbol{s}\geq\boldsymbol{0} \end{aligned}$

の任意の実行可能解 $\boldsymbol{y},\boldsymbol{s}$ に対して、条件

$\begin{aligned} {}^{t}\boldsymbol{c}\boldsymbol{x}\geq{}^{t}\boldsymbol{b}\boldsymbol{y} \end{aligned}$

が成り立つ。

( $\because$ 　主問題と双対問題の制約を用いると、

$\begin{aligned} {}^{t}\boldsymbol{c}\boldsymbol{x}-{}^{t}\boldsymbol{b}\boldsymbol{y}&={}^{t}\boldsymbol{c}\boldsymbol{x}-{}^{t}(A\boldsymbol{x})\boldsymbol{y}\\ &={}^{t}\boldsymbol{c}\boldsymbol{x}-{}^{t}(\boldsymbol{c}-\boldsymbol{s})\boldsymbol{x}\\ &={}^{t}\boldsymbol{s}\boldsymbol{x}\geq0 \end{aligned}$

が成り立つ。　　 $\blacksquare$ )

　もし主問題の目的関数の値をいくらでも小さくできるのであれば、弱双対定理より双対問題は実行可能解を持たないことが分かる。また双対問題の目的関数の値がいくらでも大きくできるのであれば、主問題は実行可能解を持たない。さらに主問題および双対問題の実行可能解であって、目的関数の値が一致するものが見つかれば、それらは最適解である。次の定理はこれの逆を保証する。

定理2.3　強定常定理　主問題

$\begin{aligned} \mathrm{Minimize}\ \ &{}^t{}\boldsymbol{c}\boldsymbol{x}\\ \mathrm{subject\ to}\ \ &A\boldsymbol{x}=\boldsymbol{b},\\ &\boldsymbol{x}\geq\boldsymbol{0} \end{aligned}$

および双対問題

の双方が実行可能解を持つならば、両問題に最適解が存在し、最適解は一致する。

　次に線形計画問題の最適解を特徴づける最適性条件を述べる。

定理2.4　最適性条件　 $\boldsymbol{x}\in\mathbb{R}^n$ を主問題

$\begin{aligned} \mathrm{Minimize}\ \ &{}^t{}\boldsymbol{c}\boldsymbol{x}\\ \mathrm{subject\ to}\ \ &A\boldsymbol{x}=\boldsymbol{b},\\ &\boldsymbol{x}\geq\boldsymbol{0} \end{aligned}$

の実行可能解とし、 $\boldsymbol{y}\in\mathbb{R}^m,\boldsymbol{s}\in\mathbb{R}^n$ を双対問題

の実行可能解とする。これらがそれぞれの問題の最適解であるためには

$\begin{aligned} x_js_j=0,j=1,\cdots,n \end{aligned}$

が必要十分である。

　以上の条件をまとめると、線形計画問題の最適解が満たすべき必要十分条件は、

$\begin{aligned} A\boldsymbol{x}=\boldsymbol{b},\\ {}^{t}A\boldsymbol{y}+\boldsymbol{s}=\boldsymbol{c},\\ x_js_j=0,j=1,\cdots,n,\\ \boldsymbol{x}\geq\boldsymbol{0},\boldsymbol{s}\geq\boldsymbol{0} \end{aligned}$

で与えられる。この3つ目の条件を相補性条件といい、主問題の不等式制約 $x_j\geq0$ と双対問題の不等式制約 $s_j\geq0$ の少なくとも一方が最適解において有効であることを意味する。
　仮に最適解において、各 $j$ について $x_j$ および $s_j$ のどちらが $0$ になるかを知っていたとすると、 $x_j=0$ および $s_{j^{\prime}}=0(j\neq j^{\prime})$ という式が少なくとも $n$ 本存在する。他に $A\boldsymbol{x}=\boldsymbol{b}$ は $m$ 本および ${}^{t}A\boldsymbol{y}+\boldsymbol{s}=\boldsymbol{c}$ は $n$ 本の等式であるから、全部で $2n+m$ 本の線形方程式が存在する。未知数の数も $\boldsymbol{x},$ $\boldsymbol{y},$ $\boldsymbol{s}$ の $2n+m$ 個あるから、最適解を得るにはこの $2n+m$ 本の線形方程式を解けばよい。無論、最適解において $x_j$ および $s_j$ のどちらが $0$ なのかを事前に知ることは出来ない。すなわち最適解においてどの不等式制約が有効であるのかを見つけることが線形問題を解くことの本質であると言える。

2.3　線形計画問題の解法

　線形計画問題には、単体法と内点法という代表的な解法が存在する。

2.3.1　単体法

　標準形

$\begin{aligned} \mathrm{Minimize}\ \ &\boldsymbol{c}^{\mathrm{T}}\boldsymbol{x}\\ \mathrm{subject\ to}\ \ &A\boldsymbol{x}=\boldsymbol{b},\\ &\boldsymbol{x}\geq\boldsymbol{0} \end{aligned}$

を数値的に解くための方法として単体法が存在する。これは実行可能基底解を順々に辿ることで線形計画問題を解く手法で、1947年に $\mathrm{George}$ $\mathrm{Dantzig}$ が提案したもので、未だに有用な数値解法である。
　単体法の基本的な考えは、1組の実行可能基底解が与えられたときに目的関数値がより低くなるような新しい実行可能基底解を効率よく求めることである。線形計画問題の基本定理から、実行可能基底からの中に最適解が存在する。実行可能基底解の選び方は高々 ${}_{m}C_{n}$ 通りであるから、実行可能基底解を順に求めていくことで有限回の手順で最適解に到達すると期待される。

　 $A$ が $m\times n$ 行列( $m\lt n$ ) $A$ で階数は $m$ だとして、標準的な形態での線形計画問題

$\begin{aligned} \mathrm{Minimize}\ \ &\boldsymbol{c}^{\mathrm{T}}\boldsymbol{x}\\ \mathrm{subject\ to}\ \ &A\boldsymbol{x}=\boldsymbol{b},\\ &\boldsymbol{x}\geq\boldsymbol{0} \end{aligned}$

を考える。
　1組の基底解が与えられているとする。簡単のために行列 $A$ の初めの $m$ 本の列ベクトルが線形独立だと仮定すると、基底行列と基底変換は

$\begin{aligned} B&=\begin{bmatrix}\boldsymbol{a}_{1},&\cdots,&\boldsymbol{a}_{m}\end{bmatrix},\\ \boldsymbol{x}_B&=\begin{bmatrix}x_1\\\vdots\\x_m\end{bmatrix} \end{aligned}$

である。このとき $B$ は正則である。また非基底変数に対応する部分を

$\begin{aligned} B&=\begin{bmatrix}\boldsymbol{a}_{m+1},&\cdots,&\boldsymbol{a}_{n}\end{bmatrix},\\ \boldsymbol{x}_N&=\begin{bmatrix}x_{m+1}\\\vdots\\x_n\end{bmatrix} \end{aligned}$

とおく。更に目的関数の係数も同様に

$\begin{aligned} \boldsymbol{c}_{B}&=\begin{bmatrix}c_{1},&\cdots,&c_{m}\end{bmatrix}^{\mathrm{T}},\\ \boldsymbol{c}_{N}&=\begin{bmatrix}c_{m+1},&\cdots,&c_{n}\end{bmatrix}^{\mathrm{T}} \end{aligned}$

とおけば、

$\begin{aligned} A&=\begin{bmatrix}B&N\end{bmatrix},\\ \boldsymbol{x}&=\begin{bmatrix}\boldsymbol{x}_{B}\\\boldsymbol{x}_{N}\end{bmatrix},\\ \boldsymbol{c}&=\begin{bmatrix}\boldsymbol{c}_{B}\\\boldsymbol{c}_{N}\end{bmatrix} \end{aligned}$

と書ける。このとき等式制約 $A\boldsymbol{x}=\boldsymbol{b}$ は $B\boldsymbol{x}_B+N\boldsymbol{x}_N=\boldsymbol{b}$ と書けるから、両辺の左から $B^{-1}$ を掛けることで

$\begin{aligned} \boldsymbol{x}_B+B^{-1}N\boldsymbol{x}_N=B^{-1}\boldsymbol{b} \end{aligned}$

を得る。これより基底変数 $\boldsymbol{x}_B$ は非基底変数 $\boldsymbol{x}_N$ を用いて

$\begin{aligned} \boldsymbol{x}_B=B^{-1}\boldsymbol{b}-B^{-1}N\boldsymbol{x}_N \end{aligned}$

と表せる。これを目的関数に代入することで

$\begin{aligned} w=&\boldsymbol{c}^{\mathrm{T}}\boldsymbol{x}\\ =&\boldsymbol{c}_B^{\mathrm{T}}\boldsymbol{x}_B+\boldsymbol{c}_N^{\mathrm{T}}\boldsymbol{x}_N\\ =&\boldsymbol{c}_B^{\mathrm{T}}\left(B^{-1}\boldsymbol{b}-B^{-1}N\boldsymbol{x}_N\right)\\ &+\boldsymbol{c}_N^{\mathrm{T}}\boldsymbol{x}_N\\ =&\boldsymbol{c}_B^{\mathrm{T}}B^{-1}\boldsymbol{b}+\left(\boldsymbol{c}_N-\left(B^{-1}N\right)^{\mathrm{T}}\boldsymbol{c}_B\right)^{\mathrm{T}}\boldsymbol{x}_N \end{aligned}$

を得る。また単体乗数 $\boldsymbol{y}=\left(B^{-1}\right)^{\mathrm{T}}\boldsymbol{c}_B$ を用いれば、

$\begin{aligned} w=\boldsymbol{c}_B^{\mathrm{T}}B^{-1}\boldsymbol{b}+\left(\boldsymbol{c}_N-N^{\mathrm{T}}\boldsymbol{y}\right)^{\mathrm{T}}\boldsymbol{x}_N \end{aligned}$

とも表すことができる。
　以上を踏まえ、

$\begin{aligned} \bar{\boldsymbol{a}}_{i}&=B^{-1}\boldsymbol{a}_{i},\\ \bar{N}&=B^{-1}N,\\ \bar{\boldsymbol{b}}&=B^{-1}\boldsymbol{b},\\ \bar{\boldsymbol{c}}_{N}&=\boldsymbol{c}_{N}-\left(B^{-1}N\right)^{\mathrm{T}}=\boldsymbol{c}_{N}-N^{\mathrm{T}}\boldsymbol{y},\\ \bar{w}&=\boldsymbol{c}_B^{\mathrm{T}}B^{-1}\boldsymbol{b}=\boldsymbol{c}_B^{\mathrm{T}}\bar{\boldsymbol{b}} \end{aligned}$

とおけば、目的関数および等式制約は

$\begin{aligned} \boldsymbol{x}_B+\bar{N}\boldsymbol{x}_N&=\bar{\boldsymbol{b}},\\ \bar{\boldsymbol{c}}_N^{\mathrm{T}}\boldsymbol{x}_N-w&=\bar{w} \end{aligned}$

と整理できる。この形式を基底形式、辞書もしくは正準形と呼ぶ。また $\bar{\boldsymbol{c}}_N$ を相対費用係数と呼ぶ。基底形式において特に $\bar{\boldsymbol{b}}\geq\boldsymbol{0}$ であるとき、実行可能基底形式という。このときに非基底変数 $\boldsymbol{x}_N=\boldsymbol{0}$ とおけば現時点の実行可能基底変数 $\boldsymbol{x}_B=\bar{\boldsymbol{b}}$ と目的関数値 $w=\bar{w}$ が得られる。したがって1つの実行可能基底形式は1組の実行可能基底解

$\begin{aligned} \boldsymbol{x}=\begin{bmatrix}\boldsymbol{x}_B\\\boldsymbol{x}_N\end{bmatrix}=\begin{bmatrix}\bar{\boldsymbol{b}}\\\boldsymbol{0}\end{bmatrix}\geq\boldsymbol{0} \end{aligned}$

を決定できる。
　ここで $\bar{\boldsymbol{c}}_N\geq\boldsymbol{0}$ ならば既に最適解が得られたことになるから、ここでは $\bar{\boldsymbol{c}}_N$ の成分のうち負のものが存在すると仮定する。そのうちの1つを $\bar{c}_j\gt0$ とする。これと対応する $\boldsymbol{x}$ の成分 $x_j=0$ を少しだけ増加させると、主問題の目的関数の値は減少する。このように変更した $\boldsymbol{x}_N$ を用いて

$\begin{aligned} \boldsymbol{x}_B=A_B^{-1}(\boldsymbol{b}-A_N\boldsymbol{x}_N) \end{aligned}$

と定めれば、等式制約 $A\boldsymbol{x}=\boldsymbol{b}$ は満たされたままである。このとき $\boldsymbol{x}_B$ の成分のうち、目的関数の値が減少するものが存在しなければ、 $x_j$ をどれだけ大きくしても不等式制約 $\boldsymbol{x}_B\geq\boldsymbol{0}$ も満たされたままになる。そのような場合を除外すれば、 $\boldsymbol{x}_B$ の成分のいずれかが最初に $0$ に到達するまで $x_j$ を増やす。これで $0$ になった成分が非基底変数に変化し、 $x_j$ が基底変数に変わった新たな実行可能基底解が得られた。このような手続を枢軸変換という。
　枢軸変換により得られた実行可能基底解が非退化であれば、ある実行可能基底解から出発して枢軸変換を繰り返すことで主問題の目的関数の値はどんどん小さくなる。これを有限回繰り返すことで最適解に到達できる。これが単体法の基本的な考え方である*4。

　最適解に到達したか否かを具体的に判定する方法を考える。実行可能基底形式を吟味することで、3つの場合が考えられ、2つ目は更に2つに分けられる。

(1)		基底形式における $\begin{aligned}-\bar{w}=\bar{\boldsymbol{c}}_N^{\mathrm{T}}\boldsymbol{x}_N-w\end{aligned}$ において $\bar{\boldsymbol{c}}_N\geq\boldsymbol{0}$ ならば、もう1つの基底形式の式 $\begin{aligned}\boldsymbol{x}_B+\bar{N}\boldsymbol{x}_N=\bar{\boldsymbol{b}}\end{aligned}$ および $\boldsymbol{x}_N\geq\boldsymbol{0}$ を満たすような任意の $\boldsymbol{x}_N$ に対して $w=\bar{w}+\bar{\boldsymbol{c}}_N^{\mathrm{T}}\boldsymbol{x}_N\geq\bar{w}$ が成り立つから、これ以上、目的関数値が下がることはない。したがってこのときの実行可能基底解が最適解である。
(2)		(1)が成り立たない場合、すなわち ${}^{\exists}q\in\{m+1\leq q\leq n\}$ ならば、 $\begin{aligned}w=\bar{w}+\bar{c}_qx_q+\displaystyle{\sum_{j=m+1,j\neq q}^{n}\bar{c}_jx_j}\end{aligned}$ であるから、非基底変数 $x_q\gt0$ を増加させることで目的関数値が $\bar{c}_qx_q$ だけ減少する。複数の候補があり得る場合、 $\displaystyle{\min_{i}\bar{c}_i}=\bar{c}_q$ を選ぶのが普通である。以上のようにして $q$ を決めた後、 $x_q$ 以外の非基底変数を $0$ として $x_q$ のみを残せば実行可能基底形式は $\begin{aligned}\boldsymbol{x}_B&=\bar{\boldsymbol{x}}+x_q(-\bar{\boldsymbol{a}}_q)\\w&=\bar{w}+\bar{c}_qx_q\end{aligned}$ と書ける。 $\bar{\boldsymbol{a}}_q$ の成分の符号に応じて、この(2)は更に2つの場合に分けることができる。
	(a)	$-\bar{\boldsymbol{a}}_q\geq\boldsymbol{0}$ であるとき、任意の $x_q\gt0$ に対して $\boldsymbol{x}_B\geq\boldsymbol{0}$ となるため、非負制約は損なわれない。更に $x_q$ を増加させることで目的関数値をいくらでも減少できるため、この場合、目的関数は下に有界でない。
	(b)	$\bar{a}_{iq}\gt0$ となるような成分が存在するとき、 $x_q$ を増やしていくと目的関数値は確かに減少するものの、 $\boldsymbol{x}_B$ の第 $i$ 成分 $\bar{b}_i-x_q\bar{a}_{iq}$ が負になる。そこで $\bar{b}_i-x_q\bar{a}_{iq}=0$ を満たすような $x_q$ を選ばなければならない。この制約をすべての $i$ について満たさなければならないため、 $\begin{aligned}x_q=\displaystyle{\min_{\bar{a}_{iq}\gt0}\frac{\bar{b}_i}{\bar{a}_{iq}}}=\displaystyle{\frac{\bar{b}_p}{\bar{a}_{pq}}}\end{aligned}$ となるような番号 $p$ を選ぶ必要がある。もしそのような番号が複数ある場合は最も小さいものを選ぶものとする。このとき $\begin{aligned}\bar{b}_p-x_q\bar{a}_{pq}=\bar{b}_p-\left(\displaystyle{\frac{\bar{b}_p}{\bar{a}_{pq}}}\right)\bar{a}_{pq}=0\end{aligned}$ が成り立つ。そこで現在の基底変数 $x_p$ を基底から外し、現在の非基底変数 $x_q$ を基底に加える。このとき $\boldsymbol{a}_{1},\cdots,\boldsymbol{a}_{p-1},\boldsymbol{a}_{p+1},\cdots,$ $\boldsymbol{a}_{m}$ は線形独立であるから、 $\boldsymbol{x}_{B}^{*}=$ $\left[x_1,\right.$ $\cdots,$ $x_{p-1},$ $x_q,$ $x_{p+1},$ $\cdots,$ $\left.x_m\right]^{\mathrm{T}}$ は新しい基底変数になる。
(3)		$\begin{aligned}x_q=\displaystyle{\min_{\bar{a}_{iq}}\frac{\bar{b}_i}{\bar{a}_{iq}} }=\displaystyle{\frac{\bar{b}_p}{\bar{a}_{pq}}}\end{aligned}$ において $\bar{b}_p=0$ ならば、 $x_q=0$ であるから、目的関数値は減少しない。他方で退化していない場合、 $\bar{b}_p\gt0$ であるから、 $\begin{aligned}x_q=\displaystyle{\frac{\bar{b}_p}{\bar{a}_{pq}}}\gt0\end{aligned}$ となり、目的関数値は $\bar{c}_qx_q$ の絶対値だけ減少する。

　以上をまとめることで以下の定理を得る。

定理2.5　単体法の原理　実行可能な基底形式

$\begin{aligned} \boldsymbol{x}_B+\bar{N}\boldsymbol{x}_N&=\bar{\boldsymbol{b}},\\ \bar{\boldsymbol{c}}_N^{\mathrm{T}}\boldsymbol{x}_N-w&=\bar{w} \end{aligned}$

について以下が成り立つ。

$\bar{\boldsymbol{c}}_N\geq\boldsymbol{0}$ ならば、このときの実行可能基底解が最適解になる。さらに $\bar{\boldsymbol{c}}_N\gt\boldsymbol{0}$ ならばこのときの実行可能基底解は一意な最適解になる。
もしある添字 $q$ に対して $\bar{c}_q\lt0,$ $\bar{\boldsymbol{a}}_q\leq$ $\boldsymbol{0}$ ならば、目的関数が下に有界でないため、解は非有界である。
$\bar{c}_q\lt0$ かつ $\bar{a}_{iq}\gt0$ となるような $\bar{\boldsymbol{a}}_q$ の成分が存在するとき、
$\begin{aligned}\displaystyle{\min_{\bar{a}_{iq}\gt0}\frac{\bar{b}_i}{\bar{a}_{iq}}}=\displaystyle{\frac{\bar{b}_p}{\bar{a}_{pq}}}\end{aligned}$
により $p$ を定める。このとき基底変数として $x_p$ を $x_q$ で置き換えることで新しい実行可能な基底形式を得ることができる。特に非退化の仮定の下では、目的関数値は $\bar{w}$ よりも $\left|\bar{c}_q\displaystyle{\frac{\bar{b}_p}{\bar{a}_{pq}}}\right|$ だけ減少する。

定義2.6　単体法のアルゴリズム　初回の実行可能な基底形式が与えられているものとする。

相対費用係数が $\bar{\boldsymbol{c}}_N\geq\boldsymbol{0}$ を満たすならば終了する。そうでなければ
$\begin{aligned}\displaystyle{\min_{\bar{c}_i\lt0}}=\bar{c}_q\end{aligned}$
を満たすような添字 $q$ を求める。
$\bar{\boldsymbol{a}}_q\leq\boldsymbol{0}$ ならば、目的関数が下に有界でないため終了する。そうでなければ
$\begin{aligned}\displaystyle{\min_{\bar{a}_{iq}\gt0}\frac{\bar{b}_i}{\bar{a}_{iq}}}=\displaystyle{\frac{\bar{b}_p}{\bar{a}_{pq}}}\end{aligned}$
となる添字 $p$ を求める。
$\bar{a}_{pq}$ をピボットとする掃き出しを実行し、 $x_p$ の代わりに $x_q$ を基底変数とする新しい実行可能な基底形式を作る。
$1.$ へ戻る。

次回

power-of-awareness.com

参考文献

寒野善博[著]/駒木文保[編](2019)「最適化手法入門」(講談社)
東京大学工学教程編纂委員会[編]、寒野　善博[著]、土谷　隆[著](2014)「東京大学工学教程基礎系数学最適化と変分法」(丸善出版)
矢部博(2006)「工学基礎　最適化とその応用」(数理工学社)
Kochenderfer, Mykel J., Wheeler, Tim A. (2019), "Algorithms for Optimization", The MIT Press (https://algorithmsbook.com/optimization/files/optimization.pdf)

*1:双対性は別に章を立てて扱う予定である。

*2:なお双対性に関する詳細は後に改めて議論する。

*3:双対問題の双対問題が主問題であるから、上述した双対問題を主問題、主問題を双対問題としてもよい。

*4:退化する場合は、枢軸変換における変数の選び方を工夫する必要がある。

はじめに

前回

2. 線形計画と凸2次計画

2.2 双対性

2.2.1 双対問題

2.2.2 双対定理

2.3 線形計画問題の解法

2.3.1 単体法

次回

参考文献

2.　線形計画と凸2次計画

2.2　双対性

2.2.1　双対問題

2.2.2　双対定理

2.3　線形計画問題の解法

2.3.1　単体法