線形計画の双対問題のラグランジュ緩和からの導出

こんにちは、株式会社Jijの宮脇です。

この記事はJij Inc. Advent Calendar 2023の23日目の記事です。

Jij(ジェイアイジェイ)は数理最適化、量子技術を用いたソフトウェアの開発を行っています。

はじめに

線形計画問題は、資源配分、コスト最小化、収益最大化などビジネスの分野でも広く応用されています。これらの問題を解く際には、効率的なアプローチとして双対問題とラグランジュ緩和の概念があります。双対問題は、元の問題（主問題）と深く関連し、より簡単に解ける問題を与えてくれることがあります。一方、ラグランジュ緩和は、特に複雑な制約を持つ問題を単純化し、解を見つけるための手法として有効です。この記事では、そのような線形計画における、双対問題やラグランジュ緩和について理解し、それらの有機的なつながりを具体例を用いて簡易に理解することを目的としています。

双対問題

双対問題とは何か

定義

一般系の線形計画問題は以下のような数式で記述できます。

$$\max z = \mathbf{c}^T \mathbf{x} \\ \text{s.t. } \mathbf{A} \mathbf{x} \leq \mathbf{b} \\ \mathbf{x} \geq 0 \tag{1}$$

これに対して、以下のような問題を双対問題といいます。具体的な定義は幾つか王道の著書もあるのでこちらなど^[1]を参照してください。

$$\min w = \mathbf{b}^T \mathbf{y} \\ \text{s.t. } \mathbf{A}^T \mathbf{y} \geq \mathbf{c} \\ \mathbf{y} \geq 0 \tag{2}$$

双対問題の特徴

１つ目の特徴は、変数と制約の関係が逆転していることです。具体的には、主問題の各制約は双対問題の変数に対応し、主問題の変数は双対問題の制約に対応しています。
２つ目の特徴は、目的関数の変換です。具体的には主問題が最大化問題なら、双対問題は最小化問題になります。
他にも、弱双対性という特徴があります。弱双対性は、主問題の任意の実行可能解に対する目的関数の値が、双対問題の任意の実行可能解に対する目的関数の値に対して常に下界（最小化問題の場合は上界）を与えるという特徴です。「下界」とは、ある集合のすべての要素が満たすべき最小の値のことです。最適化問題において、弱双対性が示す下界は、主問題の任意の実行可能解の目的関数の値が、双対問題の任意の実行可能解の目的関数の値を下回らないことを意味しています。つまり、双対問題の実行可能解によって提供される値は、主問題の解の最小限の保証された値となります。

なぜ双対問題を考えることが重要なのか

双対問題を考えるメリットはたくさんありますが、分かりやすいところで言えば、計算の効率化があります。例えば、特に変数が多く制約が少ない場合、双対問題を解く方が効率的になる蓋然性が高いです。
他にも、弱双対性は主問題の解が双対問題の解の「範囲内」にあることを意味し、双対問題の解が主問題の解にどれだけ近いかを評価する際に重要な指標となります。弱双対性は、最適化問題の解析において、解の品質を確認するための基本的な手法として使用されます。

双対問題の具体例

上記の特徴をより分かりやすく理解するために、以下のような具体的な目的関数や制約条件を考えてみましょう。

$$\max z = 2x_1 + 3x_2 + x_3 \\ \text{s.t. } x_1 + x_2 + x_3 \leq 100 \\ 2x_1 + x_2 \leq 80 \\ x_1, x_2, x_3 \geq 0 \tag{3}$$

この主問題に対する双対問題は以下のように書けます。

$$\min w = 100y_1 + 80y_2 \\ \text{s.t.} \quad y_1 + 2y_2 \geq 2 \\ y_1 + y_2 \geq 3 \\ y_1 \geq 1 \\ y_1, y_2 \geq 0 \tag{4}$$

このケースでは、主問題には3つの変数と3つの制約条件があり、双対問題は4つの制約条件に基づいて2つの変数を持ちます。このような場合、双対問題は１つ少ない数の変数を持ち、結果として計算が簡単になる可能性があります。

ラグランジュ緩和

計算効率を向上させるために、問題を緩和するという方法もあります。たとえば、ある目的関数を最大化しようとするとき、制約条件を緩和すれば、実行可能集合が大きくなり、目的関数がより大きい実行可能解を得られ、その値からもとの問題の最適値を探せるかもしれません。ラグランジュ緩和では、難解な制約を緩和することで、元の問題よりも扱いやすく、解が見つけやすい問題に変換できます。

また、実は最初に紹介した双対問題をラグランジュ緩和によって導くことも出来ます。

ラグランジュ緩和とは

ラグランジュ緩和とは、制約式の一部を緩和し、その代わりに制約に違反する分をペナルティ項として目的関数に加えたることで、問題を緩和することです。たとえば、式(1)のラグランジュ緩和問題は以下のように書けます。λはラグランジュ乗数といいます。

