最適化手法 講義資料（平成 27 年度 A1 セメスター）
分数計画
A ∈ Rm×n を定行列, b ∈ Rm , c ∈ Rn , p ∈ Rn を定ベクトル，d ∈ R, q ∈ R を定数とする．x ∈ Rn
を変数とする次の最適化問題を，線形分数計画問題という：
p⊤ x + q
min
x
c⊤ x + d
s. t. Ax ≤ b,
⊤
c x + d > 0.
問題 (1) の最適解は，y ∈ Rn と t ∈ R を変数とする線形計画問題
min p⊤ y + qt
y,t
s. t. Ay ≤ bt,
c⊤ y + dt = 1,
t≥0
を解くことで得られる．以下では，このことを説明する．
• 以下，試験の範囲外
命題 1. 問題 (1) に最適解が存在するとき，その最適値は問題 (2) の最適値に等しい．
証明. 問題 (1) の目的関数を f1 (x), 最適値を f1∗ とおく．また，問題 (2) の目的関数を
f2 (y, t)，最適値を f2∗ とおく．
まず，f1∗ ≥ f2∗ を示す．問題 (1) の任意の実行可能解を x̄ とおく．ȳ および t̄ を
ȳ =
x̄
,
c⊤ x̄ + d
t̄ =
1
c⊤ x̄ + d
と定義する．(ȳ, t̄) は問題 (2) の実行可能解であり，f1 (x̄) = f2 (ȳ, t̄) を満たす．従って，
f1∗ ≥ f2∗ が成り立つ．
次に，f1∗ ≤ f2∗ を示す．問題 (2) の任意の実行可能解を (ȳ, t̄) とおく．t̄ ̸= 0 ならば，x̄ を
x̄ =
ȳ
t̄
で定義すると，x̄ は問題 (1) の実行可能解であり，f1 (x̄) = f2 (ȳ, t̄) を満たす．t̄ = 0 の場
合には，ȳ と問題 (1) の任意の実行可能解 x0 に対して，x̄ を
x̄ = x0 + µȳ,
µ≥0
で定義する．すると，x̄ は問題 (1) の実行可能解であり，limµ→∞ f1 (x0 + µȳ) = f2 (ȳ, 0)
が成り立つ．つまり，問題 (2) の目的関数値にいくらでも近い目的関数値をもつような問
題 (1) の実行可能解が選べる．以上より，f1∗ ≤ f2∗ が成り立つことが分かる．
1
(1)
(2)
次に，問題 (1) の一般化として，最適化問題
min f0 (x)/h(x)
x
s. t.
h(x) > 0,
fi (x) ≤ 0,
(3)
i = 1, . . . , m
を考える．ただし，fi : Rn → R (i = 0, 1, . . . , m), h : Rn → R である．補助変数 s ∈ R を導入するこ
とで，問題 (3) は次の等価な問題に変形できる：
min f0 (x)/s
x,s
s. t.
0 < s ≤ h(x),
fi (x) ≤ 0,
i = 1, . . . , m.
(4)
ここで命題 1 と同様に考えて y = x/s, t = 1/s とおくと，問題 (4) は y ∈ Rn と t ∈ R を変数とする
次の最適化問題に帰着できる：
min tf0 (y/t)
y,t
s. t.
1 − th(y/t) ≤ 0,
tfi (y/t) ≤ 0,
t > 0.
(5)
i = 1, . . . , m,
一般に，関数 f : Rn → R に対して関数 g : Rn × R++ → R を
g(x, t) = tf (x/t)
(6)
で定義する（ただし，R++ = {t ∈ R | t > 0} である）．このとき，f が凸関数ならば g も凸関数であ
ることを示すことができる．
例 1. 凸 2 次関数 f (x) = x⊤ x に対して，(6) で定義される関数
g(x, t) = t(x/t)⊤ (x/t) =
x⊤ x
,
t
t>0
は凸関数である．このことは，t > 0 に対して
t2
[
]
..
[
tI
.
2
2
−tx
2
∇ g(x, t) = 3
=
tI
t3 −x⊤
t
t2
−tx⊤
x⊤ x
O
O
−x
]
⪰O
■
が成り立つことから確かめられる．
分数計画問題 (3) において，f0 , f1 , . . . , fm が凸関数であり h が凹関数（即ち，−h が凸関数）であ
ることを仮定する．このとき，問題 (3) と等価な問題 (5) は凸計画問題に帰着できる．
参考文献
[1] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge
(2004).
(2015, 寒野)
2
© Copyright 2024 ExpyDoc
