一般のノルム錐計画問題に対する弱双対定理

一般のノルム錐計画問題
に対する弱双対定理
ステラリンク株式会社
小崎敏寛
1. 線形計画問題の種類
2. 弱双対定理
3. 主双対内点法
統数研2015 3/19 3/20
2
線形計画問題の種類
• 非負変数の分類
統数研2015 3/19 3/20
1
0
1
2
4
3
3
弱双対定理
max
s.t.
min
s.t. Ax=b
x≥0
−
=
=
=
≥0
+
+ =c
z≥0
−
+⋯+
統数研2015 3/19 3/20
4
主双対内点法
• 主問題と双対問題の非負制約を強くみたしながら最適解を得る反復
解法
統数研2015 3/19 3/20
5
1.
2.
3.
4.
5.
6.
7.
ノルム錐計画問題とは
錐計画問題との関係
線形計画問題の弱双対定理
ノルムの定義と種類
pノルム錐計画問題
ノルム錐計画問題
まとめと今後の課題
統数研2015 3/19 3/20
6
ノルム錐計画問題とは
• 2次錐計画問題を一般化した次の問題：
min
s.t.
=
(NCP)
≥| : |
• ノルムはユークリッドノルムとは限らない．
統数研2015 3/19 3/20
7
錐計画問題との関係
•LP SOCP
SDP
NCP
統数研2015 3/19 3/20
8
線形計画問題の弱双対定理
min
s.t. Ax=b
x≥0
−
max
s.t.
=
=
=
≥0
+
+ =c
z≥0
−
+⋯+
統数研2015 3/19 3/20
9
ノルムの定義と種類
ノルムの定義
（1）||x||≥ 0, | | = 0 ⟺ = 0
（2）||αx||=|α|・||x||
（3）||x+y|| ≤ ||x||+ ||y||
ノルムの種類
• || || = ∑ | |
• || || = ∑
• || || = max | |
• || || ＝ ( ∑ | | )
/
定義よりノルムは凸関数
p≥ 1
統数研2015 3/19 3/20
10
Pノルム錐計画問題と双対問題
min
s.t. Ax=b
≥|
:
|
双対問題を，1/p+1/q=1,p≥1として
max
s.t.
+ =c
≥| : |
とする．
統数研2015 3/19 3/20
11
弱双対定理
−
=
=
=
≥
≥0
+
+
− ||
−
+⋯+
: || ||
ヘルダーの不等式より
:
||
統数研2015 3/19 3/20
主・双対実行可能性より
12
ノルム錐計画問題と双対問題
fをノルムとする．
min
s.t. Ax=b
≥ｆ（ｘ : ）
双対問題を，双対ノルムをf " (
:
):= max |ｘ1:n
ｆ（ｘ':(）=1
:
| として
max
s.t.
+ =c
≥ f "( : )
とする．
統数研2015 3/19 3/20
13
弱双対定理
−
=
=
=
≥
≥0
+
−
+
+⋯+
− ｆ（ｘ : ）f " (
:
)
統数研2015 3/19 3/20
双対ノルムの定義より
主・双対実行可能性より
14
まとめと今後の課題
まとめ
• 2次錐計画問題を一般化したノルム錐計画問題を提案した．
• ノルム錐計画問題に対して，弱双対性がなりたつことを示した．
今後の課題
• 強双対性がなりたつかどうか調べる．
• NCPを解く主双対内点法を考える．
• ベクトル変数だけでなく，行列変数を考える．
統数研2015 3/19 3/20
15

Download Report