1. No category

Quadratic Power Cone Programming の弱双対定理
小崎 敏寛∗
ステラリンク株式会社 (Stera Link, Co., Ltd.)
平成 27 年 4 月 13 日
概 要
Power Cone Programming[1] を一般化した Quadratic Power Cone Programming を考え
る．目的関数を凸二次関数に拡張する．この問題を徐々に一般化した 4 つの問題に対して，弱双
対定理を証明する．
1
はじめに
Power Cone Programming[1] は次の問題
min cT x
s.t. Ax = b
n
i
xα
i ≥ |z|
(1)
i=1
x ∈ {(xi , z) ∈
ℜn+
× ℜ}
n
αi = 1, 0 < αi < 1 i = 1, . . . , n.
i=1
2
Quadratic Power Cone Programming
目的関数に凸二次関数を考える．
1 T
x Qx + cT x
2
s.t. Ax = b
min
n
i
xα
i ≥ |z|
(P)
i=1
x ∈ {(xi , z) ∈ ℜn+ × ℜ}
n
n
αi = 1, 0 < αi < 1 i = 1, . . . , n, Q ∈ S+
.
i=1
∗ [email protected]
1
双対問題は次のようになる．
1
max bT y − xT Qx
2
T
s.t. A y + s − Qx = c
n
i=1
(D)
αi
si
αi
≥ |t|
s ∈ {(si , t) ∈ ℜn+ × ℜ}
主問題の実行可能解 x と双対問題の実行可能解 (y, x′ , s) について，目的関数の差は次のように
なる．
1 T
1 T
1
1 T
x Qx + cT x − (bT y − x′ Qx′ ) = (AT y + s − Qx′ )T x − (Ax)T y + xT Qx + x′ Qx′
2
2
2
2
1
= xT s + (x − x′ )Q(x − x′ )
2
n
1
xi si + zt + (x − x′ )Q(x − x′ )
=
2
i=1
n
≥
n
xi si −
i=1
i=1
xi si
αi
αi
1
+ (x − x′ )Q(x − x′ )
2
≥0
1 つ目の不等号は錐に入っていることより，2 つ目の不等号は相加相乗平均の不等式と行列 Q の半
正定値性よりなりたつ．したがって，弱双対定理がなりたつ．
3
ユークリッドノルムのとき
絶対値をユークリッドノルムに一般化した次の問題を考える．
1 T
x Qx + cT x
2
s.t. Ax = b
min
n
i
xα
i ≥ z
2
(P-2)
i=1
x ∈ {(xi , zj ) ∈ ℜn+ × ℜm }
n
n
αi = 1, 0 < αi < 1 i = 1, . . . , n, Q ∈ S+
.
i=1
2
双対問題は次のようになる．
1
max bT y − xT Qx
2
T
s.t. A y + s − Qx = c
n
i=1
αi
si
αi
≥ t
2
(D-2)
s ∈ {(si , tj ) ∈ ℜn+ × ℜm }
n
αi = 1, 0 < αi < 1 i = 1, . . . , n.
i=1
主問題の実行可能解 x と双対問題の実行可能解 (y, x′ , s) について，目的関数の差は次のように
なる．
1 T
1 T
1
1 T
x Qx + cT x − (bT y − x′ Qx′ ) = (AT y + s − Qx′ )T x − (Ax)T y + xT Qx + x′ Qx′
2
2
2
2
1
T
′ T
′
= x s + (x − x ) Q(x − x )
2
n
m
1
=
xi si +
zj tj + (x − x′ )T Q(x − x′ )
2
i=1
j=1
n
xi si − z
≥
i=1
n
≥
2
n
xi si −
i=1
i=1
t
2
xi si
αi
1
+ (x − x′ )T Q(x − x′ )
2
αi
1
+ (x − x′ )T Q(x − x′ )
2
≥0
1 つ目の不等号はコーシーシュワルツの不等式より，2 つ目の不等号は錐に入っていることより，3
つ目の不等号は相加相乗平均の不等式と行列 Q の半正定値性よりなりたつ．したがって，弱双対
定理がなりたつ．
4
Lp ノルムのとき
ノルムを Lp ノルムに一般化した次の問題を考える．
1 T
x Qx + cT x
2
s.t. Ax = b
min
n
i
xα
i ≥ z
p
(P-p)
i=1
x ∈ {(xi , zj ) ∈ ℜn+ × ℜm }
n
n
αi = 1, 0 < αi < 1 i = 1, . . . , n, Q ∈ S+
.
i=1
3
双対問題は次のようになる．
1
max bT y − xT Qx
2
T
s.t. A y + s − Qx = c
n
i=1
αi
si
αi
≥ t
q
(D-p)
s ∈ {(si , tj ) ∈ ℜn+ × ℜm }
n
αi = 1, 0 < αi < 1 i = 1, . . . , n.
i=1
ただし，p ≥ 1 の有理数で，q は 1/p + 1/q = 1 をみたす定数．
主問題の実行可能解 x と双対問題の実行可能解 (y, x′ , s) について，目的関数の差は次のように
なる．
1 T
1
1 T
1 T
x Qx + cT x − (bT y − x′ Qx′ ) = (AT y + s − Qx′ )T x − (Ax)T y + xT Qx + x′ Qx′
2
2
2
2
1
= xT s + (x − x′ )T Q(x − x′ )
2
n
m
1
=
xi si +
zj tj + (x − x′ )T Q(x − x′ )
2
i=1
j=1
n
≥
xi si − z
i=1
n
n
xi si −
≥
i=1
i=1
p
t
q
xi si
αi
1
+ (x − x′ )T Q(x − x′ )
2
αi
1
+ (x − x′ )T Q(x − x′ )
2
≥0
1 つ目の不等号はヘルダーの不等式より，2 つ目の不等号は錐に入っていることより，3 つ目の不
等号は相加相乗平均の不等式と行列 Q の半正定値性よりなりたつ．したがって，弱双対定理がな
りたつ．
5
一般のノルムのとき
ノルムを一般のノルム f (·)[2] に一般化した次の問題を考える．
1 T
x Qx + cT x
2
s.t. Ax = b
min
n
i
xα
i ≥ f (z)
(P-n)
i=1
x ∈ {(xi , zj ) ∈ ℜn+ × ℜm }
n
n
αi = 1, 0 < αi < 1 i = 1, . . . , n, Q ∈ S+
.
i=1
4
双対問題は次のようになる．
1
max bT y − xT Qx
2
T
s.t. A y + s − Qx = c
n
i=1
αi
si
αi
≥ f D (t)
(D-n)
s ∈ {(si , tj ) ∈ ℜn+ × ℜm }
n
αi = 1, 0 < αi < 1 i = 1, . . . , n.
i=1
ただし，f D は f の双対ノルム [2] で，
f D (y) := max |xT y|
(2)
f (x)=1
と定義される．
主問題の実行可能解 x と双対問題の実行可能解 (y, x′ , s) について，目的関数の差は次のように
なる．
1
1 T
1
1 T
cT x + xT Qx − (bT y − x′ Qx′ ) = (AT y + s − Qx′ )T x − (Ax)T y + xT Qx + x′ Qx′
2
2
2
2
1
T
′ T
′
= x s + (x − x ) Q(x − x )
2
n
m
1
=
xi si +
zj tj + (x − x′ )T Q(x − x′ )
2
i=1
j=1
n
≥
1
xi si − f (z)f D (t) + (x − x′ )T Q(x − x′ )
2
i=1
n
≥
n
xi si −
i=1
i=1
xi si
αi
αi
1
+ (x − x′ )T Q(x − x′ )
2
≥0
1 つ目の不等号は双対ノルムの定義より，2 つ目の不等号は錐に入っていることより，3 つ目の不
等号は相加相乗平均の不等式と行列 Q の半正定値性よりなりたつ．したがって，弱双対定理がな
りたつ．
6
結論と今後の課題
Power Cone Programming の目的関数を線形から凸二次に一般化した 4 つの問題に対して弱双
対定理を証明した．今後の課題としては，強双対定理がなりたつか調べること，問題を解くアルゴ
リズムを考えることがある．
5
参考文献
[1] Peter R. Chares, Cones and Interior-Point Algorithm for Structured Convex Optimization
involving Powers and Exponentials, Ph.D. thesis, Universite catholique de Louvain Ecole
Polytechnique de Louvain, 2007.
[2] Roger A. Horn and Chrles R. Johnson, Matrix Analysis, Cambridge University Press, 2007.
6