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

一流の大人（ビジネスマン、政治家、リーダー…）として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。データ分析・語学に力点を置いています。　→現在、コンサルタントの雛になるべく、少しずつ勉強中です(※2024年1月21日改訂)。

MENU

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

やりなおしの数学 最適化

はじめに

　応用数学の中でも非常に重要な分野である「最適化問題」を

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

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

Amazon

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

前回

power-of-awareness.com

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

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

2.1　線形計画問題

　目的関数が1次関数であり、制約が(1つの場合も複数の場合もあり得る)1次方程式ないし1次不等式のみから構成される最適化問題を線形計画問題という。線形計画問題は統一的に以下のように書くことができる。

\begin{aligned} \mathrm{Minimize}\ \ &\displaystyle{\sum_{j=1}^{n}c_jx_j}\\ \mathrm{subject\ to}\ \ &{}^{t}\boldsymbol{a}_i\boldsymbol{x}b_i,i=1,\cdots,m,\\ &x_j\geq0,j=1,\cdots,n \end{aligned}

このような形の問題を等式標準形という。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}

と書く*2。

例：工場での利益最大化生産問題
　ある工場では3種類の原材料M_1,M_2,M_3を用いて2種類の製品P_1,P_2を生産している。製品P_1,P_2の生産量をx_1,x_2[kg]とし、可能な限り最大の利益を得られるようにx_1,x_2\geq0を決めるものとする。
　製品P_1,P_2の利益をそれぞれ20,60[万円]だとすれば、総利益は20x_1+60x_2である。一方で製品P_1,P_2を生産するのに、原材料が以下の表のとおりに必要だとする。

　　　　　　　　　 　
P_1
P_2
　　　　　　　　　 M_1
5kg
4kg
　　　　　　　　　 M_2
2kg
4kg
　　　　　　　　　 M_3
2kg
8kg

　原材料の在庫をそれぞれ80,40,64[kg]とすれば、この最適化問題は


\begin{aligned} \mathrm{Maximize}\ \ &\ 20x_1+60x_2\\ \mathrm{subject\ to}\ \ &\ 5x_1+4x_2\leq80,\\ &\ 2x_1+4x_2\leq40,\\ &\ 2x_1+8x_2\leq64,\\ &\ x_1\geq0,\\ &\ x_2\geq0,\\ \end{aligned}


で定式化できる。これは目的関数も制約もすべて一次方程式ないし一次不等式であるから、線形計画問題である。

線形計画問題の制約はすべて1次式であるから、実行可能領域は凸多角形になる。目的関数も1次式であるから、等高線は一定の感覚で平行に並ぶ直線である。このため最適解は実行可能領域を表す多角形の頂点のいずれかである。一般にn個の変数を持つ線形計画問題では実行可能領域は多面体になり、その頂点のいずれかが最適解になる。

2.1.1　等式標準形

　線形計画問題は様々な形態で書き換えることができる。

　その準備として、まず線形計画問題をベクトル形式で書くことにする。
　次元数の等しいベクトル\boldsymbol{a}=(a_1,\cdots,a_n),\boldsymbol{b}=(b_1,\cdots,b_n)に対して、

\begin{aligned} {}^{\forall}i&\in\{1,\cdots,n\}\left(a_i\leq b_i\right)\\ {}^{\forall}i&\in\{1,\cdots,n\}\left(a_i\geq b_i\right) \end{aligned}

が成り立つとき、それぞれ\boldsymbol{a}\leq\boldsymbol{b}および\boldsymbol{a}\geq\boldsymbol{b}と書くことにする。

　以上を踏まえて線形計画問題を一般的な形式で書くと以下のようになる。すなわち\boldsymbol{c}=(c_1,\cdots,c_n),\boldsymbol{b}=(b_1,\cdots,b_n),\boldsymbol{h}=(h_1,\cdots,h_n)c_i,b_i,h_i\in\mathbb{R},i=1,\cdots,nに対して決定変数を\boldsymbol{x}=(x_1,\cdots,x_n)として、またA=(A_{ij}),G=(G_{ij}),A_{ij},G_{ij}\in\mathbb{R},i,j\in\{1,\cdots,n\}として

\begin{aligned} \mathrm{Minimize}\ \ &\boldsymbol{c}^{\mathrm{T}}\boldsymbol{x}\\ \mathrm{subject\ to}\ \ &A\boldsymbol{x}=\boldsymbol{b},\\ &G\boldsymbol{x}\leq\boldsymbol{h} \end{aligned}

と書くことができる。等式で書かれる制約を等式制約、不等式で書かれる制約を不等式制約という。
　応用上、上記の一般形式よりも等式標準形と呼ばれる形式を扱うことが多い。

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

