多項式最適化問題と双対性
東京工業大学情報理工学研究科
小島政和
第1回横幹連合コンファレンス
2005年11月25,26日
JA 長野県ビル
目次
1. 多項式最適化問題
2. Lagrange緩和とLagrange双対問題
3. 2乗和多項式と一般化Lagrange双対問題
4. 数値例
5. おわりに
目次
1. 多項式最適化問題
2. Lagrange緩和とLagrange双対問題
3. 2乗和多項式と一般化Lagrange双対問題
4. 数値例
5. おわりに
多項式最適化問題(POP)
p*  min f0 (x) s.t. f j (x)  0( j  1,K , m)
ただし, f0 ,K , fmは x  (x1 ,K
を変数とする多変数多項式
, xn ) R
n
多項式最適化問題(POP)
p*  min f0 (x) s.t. f j (x)  0( j  1,K , m)
例: n=3, m=2.
min f0 (x)  x13  2x1x23  x12 x2 x3  4x32
sub.to
2
f1 (x)  x1  5x2 x3  1  0
2
f2 (x)  x1  3x1x2 x3  2x3  2
x1 (x1 1)  0 (0 1 integer)
0
x2  0, x3  0, x2 x3  0 (complementarity)
多項式最適化問題(POP)
p*  min f0 (x) s.t. f j (x)  0( j  1,K , m)
• さまざまな問題が多項式計画問題として定式化
• 組合せ最適化問題を含む非凸型最適化問題に
対する大域最適化の統一的な枠組みを提供する.
目次
1. 多項式最適化問題
2. Lagrange緩和とLagrange双対問題
3. 2乗和多項式と一般化Lagrange双対問題
4. 数値例
5. おわりに
POP: p*  min f0 (x) s.t. f j (x)  0( j  1,K , m)
m
Lagrange 関数:
n
m
L(x,  )  f0 (x)    j f j (x) ((x,  ) R  R )
固定された 
m
R
j1
に対して,Lagrange緩和問題
L *( )  min{L(x,  ) : x R }
n
このとき, L *( )  p * (
m
R )
証明
m
x: 許容解,j  0   j f j (x)  0    j f j (x)  0
m
j1
 f0 (x)  f0 (x)    j f j (x)  L(x,  )
j1
 min{L(x,  ) : x は許容解 }  L * ( )
POP: p*  min f0 (x) s.t. f j (x)  0( j  1,K , m)
m
Lagrange 関数:
n
m
L(x,  )  f0 (x)    j f j (x) ((x,  ) R  R )
固定された 
m
R
j1
に対して,Lagrange緩和問題
L *( )  min{L(x,  ) : x R }
n
このとき, L *( )  p * (
m
R )
最良のLagrange緩和問題=Lagrange双対問題
L*  max{L *( ) : 
m
R }
このとき, L *( )  L*  p * ( Rm )
一般には,双対ギャップ p * L*  0が存在する
POP: p*  min f0 (x) s.t. f j (x)  0( j  1,K , m)
m
Lagrange 関数:
n
m
L(x,  )  f0 (x)    j f j (x) ((x,  ) R  R )
j1
Lagrange緩和: L *( ) 
min{L(x,  ) : x R }
n
Lagrange双対問題: L*  max{L *( ) :  Rm }
このとき, L *( )  L*  p * (
m
R )
双対ギャップ p * L*  0 を0にしたい!
理想的な方法は,罰金関数
i (x)  
0 if fi (x)  0
 if fi (x)  0
目次
1. 多項式最適化問題
2. Lagrange緩和とLagrange双対問題
3. 2乗和多項式と一般化Lagrange双対問題
4. 数値例
5. おわりに
罰金関数を2乗和多項式で近似する
2乗和多項式の集合:
k
  { gi (x)2 : gi (x) is a polynomial, k}
i1
例
n  1, f (x)  (x  4)  (5x  x  x  3)
2
3
2
2
n  2, f (x1, x2 )  (x1  2x2 )2  (3x1x2  x2  4)2
2乗和多項式の集合:
k
  { gi (x)2 : gi (x) is a polynomial, k}
i1
一般化Lagrange関数
m
L(x,  (x))  f0 (x)    j (x) f j (x) ((x,  (x)) Rn   m )
j1
一般化Lagrange双対問題:
 *  max min{L(x,  (x)) : x R }
n
  m
  *  p * (POPの最小値)
POPの許容領域が有界   *  p *
一般に
数値的に解くためには,2乗和多項式の次数を r に
制限して近似する必要がある.
次数r以下の2乗和多項式の集合:
k
 r  { gi (x)2 : gi (x) is a polynomial with deg  r, k}
i1
例
n  1, f (x)  (x  4)  (5x  x  x  3)  3
2
3
2
2
n  2, f (x1, x2 )  (x1  2x2 )2  (3x1x2  x2  4)2
 2
次数r以下の2乗和多項式の集合:
k
 r  { gi (x)2 : gi (x) is a polynomial with deg  r, k}
i1
一般化Lagrange双対問題(次数r以下)
maxm min{L(x,  (x)) : x R }
n
  r
 max 
s.t. L(x,  (x))    0 (x Rn ),   rm
  r *  max 
s.t. L(x,  (x))    r (x Rn ),   rm
*
 p * . 緩い条件の下で  r*  p *
一般に  r*   r1
半正定値計画問題として解ける.
目次
1. 多項式最適化問題
2. Lagrange緩和とLagrange双対問題
3. 2乗和多項式と一般化Lagrange双対問題
4. 数値例
5. おわりに
一般化されたRosenbrock関数の最小化
n
2 2
f (x)  1  (100(xi  xi1
)  (1 xi )2 )
i2
n
600
700
800
900
1000
精度
3.9e-7
7.5e-9
2.1e-7
2.1e-7
4.5e-7
計算時間(秒)
3.4
4.0
5.1
5.9
5.9
精度=(近似最適値ー最適値の下界値)/|最適値の下界値|
近似最適解と最適値の下解値
多項式の疎性を活用している!

大域的最適解の精度保証
目次
1. 多項式最適化問題
2. Lagrange緩和とLagrange双対問題
3. 2乗和多項式と一般化Lagrange双対問題
4. 数値例
5. おわりに
大域的最適化のための数値計算手法としては
非常に強力.
発展途中段階 --- 課題
•大規模半正定値計画問題を解く必要がある
•多項式の疎性の有効利用
•数値的な安定性
理論的には多項式半正定値計画問題
(多項式行列不等式)に拡張されている
ダウンロード

多項式最適化問題と双対性