$$\max L(x, \lambda) = \mathbf{c}^T \mathbf{x} - \mathbf{\lambda}^T (\mathbf{A} \mathbf{x} - \mathbf{b}) \\ \mathbf{x} \geq 0, \mathbf{\lambda} \geq 0 \tag{5}$$

ここでも具体的な例で考えてみましょう。式(3)のラグランジュ緩和問題を考えると以下のようになります。

$$\begin{aligned} & \max L(x_1, x_2, x_3, \lambda_1, \lambda_2) = 2x_1 + 3x_2 + x_3 \\ & \quad - \lambda_1(x_1 + x_2 + x_3 - 100) \\ & \quad - \lambda_2(2x_1 + x_2 - 80) \end{aligned} \\ \quad x_1, x_2, x_3 \geq 0 \tag{6}$$

これは変数を整理すれば以下のようにも書き換えられます。

$$\begin{aligned} & \max L(x_1, x_2, x_3, \lambda_1, \lambda_2) = (2 - \lambda_1 - 2\lambda_2)x_1 \\ & \quad + (3 - \lambda_1 - \lambda_2)x_2 \\ & \quad + (1 - \lambda_1)x_3 \\ & \quad + 100\lambda_1 + 80\lambda_2 \end{aligned} \\ x_1, x_2, x_3 \geq 0 \tag{7}$$

双対問題との関係性

ここで、式(7)の目的関数における$(2 - \lambda_1 - 2\lambda_2)$が正の実数ならば、このラグランジュ緩和問題の最適値は無限大となり、元の問題の最適値の上界の見積りとしては意味がありません。同様に$(3 - \lambda_1 - \lambda_2)$や$(1 - \lambda_1)$の少なくともどちらか一方が正の実数ならば、元の問題の最適値の上界の見積としては意味がありません。
従って、それらは全て0以下でなければなりません。また、その際のラグランジュ緩和問題の最適解は$x1,x2,x3=0$であり、この時のラグランジュ緩和問題の最適値は$100\lambda_1 + 80\lambda_2$です。
ここまでの議論をまとめると$(2 - \lambda_1 - 2\lambda_2)\leq 0$かつ、$(3 - \lambda_1 - \lambda_2)\leq 0$かつ、$(1 - \lambda_1)\leq 0$を満たす定数$\lambda_1,\lambda_2$のうち、$100\lambda_1 + 80\lambda_2$を最小にするものがよいラグランジュ乗数であると言えます。

このラグランジュ乗数を求める問題を最適化問題として記述すると以下のようにかけます。

$$\begin{aligned} & \min w = 100\lambda_1 + 80\lambda_2 \\ & \text{s.t.} \lambda_1 + 2\lambda_2 \geq 2 \\ & \quad \lambda_1 + \lambda_2 \geq 3 \\ & \quad \lambda_1 \geq 1 \\ & \quad \lambda_1, \lambda_2 \geq 0 \tag{8} \end{aligned}$$

これは式(4)の$y$が$\lambda$に変わっただけで本質的には同じです。
このようにラグランジュ乗数は双対変数としての解釈が可能であり、元の問題の制約を理解するのに役立ちます。具体的には、各ラグランジュ乗数は、対応する制約が目的関数にどの程度影響を与えるかを示します。これにより、制約の強度や重要性を定量的に評価することが可能になります。具体例を使った場合ではなく、もう少し正確な導出についてはこちら^[2]の資料等を参考にしてください。

まとめ

この記事では、線形計画問題の双対問題とラグランジュ緩和の概念、およびそれらがどのように役に立つかを解説しました。双対問題は、主問題の変数と制約の関係を逆転させ、目的関数を変換することで、より簡単に解ける問題を提供することがあります。また、ラグランジュ緩和は複雑な制約を持つ問題を単純化し、元の問題よりも解きやすい形に変換します。また、具体例を用いてこれらの有機的なつながりを示しました。弊社の西村が双対変数の直観的な理解に関する記事も書いているので、更に勉強してみたい方はそちらもご覧ください。

最後に

＼Rustエンジニア・数理最適化エンジニア募集中！／
株式会社Jijでは、数学や物理学のバックグラウンドを活かし、量子計算と数理最適化のフロンティアで活躍するRustエンジニア、数理最適化エンジニアを募集しています！
詳細は下記のリンクからご覧ください。皆さんのご応募をお待ちしております！
Rustエンジニア: https://open.talentio.com/r/1/c/j-ij.com/pages/51062
数理最適化エンジニア: https://open.talentio.com/r/1/c/j-ij.com/pages/75132

脚注

1. 梅谷俊治,「しっかり学ぶ数理最適化」, 講談社 (2020)

2. 椎名孝之,早稲田大学理工学部　オペレーションズリサーチ　ー線形計画法ー　講義資料