一般形式において[te:xG=-I,]\boldsymbol{h}=\boldsymbol{0}としたものである。
　任意の一般形式は等式標準形に直すことができる。まず目的関数の定数項は最適化には影響しないから最適解の求解には無視しても良いことに注意する*3。次に変数\boldsymbol{s}\geq\boldsymbol{0}を新たに定義して不等式制約を等式制約

\begin{aligned} G\boldsymbol{x}+\boldsymbol{s}=\boldsymbol{h} \end{aligned}

に変換する。この\boldsymbol{s}のように不等式制約を等式制約に変換するために用いられる変数をスラック変数と呼ぶ。次に新たに変数\boldsymbol{x}^{+},\boldsymbol{x}^{-}\geq\boldsymbol{0}を導入し、

\begin{aligned} \boldsymbol{x}=\boldsymbol{x}^{+}-\boldsymbol{x}^{-} \end{aligned}

と書き直す。以上から、

\begin{aligned} \mathrm{Minimize}\ \ &\begin{bmatrix}\boldsymbol{c}\\-\boldsymbol{c}\\\boldsymbol{0}\end{bmatrix}^{\mathrm{T}}\begin{bmatrix}\boldsymbol{x}^{+}\\\boldsymbol{x}^{-}\\\boldsymbol{s}\end{bmatrix}\\ \mathrm{subject\ to}\ \ &\begin{bmatrix}A&-A&O\\G&-G&I\end{bmatrix}\begin{bmatrix}\boldsymbol{x}^{+}\\\boldsymbol{x}^{-}\\\boldsymbol{x}\end{bmatrix}=\begin{bmatrix}\boldsymbol{b}\\\boldsymbol{h}\end{bmatrix},\\ &\boldsymbol{x}^{+}\geq\boldsymbol{0},\\ &\boldsymbol{x}^{-}\geq\boldsymbol{0},\\ &\boldsymbol{s}\geq\boldsymbol{0} \end{aligned}

と書ける。

2.1.2　問題の書き換え

　線形計画は、一見単純な問題しか記述できないように見える。しかし非線形の目的関数や制約の中には、工夫することで線形計画問題に帰着できるものも多い。

例1
　絶対値を含む最適化問題

\begin{aligned} \mathrm{Minimize}\ \ &\boldsymbol{c}^{T}\boldsymbol{x}\\ \mathrm{subject\ to} \ \ &\left|\boldsymbol{a}_i^{\mathrm{T}}\boldsymbol{x}\right|\leq d_i,\ i=1,\cdots,m \end{aligned}

は、線形計画問題

\begin{aligned} \mathrm{Minimize}\ \ &\boldsymbol{c}^{T}\boldsymbol{x}\\ \mathrm{subject\ to} \ \ &\boldsymbol{a}_i^{\mathrm{T}}\boldsymbol{x}\leq d_i,\ i=1,\cdots,m\\ &\boldsymbol{a}_i^{\mathrm{T}}\boldsymbol{x}\geq -d_i,\ i=1,\cdots,m \end{aligned}

に帰着できる。

例2
　目的変数に絶対値の和を含む最適化問題

\begin{aligned} \mathrm{Minimize}\ \ &\displaystyle{\sum_{i=1}^{n}|c_ix_i|}\\ \mathrm{subject\ to} \ \ &A\boldsymbol{x}\geq\boldsymbol{b} \end{aligned}

は、補助変数t_i=|c_ix_i|,i=1,\cdots,nを導入すると、

\begin{aligned} \mathrm{Minimize}\ \ &\displaystyle{\sum_{i=1}^{n}t_i}\\ \mathrm{subject\ to} \ \ &t_j\geq|c_jx_j|,\ j=1,\cdots,n\\ &A\boldsymbol{x}\geq\boldsymbol{b} \end{aligned}

に帰着でき、これはさらに線形計画問題

\begin{aligned} \mathrm{Minimize}\ \ &\displaystyle{\sum_{i=1}^{n}t_i}\\ \mathrm{subject\ to} \ \ &t_j\geq c_jx_j,\ j=1,\cdots,n\\ &t_j\leq -c_jx_j,\ j=1,\cdots,n\\ &A\boldsymbol{x}\geq\boldsymbol{b} \end{aligned}

に帰着できる。

例3
　方程式

\begin{aligned} C\boldsymbol{x}=\boldsymbol{d} \end{aligned}

が不定であるときに、可能な限り成分に0を多く含む解\boldsymbol{x}(疎な解)を求めたいとする。
　このような\boldsymbol{x}はそのl_1ノルムを最小化すると得られることが知られている。すなわち

