双対問題

双対問題とは

ある1つの最適化問題に対して、双対問題を考えられます。

  • 元の問題を主問題といいます。
  • 主問題が最小化問題のとき、双対問題は最大化問題になります。
  • 主問題が最大化問題のとき、双対問題は最小化問題になります。
  • 主問題の変数は双対問題の制約条件に、主問題の制約条件は双対問題の変数に対応します。

双対問題の重要な性質

  • 主問題または双対問題のどちらかが最適解を持つならば、もう片方の問題も最適解を持ち、両方の最適解の値は一致します(双対定理)。

補足

  • 双対問題は、線形最適化問題以外でも考えられますが、ここでは線形最適化問題に対する双対問題を考えます。

PuLPよる表現

上図左側の主問題は、PuLPで下記のように書けます。

primal_model = LpProblem(sense=LpMaximize)
primal_model += lpSum(c.T * x)
for row, rhs in  zip(A, b):
    primal_model += lpSum(row * x) <= rhs

また、図右側の双対問題は、下記のように書けます。

dual_model = LpProblem()
dual_model += lpSum(b.T * y)
for row, rhs in  zip(A.T, c):
    dual_model += lpSum(row * y) >= rhs

図のA x bのような表現を行列表現といいます。 Aが行列で、b, c, x, yは列ベクトルです。A^TAの転置を表し、PythonではA.Tと表現しています。

行列表現をコードにするときは、行列の行ごとにforでループする必要があります。

双対問題は、何の役に立つの?

双対というのは、数学や物理で重要な概念です。

  • 双対問題の解から、主問題の解を構築できます。
    • ソルバーによっては、主問題より双対問題の方が解きやすいことがあります。
  • アルゴリズムによっては、主問題と双対問題を同時に解く方法があります(主双対内点法)。
  • 効用の最大化(主問題)と費用の最小化(双対問題)の最適解が同じであることから、知見を得られます。

参考:双対

双対問題は、どうやって求めるの?

ラグランジュ緩和問題を使って求められます。

手順の一部のイメージは、下記のようになります。

b^T y = y^T b ≧ y^T A x = (A^T y)^T x ≧ c^T x

より詳しい説明については、下記書籍などにあります。

dualライブラリー

どんな主問題に対しても、双対問題を考えられます。

ある主問題が、どのような双対問題になるのか覚えるのは大変です。

dualライブラリーを使うと、簡単な形式で、双対問題をJupyter上で確認できます。

dualのインストール

コマンドプロンプトで、pip install -U dualでできます(macOSではpip3 install -U dual)。

dualの書き方

  • import dualが必要です
  • セルの最初に%%dualを書いてください
  • モデルの1行目は下記のどちらかを書いてください
    • min 目的関数の式
    • max 目的関数の式
  • 2行目以降は、下記のように制約条件を書きます
    • >= 定数
    • = 定数
    • <= 定数
  • 制約条件では、行列形式も使えます。
  • 式の中で、c^T xのように、左に係数を、右に変数を書きます
  • c^Tは、ベクトルまたは行列cの転置を表します。

サンプル

PuLPとの比較を載せます。

import numpy as np
from pulp import LpProblem, LpVariable, lpSum
A = np.array([[1, 0], [0, 1]])
b = np.array([1, 1])
c = np.array([1, 1])

# 主問題
primal_model = LpProblem(sense=LpMaximize)
x = [LpVariable(f'x{i}', lowBound=0) for i in range(2)]
primal_model += lpSum(c.T * x)
for row, rhs in  zip(A, b):
    primal_model += lpSum(row * x) <= rhs

上記は、下記のように記述します。

%%dual
max c^T x
A x <= b
x >= 0

実行すると、双対問題は、下記のように出力されます。

min b^T y
A^T y >= c
y >= 0

下記と対応します。

# 双対問題
dual_model = LpProblem()
y = [LpVariable(f'y{i}', lowBound=0) for i in range(2)]
dual_model += lpSum(b.T * y)
for row, rhs in  zip(A.T, c):
    dual_model += lpSum(row * y) >= rhs