Complex LP と QP の弱双対定理

Complex LP と QP の弱双対定理
小崎敏寛∗
ステラリンク株式会社 (Stera Link, Co., Ltd.)
2015 年 12 月 21 日
2016 年 3 月 8 日改訂
概要
複素線形計画問題と複素凸二次計画問題を考える．これらの問題の弱双対定理を証明する．
1
はじめに
連続 (最適化) 問題は，次のように分類できる．
1. 問題 →(a) 最適化，(b) 方程式
2. 変数の種類 →(a) 実数，(b) 複素数
3. 変数の数 →(a)1 変数，(b) 多変数，(c) 無限変数
4. 関数の形 →(a) 線形，(b) 二次，(c) 多項式，(d) 非線形
5. 制約 →(a) なし，(b) あり
たとえば，線形計画問題は，(a)(a)(b)(a)(b) であり，一変数の代数方程式は，(b)(b)(a)(c)(a) で
ある．
2
内積
複素数ベクトルの内積としては次のようなものがある．
(i) < x, y >:= x̄T y
(ii) < x, y >:= xT ȳ
x̄T y + xT ȳ
(iii) < x, y >:=
2
¯
ただし (·) は複素共役．(iii) の内積は実数値をとり，
< (x + y), z >=< x, z > + < y, z >, < x, (y + z) >=< x, y > + < x, z >
実数 λ ∈ ℜ について，< λx, y >= λ < x, y >, < x, λy >= λ < x, y >
< x, y >=< y, x >
がなりたつ．
以下では，内積として (iii) を採用する．
∗ [email protected]
1
線形計画問題の弱双対定理
3
3.1
線形計画問題
線形計画問題 [1, 2, 3, 4] は，
min cT x
s.t. Ax = b
x≥0
(P-LP)
x ∈ ℜn
ただし，変数は x．双対問題は次のようになる．
max bT y
s.t. AT y + z = c
z≥0
(D-LP)
y ∈ ℜm , z ∈ ℜn
ただし，変数は (y, z).
3.2
弱双対定理
目的関数の差は次のようになる．
cT x − bT y = (AT y + z)T x − (Ax)T y
= xT z
= x1 z1 + · · · + xn zn
≥ 0.
したがって，弱双対定理がなりたつ．
複素線形計画問題
4
4.1
複素線形計画問題の定式化
考える問題は次の複素線形計画問題：
min < c, x >
s.t. < a1 , x >= b1
..
.
< am , x >= bm
x≥0
x ∈ Cn
2
(P-CLP)
ただし，定数は a1 , . . . , am ∈ C n , b1 , . . . , bm ∈ ℜ, c ∈ C n , 変数は x ∈ C n ．複素数ベクトルの不
等号を実部ベクトルと虚部ベクトルが非負とする．C n ∋ s, t ≥ 0 ならば < s, t >≥ 0 がなりたつ．
双対問題は次のようになる．
max bT y
s.t. AT y + z = c
(D-CLP)
z≥0
y ∈ ℜm , z ∈ C n
ただし，行列 AT を
AT := [a1 , · · · , am ]
(1)
とし，変数を (y, z) とする.
4.2
複素線形計画問題の弱双対定理
目的関数の差は次のようになる．
m
T
T
< c, x > −b y =< A y + z, x > −
< ai , x > yi
i=1
m
=< AT y, x > + < z, x > −
< ai , x > yi
i=1
m
=< [y1 a1 + · · · + ym am ], x > + < z, x > −
< ai , x > y i
i=1
m
=< y1 a1 , x > + · · · + < ym am , x > + < z, x > −
< ai , x > y i
i=1
m
= y1 < a1 , x > + · · · + ym < am , x > + < z, x > −
< ai , x > yi
i=1
=< x, z >
≥0
したがって，弱双対定理がなりたつ．
3
複素凸二次計画問題の弱双対定理
5
5.1
複素凸二次計画問題の定式化
考える問題は次の複素凸二次計画問題：
1
< x, Qx > + < c, x >
2
s.t. < a1 , x >= b1
min
..
.
(P-CQP)
< am , x >= bm
x≥0
x ∈ Cn
ただし，定数として，Q は半正定値エルミート行列，a1 , . . . , am ∈ C n , b1 , . . . , bm ∈ ℜ, c ∈ C n ,
変数は x ∈ C n ．双対問題は次のようになる．
1
< x′ , Qx′ >
2
s.t. AT y − Qx′ + z = c
max bT y −
z≥0
y ∈ ℜm , z ∈ C n
変数は (x′ , y, z).
5.2
複素凸二次計画問題の弱双対定理
目的関数の差は次のようになる．
1
1
< x, Qx > + < c, x > −bT y + < x′ , Qx′ >
2
2
m
1
′
′
T
′
= (< x, Qx > + < x , Qx >)+ < A y + z − Qx , x > −
yi < ai , x >
2
i=1
1
< x − x′ , Q(x − x′ ) > + < x, z >
2
≥0
=
したがって，弱双対定理がなりたつ．
参考文献
[1] 寒野善博, 土谷隆, 最適化と変分法, 丸善出版, 2014.
[2] 小島政和, 土谷隆, 水野眞治, 矢部博, 内点法, 朝倉書店, 2001.
[3] 今野浩, 線形計画法, 日科技連, 1997.
[4] S. J. Wright, Primal-Dual Interior-Point Methods, SIAM, 1997.
4
(D-CQP)

Download Report