\begin{aligned} \mathrm{Minimize}\ \ &\|\boldsymbol{x}\|=\displaystyle{\sum_{i=1}^{n}|x_{i}|}\\ \mathrm{subject\ to}\ \ &C\boldsymbol{x}=\boldsymbol{d} \end{aligned}

を解けばよい。これは更に補助変数を導入することで線形計画問題に帰着できる。

2.1.3　線形計画問題の基本定理

　等式制約の係数行列から線形独立な列ベクトルを並べて定義した正則行列を基底行列と呼び、それに対応する変数を基底変数という。非基底変数を0とおけば、基底変数は基底行列をBとおけば、\boldsymbol{x}_B=B^{-1}\boldsymbol{b}と一意に決まる。こうして定まった解を基底解と呼ぶ。更にこの基底解のすべてが非負であるとき、実行可能基底解と呼ぶ。
　もし実行可能基底解で等式制約の行列のランクと等しい個数の変数が非負であるとき、非退化実行可能基底解という。

　以下の定理から、線形計画問題を解く際には、実行可能基底解が重要になることが分かる。


定理2.1　線形計画問題の基本定理　線形計画問題

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

が与えられたとき、以下が成り立つ。

(1) 実行可能解が存在するならば、実行可能基底解が存在する。
(2) 最適解が存在するならば、実行可能基底解の中に最適解が存在する。

