『しっかり学ぶ数理最適化』と線形計画問題の話。

『しっかり学ぶ数理最適化』の勉強会の話で、線形計画問題の標準形について言及した。

しっかり学ぶ数理最適化　モデルからアルゴリズムまで (ＫＳ情報科学専門書)

作者:梅谷俊治
講談社

Amazon

今日はそれについて詳しく書いてみたい。

これは数理最適化 Advent Calendar 2025の4日目の記事です。

不等式標準形

線形計画問題でまず紹介されるのは不等式標準形：

$\begin{array}{ll} \mathrm{max.} & \boldsymbol{c}^\top \boldsymbol{x} \\ \mathrm{sub.\ to} & A\boldsymbol{x} \le \boldsymbol{b} \\ &\boldsymbol{x} \ge \boldsymbol{0} \\ \end{array}$

この形の嬉しいところは $\boldsymbol{x} \in \mathbb{R}^2$ なら実行可能領域をグラフに可視化できるので直観的に分かりやすいというところ。

実際、『しっかり学ぶ数理最適化』でも例題をグラフで可視化している：

これはとても分かりやすいし、（今もそうかは分からないけど）このように可視化して最適化問題を解くのは高校数学でも出てきたりする。

ただ、これを単体法で解くためにはスラック変数を導入して等式標準形に直すことになる。すると、各辺が $x_i = 0$ に対応することになり、2つの変数を0にする（＝非基底変数にする）と各頂点に対応することになるんだけど、これが慣れてないとちょっと分かりにくいっぽい。

実際、図としては2次元なんだけど、各点の座標を表示した図を見ると（目的値の $z$ を含めて）6次元となっていて、これはどういうことなんだ？と混乱する人も。

そして、実際にはここからは行列演算で解いていくので元の変数とスラック変数とで差はないんだけど、あとから導入された変数ということで差を感じてしまう可能性も。

等式標準形

そうやってあとから等式標準形にして混乱が生じるくらいなら、最初から等式標準形で考えた方がいいのでは？というのが自分の考え。

線形計画問題の等式標準形は次のようになっている：

$\begin{array}{ll} \mathrm{min.} & \boldsymbol{c}^\top \boldsymbol{x} \\ \mathrm{sub.\ to} & A\boldsymbol{x} = \boldsymbol{b} \\ &\boldsymbol{x} \ge \boldsymbol{0} \\ \end{array}$

余談だけど、実はこれは線形計画問題を一般化した錐線形計画問題（CLP: Cone Linear Programming）の形に従うものとなっている。

錐線形計画問題では内積を $\langle\boldsymbol{x}, \boldsymbol{y}\rangle$ とし、閉凸錐 $\mathcal{K}$ に対して次のような問題を考える：

$\begin{array}{ll} \mathrm{min.} & \langle\boldsymbol{c}, \boldsymbol{x}\rangle \\ \mathrm{sub.\ to} & \langle \boldsymbol{a}_i, \boldsymbol{x} \rangle = b_i \quad(i = 1, \ldots, m) \\ &\boldsymbol{x} \in \mathcal{K} \\ \end{array}$

これで内積 $\langle \boldsymbol{x}, \boldsymbol{y} \rangle = \boldsymbol{x}^\top \boldsymbol{y}$ とし、閉凸錐 $\mathcal{K} = \{\boldsymbol{x}| \boldsymbol{x} \ge \boldsymbol{0}\}$ としたものが線形計画問題。

また、対称行列の集合に対して内積を $X \bullet Y$ とし、閉凸錐を半正定値行列の集合としたものは半正定値計画問題（SDP: Semi-Definite Programming）になるし、内積をベクトルの内積、閉凸錐を2次錐にすると、2次錐計画問題（SOCP: Second-Order Cone Programming）となる。

ここで、1つ目の制約は $\boldsymbol{x}$ がアフィン空間に入っていることを示し、2つ目の制約はその空間が閉凸錐で切り取られた部分が実行可能領域になることを示している。なので、実は1つ目の制約はそれほど重要ではなく、2つ目の制約の違いこそが各問題の違いを生んでいるとも言えたり。（勉強したのがだいぶ前なのでけっこう曖昧だけど（＾＾；）

閑話休題で、線形計画問題の話に戻ってくると、つまり実行可能領域の境界を生んでるのは $\boldsymbol{x} \ge \boldsymbol{0}$ という制約であり、 $x_i = 0$ と固定するものが増えるたびにアフィン空間の次元が落ちて、最終的には面→辺→頂点へとなっていくことになる（点になったのが各基底解）。

先程の例題だと、5次元空間の中に2次元のアフィン平面があり、これが $\boldsymbol{x} \ge \boldsymbol{0}$ という制約で区切られた凸多面体になっていて、 $\boldsymbol{x}$ の1つの成分を0にすると辺になり、2つの成分を0にすると頂点になる。そしてこの凸多面体を $x_1\mathrm{-} x_2$ 平面に射影してきたものが本に載っている図となる。

・・・とまぁ書いたけど、これを説明してると難しい。これは図で表現しにくいものを図で表現しようとしてるからで、分かりやすくするために図を導入してるはずなのに、かえって難しくなってしまっている。これでは本末転倒なので、まずは形式的に処理できる行列演算の形で説明して、あとから幾何的な解釈を説明する方がよさそうとなる。そして、図での説明をしないなら不等式標準形をわざわざ出す嬉しさもないので、初めから等式標準形で考えていけばいいよねと。

等式標準形で説明した場合、理論的にもちょっと嬉しいところがあって、この双対問題は次のように書ける：

$\begin{array}{ll} \mathrm{max.} & \boldsymbol{b}^\top \boldsymbol{y} \\ \mathrm{sub.\ to} & A^\top\boldsymbol{y} + \boldsymbol{z} = \boldsymbol{c} \\ &\boldsymbol{z} \ge \boldsymbol{0} \\ \end{array}$

このとき、相補性条件は $\boldsymbol{x}^\top\boldsymbol{z} = 0$ と書けて、とてもシンプルな形になる。よく出てくる相補性条件の式はゴチャゴチャしすぎなんよね。

ちなみに錐線形計画問題だと双対問題は以下：

$\begin{array}{ll} \mathrm{max.} & \langle\boldsymbol{b}, \boldsymbol{y}\rangle \\ \mathrm{sub.\ to} & \sum_i y_i \boldsymbol{a}_i + \boldsymbol{z} = \boldsymbol{c} \\ &\boldsymbol{z} \in \mathcal{K}^\ast \\ \end{array}$