「大人の教養・知識・気付き」を伸ばすブログ

一流の大人（ビジネスマン、政治家、リーダー…）として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。目下、データ分析・語学に力点を置いています。

MENU

最適化問題を解く（その03/X）

やりなおしの数学 最適化

はじめに

　統計学にしても経済学にしても、応用数学の中でも非常に重要な分野である「最適化問題」を

最適化手法入門 データサイエンス入門シリーズ

最適化手法入門 データサイエンス入門シリーズ

Amazon

などを参考に学んでいきます。

前回

power-of-awareness.com

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

　まずはシンプルで分かりやすいこともあり、線形計画（および凸2次計画）を扱う。また線形問題の中でという前提で双対性など他の最適化問題にも当てはまる理論を少し扱う*1。

2.2　双対性

　線形計画の理論の核である双対性を議論する*2。

2.2.1　双対問題

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

\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}

および双対問題

\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}

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


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


定理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} \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}

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

\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　単体法のアルゴリズム　初回の実行可能な基底形式が与えられているものとする。

  1. 相対費用係数が\bar{\boldsymbol{c}}_N\geq\boldsymbol{0}を満たすならば終了する。そうでなければ

    \begin{aligned}\displaystyle{\min_{\bar{c}_i\lt0}}=\bar{c}_q\end{aligned}

    を満たすような添字qを求める。
  2. \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を求める。
  3. \bar{a}_{pq}をピボットとする掃き出しを実行し、x_pの代わりにx_qを基底変数とする新しい実行可能な基底形式を作る。
  4. 1.へ戻る。

次回

power-of-awareness.com

参考文献

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

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

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

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

プライバシーポリシー お問い合わせ