(\because　まず(1)について、実行可能解の1つを\bar{\boldsymbol{x}}=(\bar{x}_{1},\cdots,\bar{x}_{n})^{\mathrm{T}}とし、等式制約の行列Aにおいて対応する列ベクトルをそれぞれ\bar{\boldsymbol{a}}_{1},\cdots,\bar{\boldsymbol{a}}_{n}とおくと、実行可能解であることから、

\begin{aligned} \displaystyle{\sum_{i=1}^{n}\bar{x}_i\bar{\boldsymbol{a}}_i}=\boldsymbol{b},\bar{x}_i\geq0,i=1,\cdots,n \end{aligned}

が成立する。\bar{\boldsymbol{x}}の成分のうち正のものは1つもないか少なくとも1つ存在する。その数をkとおく。
　まずk\gt0の場合、\bar{\boldsymbol{x}}の最初のk個の成分が正であるとしても一般性を失わない。このとき

\begin{aligned} \displaystyle{\sum_{i=1}^{k}\bar{x}_i\bar{\boldsymbol{a}}_i}&=\boldsymbol{b},\\ \bar{x}_i&\geq0,i=1,\cdots,n,\\ \bar{x}_i&\gt0,i=1,\cdots,k,\bar{x}_j=0,j=k+1,\cdots,n \end{aligned}

であり、これは\bar{\boldsymbol{a}}_{1},\cdots,\bar{\boldsymbol{a}}_{k}が線形独立か否かで場合分けできる。
　まず\bar{\boldsymbol{a}}_{1},\cdots,\bar{\boldsymbol{a}}_{k}が線形独立ならば、\mathrm{rank}\ A=mであるから、k\leq mである。
　k=mならば、\bar{\boldsymbol{x}}は\bar{x}_1,\cdots,\bar{x}_mを基底変数とする非退化実行可能基底解となる。
　k\lt mならば、行列Aの残ったn-k列から適当にm-k個選んでそれらと\bar{\boldsymbol{a}}_{1},\cdots,\bar{\boldsymbol{a}}_{k}が線形独立になるようにできる。このとき\bar{x}_{1},\cdots,\bar{x}_{m}を基底変数とする退化した実行可能基底解になる。またk=0の場合もこれに帰着できる。
　
　他方でもし\bar{\boldsymbol{a}}_{1},\cdots,\bar{\boldsymbol{a}}_{k}が線形従属であるならば、

\begin{aligned} \alpha_{1}\bar{\boldsymbol{a}}_{1}+\cdots+\alpha_{k}\bar{\boldsymbol{a}}_{k}=\boldsymbol{0} \end{aligned}

であるような、少なくとも1つが非零であるようなスカラー\alpha_1,\cdots,\alpha_kが存在する。ここで一般性を失うことなく、少なくとも1つは\alpha_i\gt0であるとすれば、任意の正数\varepsilonに対して

\begin{aligned} \displaystyle{\sum_{i=1}^{n}(\bar{x}_i-\varepsilon\alpha_i)\bar{\boldsymbol{a}}_i}=\boldsymbol{b} \end{aligned}

が成り立つ。ここで\varepsilonを0から正に増大させると、\bar{x}_i-\varepsilon\alpha_iは0に近づいていく。これを繰り返していくことで、最終的に線形独立な列ベクトルを持つ実行可能解が得られ、線形独立の場合に帰着できる。


　(2)の場合について、\bar{\boldsymbol{x}}^{*}=(\bar{x}_{1}^{*},\cdots,\bar{x}_{n}^{*})^{\mathrm{T}}とし、対応するAの列ベクトルを\bar{\boldsymbol{a}}_{1},\cdots,\bar{\boldsymbol{a}}_{n}とする。もし\bar{\boldsymbol{x}}^{*}=\boldsymbol{0}ならば、(1)の場合と同様に退化した実行可能基底解が構築でき、しかも目的関数値は\boldsymbol{c}^{\mathrm{T}}\bar{\boldsymbol{x}}^{*}=0と等しくなるから、この実行可能基底解は最適解となる。
　次に\bar{\boldsymbol{x}}^{*}\neq\boldsymbol{0}の場合を考える。\bar{\boldsymbol{x}}^{*}の最初のk\gt0個の成分が正であるとしても一般性を失わない。対応する列ベクトルを\bar{\boldsymbol{a}}_{1},\cdots,\bar{\boldsymbol{a}}_{k}とすれば、

\begin{aligned} \bar{x}_{1}^{*}\bar{\boldsymbol{a}}_{1}+\cdots+\bar{x}_{k}^{*}\bar{\boldsymbol{a}}_{k}=\boldsymbol{b} \end{aligned}

となる。
　このとき、\bar{\boldsymbol{a}}_{1},\cdots,\bar{\boldsymbol{a}}_{k}が線形独立ならば、(1)の場合と同様にすれば最適解\boldsymbol{x}=\bar{\boldsymbol{x}}^{*}が実行可能基底解になる。
　\bar{\boldsymbol{a}}_{1},\cdots,\bar{\boldsymbol{a}}_{k}が線形従属ならば、

\begin{aligned} \alpha_1\bar{\boldsymbol{a}}_{1}+\cdots+\alpha_k\bar{\boldsymbol{a}}_{k}=\boldsymbol{0} \end{aligned}

を満たし少なくとも1つが正であるような\alpha_1,\cdots,\alpha_kが存在する。|\delta|が充分に小さい任意の\deltaに対して

\begin{aligned} \hat{\boldsymbol{x}}=\left(\bar{x}_{1}^{*}+\delta\alpha_{1},\cdots,\bar{x}_{k}^{*}+\delta\alpha_{k},0,\cdots,0\right) \end{aligned}

は実行可能解になるため、

\begin{aligned} \boldsymbol{c}^{\mathrm{T}}\boldsymbol{x}\leq\boldsymbol{c}^{\mathrm{T}}\hat{\boldsymbol{x}}=\boldsymbol{c}^{\mathrm{T}}\bar{\boldsymbol{x}}^{*}+\delta\displaystyle{\sum_{i=1}^{k}c_i\alpha_i} \end{aligned}

が成り立ち、0\leq\delta\displaystyle{\sum_{i=1}^{k}c_i\alpha_i}となる。これは\deltaの符号にかかわらず成り立つから、\displaystyle{\sum_{i=1}^{k}c_i\alpha_i}=0が成立する。したがって任意の\varepsilon\gt0に対して


\begin{aligned} \displaystyle{\sum_{i=1}^{k}c_i(\bar{x}_i^{*}+\varepsilon\alpha_i)}=\boldsymbol{c}^{\mathrm{T}}\bar{\boldsymbol{x}}^{*}+\varepsilon\displaystyle{\sum_{i=1}^{k}c_i\alpha_i}=\boldsymbol{c}^{\mathrm{T}}\bar{\boldsymbol{x}}^{*} \end{aligned}

が得られる。したがって(1)と同様に不要な変数を例にしていくと、適当な\bar{\varepsilon}\gt0,k^{\prime}\gt0に対して

\begin{aligned} \bar{\boldsymbol{x}}^{\prime}=\left(\bar{x}_{1}^{*}-\bar{\varepsilon}\alpha_{1},\cdots,\bar{x}_{k^{\prime}}^{*}-\bar{\varepsilon}\alpha_{k^{\prime}},0,\cdots,0\right)^{\mathrm{T}} \end{aligned}

は実行可能基底解かつ最適解である。以上より、実行可能基底解の中に最適解が存在することが示された。　\blacksquare)

この基本定理により、線形計画問題を解くためには実行可能基底解を調べればよい。

次回

https://power-of-awareness.com/entry/2023/02/17/050000power-of-awareness.com

参考文献

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

*2:\boldsymbol{x}\geq\boldsymbol{0}はすべての成分についてx_j\geq0が成り立つことをいう。

*3:もちろん最適解における目的関数の値は変化するために注意する。

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