1. No category

ゲージ錐計画問題の双対性
小崎敏寛 (Toshihiro Kosaki)∗
ステラリンク株式会社 (Stera Link, Co., Ltd.)
平成 26 年 12 月 18 日
概 要
2 次錐計画問題 [1] に表れる 2 次錐に似たゲージ錐を導入する．この錐を使った数理計画問題を導
入する．その問題に対して双対問題を考える．そして主問題と双対問題の間に弱双対定理がなりたつ
ことを示す．
1
はじめに
2 次錐は，ベクトルの 2 ノルムが非負実数で抑えられるという
t≥ x
2
(1)
という形式で記述される．アイデアは，ノルムより一般の関数であるゲージ f を考えることである．ゲー
ジ錐を x0 ≥ f (x1:n ) とする．この時，弱双対定理がなりたつことを示す．
2
考える問題
¯ をゲージ関数と言う．
次の 4 つの性質をみたす関数 f : ℜn → ℜ
1. f は凸関数,
2. f は非負,
3. f は正斉次 (すなわち, ∀α > 0, f (αx) = αf (x)),
4. f は f (0) = 0.
考えるゲージ錐問題は次のようになる．
min cT x
s.t. Ax = b
f (x1:n ) ≤ x0 .
変数は x := (x0 , x1:n ).
関数 f ◦ (z1:n ) := inf{v ≥ 0 : xT1:n z1:n ≤ vf (x1:n ) ∀x1:n } とする．
∗ [email protected]
1
(P)
双対問題は，
max bT y
s.t. AT y + z = c
(D)
◦
f (z1:n ) ≤ z0
となる．主問題と双対問題の目的関数値について，ゲージ関数 f と f ◦ について, xT y ≤ f (x)f ◦ (y) が成
り立つ [2] ことより，
cT x − bT y = (AT y + z)T x − (Ax)T y
= xT z
= x0 z0 + x1 z1 + · · · + xn zn
(2)
◦
≥ x0 z0 − f (x1:n )f (z1:n )
≥0
がなりたつことより，弱双対定理がなりたつ．
3
証明に使用した不等式
補題 1 実数 a ≥ b ≥ 0, c ≥ d ≥ 0 に対して，
ac − bd ≥ 0
(3)
がなりたつ．
(証明)
0 ≤ (a − b)(c − d) = ac + bd − ad − bc
= ac − bd + d(b − a) + b(d − c)
(4)
となる．d ≥ 0, a − b ≥ 0, b ≥ 0, c − d ≥ 0 より，
ac − bd ≥ d(a − b) + b(c − d)
≥0
(5)
がなりたつ．
4
まとめと今後の課題
この論文では，2 次錐計画問題を一般化したゲージ錐計画問題を提案した．ゲージ錐計画問題に対し
て，弱双対性がなりたつことを示した．
今後の課題として次のようなものがある．強双対性がなりたつかどうか調べる．ゲージ錐計画問題を
解く主双対内点法を考える．ベクトル変数だけでなく，行列変数を考える．
2
参考文献
[1] F. Alizadeh and D. Goldfarb, Second-Order Cone Programming, Mathematical Programming, 95,
3-51, 2003.
[2] R. M. Freund, Dual Gauge Programs, with Applications to Quadratic Programming and the
Minimum-Norm Problem, Mathematical Programming, 38, 47-67, 1987.
3