第4章双対問題

46
第 4 章双対問題
4.1 ラグランジュ型双対問題
主問題：
min
s.t.
f(x)
gi (x) ≤ 0 i = 1, . . . , m
hi (x) = 0 i = 1, . . . , l
x∈X
(4.1)
f，gi ，hi から，ψ を次のように定義する．
ψ(u, v) = inf {f(x) +
x∈X
m
∑
ui gi (x) +
i=1
l
∑
vi hi (x)}
(4.2)
i=1
双対問題：
sup{ψ(u, v) | u ≥ 0}
(4.3)
u,v
以下の例で，主問題と双対問題の関係を図を用いて説明する．
例 4.1
次の問題を考えよう．
min
s.t.
−x1
x21 + x22 ≤ 4
(4.4)
問題 (4.4) の双対問題を定義すると次のようになる．
sup{ψ(u) | u ≥ 0}
(4.5)
ψ(u) = inf {−x1 + u(x21 + x22 − 4)}
(4.6)
ただし，
x1 ,x2
である．
主問題 (4.4) は簡単に解くことができて，最適解は (2, 0)，最適値は −2 である．p，q を
q = f(x) = −x1
p = g(x) = x21 + x22 − 4
とおく．さらに t ≥ 0 と 0 ≤ θ ≤ 2π によって，x1 = t cos θ，x2 = t sin θ とおくと
q = −t cos θ
p = t2 − 4
第 4 章双対問題
47
となる．主問題が実行可能な領域は，p ≤ 0 (t ≤ 2) の範囲の範囲であることに注意してほしい．p
と q の式から t を消去すると，θ ̸= 12 π, 32 π において，
p=
1
q2 − 4
(cos θ)2
となる．また，θ = 21 π, 32 π では，q = 0，p ≥ −4 の半直線を表す．結局，(x1 ，x2 ) が R2 全体を動
いたとき，(p, q) のとりうる範囲は放物線 p = q2 − 4 で囲まれる領域である．この領域を G と呼
ぼう．
ψ(u) について考えると， u があたえられたとき，G 上で q + up を最小にする値が ψ(u) であ
る．α = p + uq とおくと，ψ(u) は，G に下から接する傾き −u の直線の q-切片である．したがっ
て，双対問題は，u ≥ 0 において，q-切片の値を最大にする問題とみることができる．G の形状か
ら，主問題の最適解は (p, q) = (−2, 0) をとおる傾き −u が −1/4 の場合で，最適値は −2 である．
上で，g(x) ≤ 0 を満たす制約領域は p ≤ 0 であると指摘した．制約条件を少し緩和した場合，
すなわち
min
s.t.
−x1
x21 + x22 ≤ 4 + ϵ
(4.7)
とした場合を考えよう．ϵ が −4 から増加していったとき，最適値の軌跡は G の下側の包絡線に相
当する．これを ϵ の関数とみなして，ϕ(ϵ) とおこう．ϕ が微分可能ならば，ϕ ′ (0) は，条件を緩
和したときの最適値の限界的な変化量とみることができる．これは，双対問題の最適解 u∗ にほか
ならない．
例 4.2
線型計画問題で考えよう．
min
s.t.
c1 x1 + · · · + cn xn
a11 x1 + · · · + a1n xn = b1
a21 x1 + · · · + a2n xn = b2
..
.
(4.8)
am1 x1 + · · · + amn xn = bm
−xj ≤ 0, j = 1, . . . , n
ψ(u, v) は次のようになる．
ψ(u, v) = inf
x

n
∑

cj xj +
j=1
m
∑

vi 
i=1
n
∑

aij xj − bi  +
j=1
n
∑


uj (−xj )
j=1

