ゲージ錐計画問題の双対性小崎敏寛 (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