(4.9)
和の順序を入れ換えて，

) 
(
m
n
m

 ∑
∑
∑
aij vi xj
cj − uj +
bi vi +
ψ(u, v) = inf −
x 

i=1
を得る．もし，cj −uj +
について，
∑m
i=1
j=1
(4.10)
i=1
aij vi ̸= 0 ならば，ψ(u, v) は −∞ になってしまう．すべての j = 1, . . . , n
cj − uj +
n
∑
i=1
aij vi = 0
第 4 章双対問題
ならば，ψ(u, v) = −
48
∑m
i=1
bi vi である．−vi = yi とおいて，双対問題は，
max
s.t.
b1 y1 + · · · + bm ym
a11 y1 + · · · + am1 ym ≥ b1
a12 y1 + · · · + am2 ym ≥ b2
..
.
(4.11)
a1m y1 + · · · + amn ym ≥ bm
となる．
4.2 双対定理
定理 4.1 (弱双対定理)
x を主問題 (4.1) の実行可能解，u, v を双対問題 (4.3) の実行可能解とする．このとき，
f(x) ≥ ψ(u, v)
(4.12)
が成り立つ．
[証明]
ψ(u, v) の定義，および x, u, v の実行可能性より，
ψ(u, v) = inf {f(x) +
x∈X
m
∑
i=1
ui gi (x) +
l
∑
vi hi (x)} ≤ f(x) +
i=1
m
∑
ui gi (x) +
i=1
l
∑
vi hi (x) ≤ f(x)
i=1
が成り立つ．
系 4.2
¯ が主問題 (4.1) の実行可能解，u
¯ , ¯v が双対問題 (4.3) の実行可能解であり，f(¯
x
x) = ψ(¯
u, ¯v) が成り
¯, u
¯ , ¯v は最適解である．
立っているならば，x
系 4.3
もし supu,v {ψ(u, v) | u ≥ 0} = ∞ ならば，主問題は実行不可能である．
定義 4.1 (双対ギャップ)
主問題の最適解を x∗ ，双対問題の最適解を u∗ , v∗ とし，
ζ = f(x∗ ) − ψ(u∗ , v∗ )
とおく．ζ > 0 のとき，これを双対ギャップという．
弱双対定理より，常に ζ ≥ 0 である．例 4.1 では，主問題と双対問題の最適値は一致し，双対
ギャップは存在しなかった．しかし，双対ギャップが生じる場合もある．
例 4.3
次の問題を考えよう．
min
s.t.
−x1
(4.13)
x21 + x22 ≤ 4
(x1 , x2 ) ∈ X
√
√
√
√
ここで，X は，A ( 6/2, 6/2)，B (1, − 3)，C (1/2, 2/2)，D (2, 1) の 4 点からなる集合とす
る．明らかに，最適解は点 A で達成される．
第 4 章双対問題
49
問題 (4.13) の双対問題を定義すると次のようになる．
sup{ψ(u) | u ≥ 0}
(4.14)
ただし，
ψ(u) =
{−x1 + u(x21 + x22 − 4)}
inf
(4.15)
(x1 ,x2 )∈X
である．X が 4 点からのみなる集合なので，4.15 は，次のように書き換えることができる．
{
}
√
6
13
1
ψ(u) = min −u −
, −1, − u − , u − 2
(4.16)
2
4
2
ψ(u) は，図にある 4 本の直線のうち，もっとも小さい値を達成してる直線をつなげた関数として
表される．したがって，双対問題
4.14 の最適解は u∗ = 3/8 であり，最適値は −13/8 である．双
√
対ギャップ ζ = − 6/2 − (−13/8) ≈ 0.40 > 0 である．
図表 4.1 例 4.3 の ψ(u)
定理 4.4 (強双対定理)
X を非空な凸集合，f(x)，gi (x) i = 1, . . . , m を凸関数，hi (x) i = 1, . . . , l をアフィン関数とし，制
約想定
ある x
^ ∈ X が存在してg(^
x) < 0;
h(^
x) = 0
0 ∈ int h(X),
h(X)
{y | yi = hi (x), i = 1, . . . , l; x ∈ X}
を満たすとする．このとき，
inf{f(x) | gi (x) ≤ 0, i = 1, . . . , m; hi (x) = 0, i = 1, . . . , l ; x ∈ X}
= sup{ψ(u, v) | ui ≥ 0, i = 1, . . . , m}
(4.17)
が成り立つ．
∑m
さらに，(4.17) の両辺の値が有限ならば，最適解 x∗ と u∗ の間に， i=1 u∗i gi (x∗ ) = 0 が成り
立つ．
第 4 章双対問題
50
証明は省いて，簡単な問題で直感的に説明する．例 4.1 と同様に，制約式が一本の不当式だけ
からなる場合を考えよう．
min
s.t.
f(x)
g(x) ≤ 0
x∈X
(4.18)
q = f(x)，p = g(x) とおき，G = {(p, q) | p = g(x), q = f(x), x ∈ X} とする．また，次のように
ϕ(p) を定義する．
ϕ(p)
{f(x) | g(x) ≤ p, x ∈ X}
(4.19)
ϕ(p) は単調減少関数である．なぜならば，p1 ≤ p2 にたいして，ϕ(p2 ) の方が制約式が緩和され
ている分だけ目的関数を小さくできるからである．p-q 平面上で，一般に G の形状は不定型であ
るが，ϕ(p) は G の下にある単調減少関数の中で最大のものとみなすことができる．主問題の最適
値は，ϕ(0) であることに注意しよう．
一方，双対問題の最適値は，G に下から接する直線の q 切片によってあたえられる．図 4.2 で
は，G の接線の q 切片と ϕ(0) が一致しておらず，双対ギャップが生じていることがみてとれる．
図表 4.2 双対ギャップの例
強双対定理は，目的関数・制約式が凸関数などの条件があると，双対ギャップが生じないことを
主張している．(4.17) で，f と g が凸関数，X が凸集合であるとしよう．このとき，ϕ(p) が凸関数
となることを示すことができる．そうすると，G に下から接する傾きが非正の接線のなかで q 切
片が最大になるのは，p < 0 で傾きが 0 で接する場合か，p = 0 で接する場合である．いずれの場
合も q 切片と ϕ(p) の値は一致し，双対ギャップは生じない．
定義 4.2 (鞍点)
問題 4.1 において，次のようにラグランジュ関数を定義する．
η(x, u, v) = f(x) +
m
∑
i=1
ui gi (x) +
l
∑
i=1
vi hi (x)
(4.20)
第 4 章双対問題
51
¯ ∈ X，u
¯ ≥ 0 であり，任意の x ∈ X と u ≥ 0，v にたいして
x
¯ , ¯v) ≤ η(x, u
¯ , ¯v)
η(¯
x, u, v) ≤ η(¯
x, u
(4.21)
¯ , ¯v) を鞍点 (saddle point) と呼ぶ．
が成り立つとき，(¯
x, u
図表 4.3 鞍点のイメージ
定理 4.5 (鞍点定理)
∑l
∑
¯ ∈ X，u
¯ ≥ 0 である (¯
¯ , ¯v) が関数 η(x, u, v) = f(x) + m
x
x, u
i=1 vi hi (x) の鞍点であ
i=1 ui gi (x) +
ることの必要十分条件は，次の a)，b)，c) が成り立つことである．
¯ , ¯v) = min{η(x, u
¯ , ¯v) | x ∈ X}
a) η(¯
x, u
b) gi (¯
x) ≤ 0, i = 1, . . . , m;
hi (¯
x) = 0, i = 1, . . . , l;
¯ i gi (¯
c) u
x) = 0, i = 1, . . . , m
¯ , ¯v) が鞍点であることの必要十分条件は，x
¯ が主問題の最適解，(¯
さらに， (¯
x, u
u, ¯v) が双対問題の
最適解となることである．
[証明]
前半：
¯ , ¯v) が関数 η(x, u, v) の鞍点であるとする．鞍点の定義より a) が成り立つ．また，η の定義
(¯
x, u
と鞍点の性質より，任意の u ≥ 0 と v にたいして
f(¯
x) +
m
∑
i=1
¯ i gi (¯
u
x) +
l
∑
i=1
¯vi hi (¯
x) ≥ f(¯
x) +
m
∑
i=1
ui gi (¯
x) +
l
∑
vi hi (¯
x)
(4.22)
i=1
となる．これが成り立つためには，b) gi (¯
x) ≤ 0, i = 1, . . . , m と hi (¯
x) = 0, i = 1, . . . , l が成り
∑m
¯ i gi (¯
立っていなくてはならない．また，(4.22) で u = 0 とおくと， i=1 u
x) ≥ 0 を得るが，一方
∑m
¯ i ≥ 0，gi (¯
¯ i gi (¯
でu
x) ≤ 0 より， i=1 u
x) ≤ 0 でなくてはならない．以上より，c) がいえる．
¯ ∈ X，u
¯ ≥ 0 である (¯
¯ , ¯v) が，条件 a)，b)，c) を満たすとする．まず，条件 a) より，
逆に x
x, u
¯ , ¯v) ≤ η(x, u
¯ , ¯v) が成り立つ．さらに，条件 b) ，c) から，η(¯
¯ , ¯v) もいえる．
η(¯
x, u
x, u, v) ≤ η(¯
x, u
¯ , ¯v) は鞍点である．
よって，(¯
x, u
第 4 章双対問題
52
後半：
¯ , ¯v) が鞍点であるとする．条件 b) から，x
¯ は主問題の実行可能解となる．また，u
¯ ≥0か
(¯
x, u
ら，(¯
u, ¯v) が双対問題の実行可能解であることもわかる．さらに，
¯ , ¯v) = f(¯
ϕ(¯
u, ¯v) = η(¯
x, u
x)
¯ は主問題の最適解，(¯
が成り立つので，弱双対定理より x
u, ¯v) が双対問題の最適解であることがい
える．
¯ が主問題の最適解，(¯
逆に，x
u, ¯v) が双対問題の最適解であるとしよう．双対定理より f(¯
x) =
¯
ϕ(¯
u, v) である．一方，主問題，双対問題の制約条件より
ϕ(¯
u, ¯v) = min{f(x) +
m
∑
¯ i gi (x) +
u
i=1
≤ f(¯
x) +
m
∑
i=1
¯ i gi (¯
u
x) +
l
∑
¯vi hi (x) | x ∈ X}
i=1
l
∑
¯vi hi (¯
x) = f(¯
x) +
i=1
m
∑
¯ i gi (¯
u
x) ≤ f(¯
x)
i=1
∑m
¯ i gi (¯
という不等式が成り立っている．f(¯
x) = ϕ(¯
u, ¯v) であるためには， i=1 u
x) = 0 でなくてはな
らない．以上より，条件 a)，b)，c) が成り立つことが確かめられた．
課題
1. 主問題を
min
s.t.
ex
x≥0
とおく．
(a) 主問題を解き，最適解と最適値を求めよ．
(b) 双対問題を作り，双対問題の最適解と最適値を求めよ．

Download Report