双対問題

一次式とノルムで構成された最適化問題とその双対問題

第一部 ゲージ最適化問題とその応用問題

京都大学大学院情報学研究科 山下信雄 2018年7月25日 (本資料は7月30日に改訂)

本講演の概要

第1部 一般化ゲージ最適化問題とその応用問題

第2部 ゲージ関数とその諸性質

第3部 一般化ゲージ最適化問題の双対問題

I. ラグランジュ双対問題とFenchel双対問題

II. Gauge双対問題

III. 新しいタイプの双対問題

用語

• 凸関数(convex function)

• 標示関数(indicator function)

• 実効定義域(effective domain)

(1

) ))

( )

(1

) ( )

( x

y

f

f



 







x

 



f y

if

0

(

otherwi

)

se

S

x

x

S









 

_







dom

f



x



V

f

( )

x

 

第1部 概要

1. 今回考える問題

• ノルムとその一般化した関数(ゲージ関数) • 1次式とゲージ関数で構成された最適化問題

2. 応用問題

ゲージ最適化問題 • L1-L2最適化問題 • 半正定値計画問題 2次錐計画問題 絶対値計画問題 • 0-1整数計画問題 • 線形な均衡制約つき最適化問題(MPEC)

今回考える問題の準備：

ゲージ関数（ノルムの一般化）

定義 以下の性質を満たす関数 をゲージ関数_{(gauge function)という} (i) 非負の関数 (ii) 凸関数

(iii) 正斉次(Positively homogeneous)

例： ノルムは上記の条件を満たす

:

V

R

{ }



  

( )

tx

t

( )

x

t

0

ノルムとゲージ関数

norm: 標準，基準….. gauge: 基準，規格，標準寸法…. 注意：今回の話はゲージ理論とは関係ない ノルムはゲージ関数 非負性： 正斉次性： 凸性： に対して

0

x 

(

0)

tx



t

x

t



(1 ) (1 ) (1 ) x y x y x y           

[0,1]





三角不等式

ノルムの例（有名なもの）

ベクトルのノルム • pノルム • 無限大ノルム • 1ノルム ⇒ 正則化やスパース化によく使われる 行列のノルム • Frobenius ノルム • Nuclear ノルム ⇒ Nuclearノルムは rank(A) の 凸緩和として使われる | _i |p p p x x   max | _i | i x _  x 1 | i | x 



x ( )A A  を行列 の特異値を並べたベクトルとする 2 ( ) F A   A * ( ) 1 A   A

ノルムの例(有名でないもの?)

：

の成分を，絶対値の大きい順に並べたときの 番目 利用例 CVaRノルム (largest-k ノルム) ある線形計画問題の最適値として表せるため， 最適化モデルで使いやすい 応用： 金融のCVaR, ν-SVM ( )i

x

n

x



R

i (1) | | (2) | ( ) | x  x  | x _n | 1 (1) ( ) ₁ 1 1 ( ) , i n i i i x x x x x     







( ) CVaR , 1

|

|

n n i i

x

x

   





ノルムでないゲージ関数

• 0とのMax関数(演習問題) ＊損失関数やペナルティ関数に使われる • 凸錐 の標示関数 凸関数の標示関数 ⇒ 非負の凸関数 錐の標示関数 ⇒ 正斉次関数

 

1 ( ) max 0, n i i x x   



C

_C( )x

今回考える問題の準備

• 変数 を 個に分割する． • ベクトル値ゲージ関数： ただし はゲージ関数

x V



1 2

,

,

)

1 2

( ,

x

V

V

x



x x

 

V





 

:

(

1,

,

)

i

V

i

R

i



  





1 1 2 2 ( ) ( ) ( ) ( ) x x x x                 

:

V

(

R

{ })





 





dom

 

x x

_i



dom



_i

(

i



1

,



,

)

一般化ゲージ最適化問題

ただし， は適当な大きさの ベクトルや行列(線形写像) が非負ベクトル， の各成分が０以下 凸最適化問題

min

,

, ( )

s.t.

( )

( )

c x

d

x

x

b

x

Ax

B

Hx

K

e



   















0,

B



d

, , , , , ,

,

c b d e A B H K

一般化ゲージ最適化問題 特別な凸最適化問題 Gauge 最適化問題 絶対値計画 K

ゲージ最適化問題

_{(Gauge Optimization)}

[Freund, 1987], [Friedlander, Macedo, and Pong, 2014], etc

min

( )

s.t.

(

)

x

Ax

b











• と はゲージ関数 • は線形写像， は定数ベクトル • は非負の定数 • 凸最適化問題である．





A



b

        ( ) min ( ) ( ) s.t. ( 0, 1 ) ( 0 0 0 ) 0 0 ( 0 1 ) , x y x A I b y x y y x x y x y                                _{ } _{ }                   

ゲージ最適化の応用例１： L1-L2最適化

基底追跡ノイズ除去 (Basic pursuit denoising)

1

min

s.t.

x

ゲージ最適化の応用例２：半正定値計画問題

(ちょっとトリッキーですが．．) 半正定値行列の集合の標示関数： 双対問題の実行可能解： が実行可能解であれば， よって， _{⇒ (実行可能集合上で)Gauge関数} ( ) S X  _

y

1 1 max s.t. i i i i m i m i b C y y A S     





min s.t. , ( 1, ) , , i i C X A X b S i X m      X 1 1 , , , _{i i} 0 n n i i i i C A X C b C X y X y         (X) C, X _S (X) 0   _  は半正定値対称行列の集合 S_ trace( , ) C X  C X i i y A C  C



SDP ⇒ ゲージ最適化問題

1 , ( 1, min , , ) s.t. m i i i i i C X b A X m S b i X y         min s.t. , ( 1, ) , , i i C X A X b S i X m      min s.t. , , , ( 1, ) i i X A X b m C i X S_     min s.t. , ( 1, ) ) , ( , i S i C X X X A b i m  _     min s.t. , ) ) ( , ( 1, i i A X i X b m     min ( ) s.t. ( ) 0 X AX b     1 ( ) , , , m X y y X A AX A             

SDP ⇒ 一般化ゲージ最適化問題

min s.t. , ( 1, ) , , i i C X A X b S i X m      , ( min s.t. , , 1 1, ) ( ) i i S C X A b i X X m  _     一次式が使えるので簡単

2次錐計画問題

(Second-order cone programming problem)

ただし， は p 次元の2次錐:

min

s.t.

,

c x

Ax

K

b

x





1 2 1 , n i i n Kn K K K n n      



p K



2 2 2



1 2 3 p p p K  x R x  x  x   x 2 3 1 p x x x x              一次式とノルム

凸2次不等式制約 ⇒ 2次錐制約

ただし は半正定値対称

0

x

b

A

x

c

x



 

2

0

C

x



b x

 

c

A

,

r n

A



C

C

C



R

 2 _{2 2}

)

(

(1

1

4

Cx





b

x



c





b

x



c

)

2 ₂

4

Cx

 

(1

b

x



c

)

 

1

b

x



c

2

1

1

2

r

b x

c

b x

c

Cx

K

_











_

_

















凸２次関数とノルムで表された目的関数や 凸２次不等式制約は 一次式とノルムで表せる

絶対値計画問題

[Mangasarian, 2007]

ただし， ・ 非凸な問題 ・ モデル化能力は高いがあまり研究されていない．

min

,

,| |

s.t.

| |

|

|

Ax

B x

c x

d x

b

x

e

H

K

x







  







1 2 | | | | | | | | n x x x x             

絶対値計画問題の応用例：0-1最適化問題

min s.t. , ( {0,1} 1, , ) i c x Hx x i e n     1 {0,1} | 1, ( 1) 2 | i i i i x   y  x  y  , | ( min s.t. 1 ( 1), | 1 , ) 2 1, i i i e y c x n x H x y i      

絶対値方程式と線形相補性問題

(Absolute Value Equations and Linear Complementarity Problem)

[Mangasarian, 2014] 絶対値方程式： 線形相補性問題

Ax



B x



b

0,

Mz

q

0,

z

(

M

)

0

z



 

z



q



(

M



I z

)

 

q

(

M



I z

)



q

( ) y  M  I z  q (M  I z)  q y 0 0 0 0 y I I M y q z I M z I q            _{ }   _   _  _         

LCP

AVE

各成分ごとに考えればよい． のとき， のとき， よって， のとき のとき

0,

0,

(

)

0

Mz

q

z

M

z

z

q

 







(

)

(

)

M

I z

q

M

I z

q











((M  I z)  q)_i  0

z

i



0,

(

Mz



q

)

i



0

((M  I z)  q)_i  0 (Mz  q)_i  0, z_i  0 0, 0, , (Mz  q)_i  z_i  (Mz  q z)_{i i}  0 (i 1, m) (Mz  q)_i  0, z_i  0 0  (Mz  q)_i  ((M  I z)  q)_i  ((M  I z)  q)_i  (M  I z)  q ) 0, (Mz  q _i  z_i  0 0 ( ) (( ) ) ( ) ( ) (( ) ) ( ) i i i i i i Mz q z M I z q Mz q z M I z q M I z q                  

LCP制約つき最適化問題

（線形なMPEC） この問題は一般化ゲージ最適化問題として書ける． （演習問題） 1 2

min

s.t.

0,

0

0

,

(

)

c x

c y

Ax

y

My

Nx

q

y

My

Nx

q

b



















一次式とノルムで構成された最適化問題とその双対問題

第2部 ゲージ関数とその性質

京都大学大学院情報学研究科 山下信雄

第2部の概要

1. ゲージ関数 2. 共役関数

3. ゲージ関数の極関数 4. ゲージ関数の共役関数

ゲージ関数（再掲）

定義 以下の性質を満たす関数 をゲージ関数_{(gauge function)という} (i) 非負の関数 (ii) 凸関数

(iii) 正斉次(Positively homogeneous)

:

V

R

{ }



  

( )

tx

t

( )

x

t

0

共役関数とその諸性質

(室田先生の予習資料) 凸関数 の_{共役関数(ルジャンドル変換)} 共役関数の諸性質: • • • は凸関数 f





*

( )

sup

_x

,

( )

f

y



y x



f x

** * *

(

)

f



f



f

*

(

( )

y

)

,

f x



f



x y

Fenchel双対の双対性で重要 Fenchel双対の Fenchel双対を 考える上で重要 *

f

Fenchel双対の 凸性で重要

ゲージ関数の極関数

ゲージ関数

の

_{極関数(polar function)}

がノルムのとき，

は

双対ノルム

参考：共役関数

f





( )

sup

x

,

( )

1

f



y



y

f

x







*

( )

sup

_x

,

( )

f

y



y x



f x

f

f



双対ノルムの例

• L1ノルム 無限大ノルム • pノルム • CVaRノルム 1 x x _ i p p p x 



x _q 1 1 1 p q x 　ただし   CVaR , x _ 1 CVaR , max , x x n n x _      _ _  

極関数の例

• 0とのMax関数 • 錐 の標示関数 極錐 の標示関数 ただし

C

( )

C

x



C

,

{

|

0

}

C





y

x y



 

x

C

( )

C

x



 1 max{0 ( ) , } m i i g x x  



max if 0 ot ( ) herwise i i y g y y       

極関数の諸性質

共役関数の諸性質(再掲)

•

•

•

は凸関数

ゲージ関数の極関数の諸性質

•

•

•

はゲージ関数

(

)

f





f

 



f

** * * ( ) f  f  f * ( ( ) y) , f x  f  x y ( ) , dom , d ( ) y x y x f y om f f x  f       

f

 * f Gauge双対の 双対性で重要 Gauge双対のGauge双対を 考える上で重要 Gauge双対の 凸性で重要

「極関数

はゲージ関数」の証明

非負性： より 正斉次性： 凸性：

f







sup 1 0 ( ) , ( ) x f  y  x y f x  

(0)

0

f











( ) sup , ( ) 1 sup , ( ) 1 ( ) x x f  ty  x ty f x   t x y f x   tf  y

















ˆ , ˆ sup 1 ˆ ˆ sup 1, ( ) 1, ˆ ˆ sup 1 s ( (1 ) ) , (1 ) ( ) , , (1 ) ( ) , ( ) , (1 ) ( ) ( up ˆ 1 ) ) ( ( 1 ) x x x x x f y z x y z f x x y z f x x y f x z y x f x x x x f f f x z                                 

の証明

(i)

のとき， そうでないとすると よって， より これは に矛盾

(

(

)

y

)

,

f x f





x y

( ) 0 f x  x y,   0 y dom f  , 0 x y  ( ( x) f ) 0 1 f







x   , , as x y x y







 



 





sup

,

)

)

1

(

x y

f

(

f



y



x



 

dom

y



f



の証明(続き)

(ii)

のとき， とすると よって，

(

(

)

y

)

,

f x f





x y

( ) 0 f x 





sup , ( ) 1 ( ) 1 , ( ) , f y x x y f x y x z y f  _    1 ( ) ( ) 1 ( ) ( ) x f f f x f x x z f    _{ }     ( ) z x f x 

ゲージ関数の共役関数 (演習問題)

をゲージ関数とする． を錐とする． ただし

f

*

if

( )

1

o

0

t

( )

herwise

y

f

f

y





 









C

* C C _C







 







,

0



C





y

x y

  

x

C

一次式とノルムで構成された最適化問題とその双対問題

第3部 双対問題

京都大学大学院情報学研究科 山下信雄

第3部 概要

1. 双対問題とその応用

2. ゲージ最適化問題の双対問題

I. ラグランジュ双対問題とFenchel双対問題 II. Gauge双対問題 III. 新しいタイプの双対問題

4. まとめ

数理最適化問題（主問題）

( )

s.t.

( )

0,

1,

,

( )

0,

1

m n

,

i

,

i j

f x

h x

i

m

g x

j

r

x

X



 



 



以下では 実行可能集合



_i( )x 0 ( 1, ,m g), _j( ) 0 ( 1, , )



F  x h  i   x  j   r



F,



S  x x x X

双対問題とは

元の問題(主問題)を鏡で映したようなもの． 主問題 双対問題 最小化 ⇔ 最大化 決定変数の数 ⇔ 制約条件の数 制約条件の数 ⇔ 決定変数の数

max

( , )

s.t.

,

0

m r

R

R

  













( ) s.t. ( ) 0, 1, , ( ) 0, 1 m n , i , i j f x h x i m g x j r x X        主問題 双対問題

双対問題の望ましい性質

• (弱)双対性： それぞれの実行可能解 に対して • (適当な仮定の下)双対問題の双対問題は主問題になる．

,

(

)

(

)

f x



  

min s.t. 0 i x Ax b x  



max 1 1 s.t. 1 , b A                , , ( ) x   max s.t. 0 i   



例

ラグランジュの双対問題

ラグランジュ関数: 標示関数： 1 1

, )

(

( ,

)

( )

( )

m r i j i j i j

f x

x

L x







h



g x

 











if { ( ) 0 0 | , ( ) 0 othe } s ( e ) rwi i j F F x x x g x h x



         0 1 , 1

( )

sup

m

( )

( )

m r F _R i j j i i j

x

x

x

_{ }

h

g



_{ }





 





















主問題(元の問題)のmin-max表現

主問題の目的関数

min

(

( )

s

)

.t.

F

f

x

x

x

X







0 1 1 0 1 1 0 , , , ( ) ( ) sup ( ) ( ) ( ( ) sup ) ( ) ( ) ( , s pu , ) m m m m r F _R i i j j i j m r i i j j R i j R x f x x x f x f x h g x x g x h L                            _  _             









ラグランジュ双対問題

[主問題]

[双対問題]

0 ,

su

m

in

_{x X}

p

m

(

, , )

R

L x

 

 

 _{ }

max

( , , )

s. t

i

0

nf

,

.

m x X

L x

R

 











弱双対定理

双対問題の目的関数(必ず凹関数)： ⇒ 下界値の計算に利用できる

, )

)

(

inf

_{x X}

L x

( , ,

w

 



_

 

弱双対定理

( )

w

( , )

x

,

R

m

,

0

f x



 

 

S









強双対定理

: 凸関数 ：１次関数 適当な制約想定が成り立つ． 主問題に最適解が存在する． ↓ 主問題と双対問題の最適値は一致する． , ) , ( 1, , ) ( 1, j i r h m f g j i    

双対問題の利用１：感度解析

ラグランジュ双対問題の最適解には経済的な意味がある． 最適値関数 ラグランジュ双対問題の最適解を とする． を制約条件 の潜在価格_{(シャドウプライス)という} | ( 1, ( )u min{ ( )f x h_i( )x u_i i ,m), g x_j( ) 0( j 1, ,r)}         * * ( ,  ) * (0) i i u    _  * i



h x _i( ) 0

双対問題の利用２： 解法の開発，解析

[解法] • ラグランジュ緩和 (応用例：オンライン広告, 火力発電計画，etc) ⇒ 並列化，逐次計算を可能にする． • サポートベクターマシン • etc [解析] • 乗数法(拡張ラグランジュ法) ⇔ 双対問題では近接点法

＊Dual Augmented Lagrangian method [Tomioka,etc, 2011]はこの逆 • Alternating Direction Method of Multipliers (ADMM)

⇔ 双対問題ではDouglas-Rachford Splitting (近接勾配法みたいなもの)

双対問題の利用３：ロバスト最適化

データが不確実なとき，最悪の場合を考えての最適化 半無限計画(semi-infinite programing)か， 制約条件中に最適化問題が含まれる問題になる． min s.t. ( ) ; ) 0 ( f x g x u   u U

min

s.t. ma

( )

(

)

x

_{u U}

;

0

f x

g x u





ロバスト最適化 不確実なデータ 不確実性集合

双対問題の利用３：ロバスト最適化

min s.t. ma ( ) ( ) x_{u U} ; 0 f x g x u   制約条件中の問題 ( ; ) max s.t. g x u uU ロバスト最適化 双対問題 min ( ; ) s.t. x     

, ( ; )

0

max ( , )

( , )

0

u U

x

g x u

x



 

 







 





弱双対 min s.t. ( ) ; ) 0 ( f x w x      強双対性が成り立てば等価

第3部 概要

1. 双対問題とその応用

2. ゲージ最適化問題の双対問題

I. ラグランジュ双対問題とFenchel双対問題 II. Gauge双対問題 III. 新しいタイプの双対問題

4. まとめ

一般化ゲージ最適化問題

ただし， は適当な大きさのベクトルや行列

min

,

, ( )

s.t.

( )

( )

c x

d

x

x

b

x

Ax

B

Hx

K

e



   















, , , , , ,

,

c b d e A B H K

一般化ゲージ最適化問題 特別な凸最適化問題 Gauge 最適化問題 絶対値計画

一般化ゲージ最適化問題の補正

min

,

, ( )

s.t.

( )

( )

dom

Ax

B

c x

d

x

x

x

x

e

K

b

Hx





   

















一般化ゲージ最適化問題は，実効定義域外では， 定義が不明瞭になる場合がある． そこで以下では，制約条件に実効定義域を加えた 次の問題を考える．

ラグランジュ双対問題

ラグランジュ関数： 目的関数： • 陽に表しにくい．制約がないときはどうする？ → Fenchel 双対問題 • 他のタイプはないの？ → Gauge 双対問題 ( ) ( ( , , ) , , , ) , ( ) L x u v c x d u b Ax B v e Hx K x x x            dom

( , )

i

nf

( , ,

)

x

L

u v

v

x

u



 



Fenchel 双対問題

凸最適化問題 ＊標示関数を使えば，制約つきの問題も扱える．

(

in

)

( )

m

f Ax



g x

s.t.

min

f y

( )

g x

( )

y

Ax





min s.t ( ) . f x xS ( ) min f x _S( )x

Fenchel双対問題

ただし， は以下で定義される_{共役関数(ルジャンドル変換)}

( , , )

f y

( )

g x

( )

,

L x y







 



Ax

 

y

















, , * * ( ) ( ) ( ) ( ) ( ) ( ( ) inf , sup , , sup , su ( p , ) ( ) ) x y x y y x y Ax y f y g x f y g x f y g x Ax y A x f g A

 















                             * f





*

( )

sup

_x

,

( )

f

y



y x



f x

s.t. min f y( ) g x( ) y Ax  

Fenchel 双対問題

共役関数の例： 線形関数 凸2次関数 平行移動 分離可能な和 * *

(

)

m

a

x



f

 



g A

(



)

* if otherwi 0 ( ) ) se ( y c f x c x f y        _ * 1 1 ) 2 ( 1 2 ( ) f x  x Ax  f y  x A x * * ( ) ( ) ( ) ( ) f x  g x b  f y  g y b y 1 2 1 2 * 1 2 1 1 1 * * 2 2 2 ( , ) ( ) ( ) ( , ) ( ) ( ) f x x  g x  g x  f y y  g y  g y

Fenchel 双対問題の例

Support Vector Regression

教科書によく出ているLagrange双対問題 1 1 min s.t 1 2 . 1, , ) 1 ( T t t t t t t K C T b C                





1 1 min ) ) ( ) s.t. ( ) 1 ( ( ( ) 2 0 , ( 1 1 , , ) T T t t t t t t t t t t t b K C t T                           







, | 0, 0 | t t t t t t t t                  1 2 , 1 min max 0,| | 2 n t t T x t R y R C a x y b  x   _    

第3部 概要

1. 双対問題とその応用

2. ゲージ最適化問題の双対問題

I. ラグランジュ双対問題とFenchel双対問題 II. Gauge双対問題 III. 新しいタイプの双対問題

4. まとめ

Gauge 双対問題の動機

数学的興味： Gauge関数の特性を生かした， Lagrange双対問題とは違った双対問題はあるか？ 工学的動機： 制約条件と目的関数にある定数行列を入れ替えたい． • 大規模凸最適化の代表的な解法は，実行可能集合の射影を計算するこ とが多い．

min

( )

s.t.

(

)

x

Ax

b











max , ( ) s.t. ( ) 1 b A          Gauge最適化 Lagrange双対問題

Gauge双対性

[Freund, 1987]

をgauge関数とし，次の二つの問題を考える． ただし， は凸集合で， を次式で定義する． のとき， min ( ) s.t. x C x   1 min ( ) s.t. y C y   C





1

,

1

C



y

x y



 

y

C



1 C 1 , xC yC ( )x ( )y x y, 1





 _{ } これを弱双対と考える 注意 最小化問題 anti-polar という 1 max ( ) s.t 1 . y C y   1 ( ) ( ) x y





 

Gauge双対問題

[Friedlander, Macedo, and Pong, 2014]

min

s.t.

(

)

,

( )

1

A y

b y

y





 





min

( )

s.t.

(

)

x

Ax

b











{x | (Ax b) } C     のとき 1





, ( ) b y y y y C  A   性質 • Lagrange双対の最適値を ，Gauge双対の最適値を とすると • Lagrange双対の最適解を ，Gauge双対の最適解を とすると L D _DG 1 L G D D  * y *  * * G y  D  Gauge最適化問題 Gauge双対問題

第3部 概要

1. 双対問題とその応用

2. ゲージ最適化問題の双対問題

I. ラグランジュ双対問題とFenchel双対問題 II. Gauge双対問題 III. 新しいタイプの双対問題

4. まとめ

絶対値計画問題の双対問題

[Mangasarian, 2007]

min , ,| | s.t. | | | | Ax B x c x d x b x e H K x          max , , s.t. 0 A u v c b u e v v K v H   B u d          • 凸最適化問題(線形計画問題に変換可能) • 弱双対定理が成り立つ[Mangasarian 2007] Mangasarianの双対問題

これまでの双対問題のまとめ

Lagrange双対問題 Fenchel 双対問題 Gauge 双対問題 等価 変数変換で等価 今考えている問題 特別な凸最適化問題 Gauge 最適化問題 絶対値計画 Mangasarianによる 双対問題

？

陽に表せない

一般化ゲージ最適化問題の双対問題の表現

[山中，山下，2018?] 0 ( ) max , , s.t. ( ) 0 M D b u e v A u H v c B v v u K d             • 凸最適化問題 • は，より一般的には随伴作用素とする 0 1 0 2 0 1 0 1 0 ( ) ( ) ( ) , ( ) i i y y y y                    は の極関数 ただし， , , , A B H K

双対問題

_{の例： SDP}

, ( min s.t. , , 1 1, ) ( ) i i S C X A b i X X m  _     min s.t. , ( 1, , , 0 ( ) 0 ( ) 0 ) ( 1 d , ) om i i S S S S X X C X A b i X X m X X                    1 ( ) max s. 0 , t. _{i i} 0 i S m b u v A u C v v       _ _      



1 max s.t. , m i i i b u C Au S_   



(

D

_M

)

双対問題 (S_)  S_

弱双対定理

•

凸性は仮定していない • 双対問題の実行可能解なら 定理1 [山中，山下 2018?] を一般化ゲージ最適化問題の実行可能解とし， を双対問題 の実行可能解とする． このとき (D_M )

x

( , )

u v

( )

,

,

x

,

e v

,

c x



d





b

u



dom u H A  v  c 

弱双対定理の証明

( ) , , x , , c x  d   b u  e v , ( ) , ( ) , , c x  A u H v c B u K v x b u e v           , ( ), (x) , ( ) , ( ) , , c x  A u H v c u B x v K x b u e v             , ,x , ( ) , ( ) , , c x A u H v c u B x v K x b u e v           , , , , , ( ) , ( ) , , c x c x u Ax v Hx u B x v K x b u e v           ( ) , x ( )x , u A B b v Hx K x e         0  双対問題の実行可能性 ゲージ関数の非負性 主問題，双対問題の実行可能性 ( ),y ( )z y x, , x dom , y dom           

Lagrange双対問題との関係は？

Lagrange関数： Lagrange双対問題の目的関数 ( ) ( ( , , ) , , , ) , ( ) L x u v c x d u d Ax B v e Hx K x x x            dom

( , )

inf

(0, ,

(

)

,

,

,

,

)

x

L x u

u v

L

u v

b u

e v

v



 









0 ( ) max , , s.t. ( ) 0 M D b u e v A u H v c B v v u K d             Lagrange双対よりも よい双対問題？ （双対ギャップが小さい？）

残念！！

補題1 が双対問題 の実行可能解のとき

( , )

u v

( , )

u v

b u

,

e v

,







(D_M ) 0 ( ) max , , s.t. ( ) 0 M D b u e v A u H v c B v v u K d             0 ( ) max ( , ) s.t. ( ) 0 M u v D u v A H c B u K v d v         ( ) max ( , ) s.t. 0 L D u v v   Lagrange双対のほうが よい双対問題？ （双対ギャップが小さい？）









( , , ) , , , , , , ( ) ( ) ( ) ( ) , , , , , , , L x u v c A v x d B u v A v c d B u v B A v c u v u H u K v x b e u H x u K v x b e d u K v u H x b e b u v e                                   

補題１の証明

任意の に対して， 等号は のときに成り立つ． よって，

dom

x 



0

x 

dom

( , )

in

f

(

, , )

,

,

x

L x u v

b u

e v

u v



 







( ), ( )

y

x

y x

,









双対問題の実行可能性 ゲージ関数の非負性

双対問題

はラグランジュ双対よりも悪い？？

0 ( ) max ( , ) s.t. ( ) 0 M u v D u v A H c B u K v d v         ( ) max ( , ) s.t. 0 L D u v v   (D_M ) はラグランジュ双対よりも制約条件が多い 最大値が小さくなる(かも) 双対ギャップが大きくなる(かも) よかった！！(次のスライドから) 適当な仮定のもとでは とラグランジュ双対は等価 (D_M ) (D_M )

[山中，山下 2018]の結果

補題２ _{[山中，山下 2018]} とする． 仮定１が成り立つとする． が双対問題 の実行可能解でなければ

0

v 

( , )

u v

dom

( , )

u v

in

f

_x

L x u v

(

,

, )





_{ }

 

(D_M ) 仮定１ すべての に対して は全空間で， が成り立つ i dom_i ( )x_i 0 x_i 0     • 絶対値計画は仮定１を満たす． • 標示関数は仮定１を満たさないので，SDPではこの結果が使えない • _{g x( ) }



_max{0,xi}は仮定１を満たさない．

仮定１を弱めた仮定

仮定２ すべての _{に対して，次の(I)と(II)どちらかが成り立つ．} (I) (II) が全空間で， となる が存在．

i

0, 0 , 0 i ti ti d  B  t K  t dom



_i



_i( )xˆ_i  0 xˆ_i Remark • すべての に対して(I)が成り立てば，一般化ゲージ最適化 は凸最適化になる • (II)は実質的には，「 が全空間」で十分． もし， であれば， を適当なノルムに置き換えて， にかかる係数 _{を0とすればよい．}

i

dom



_i ( ) 0 i x x



  i i  d B_i, _ji, K_ji

新しい仮定のもとでの補題

仮定２のもとで次の補題が成り立つ．

補題３ とする． 仮定２が成り立つとする． が双対問題 の実行可能解でなければ

0

v 

( , )

u v

dom

( , )

u v

in

f

_x

L x u v

(

,

, )





_{ }

 

(D_M)

補題３の証明 (記号の定義)

制約条件は この制約条件を満たしていないため，ある が存在して いま， とおくと (( ) ) ( ) ( 1, , ) i A u H v c i B u K v i di i  _{      }

j

(( ) ) ( ) j A u H v c j d j B u K v j  _{    } ( ) , ( ) j A u H v c j j dj B u K v j         ( ) j j j   _  大事な式(1)

補題３の証明 (ラグランジュ関数の表記)

ラグランジュ関数は以下のように書ける． いま， とすると となり，さらに ( ) ( , , ) , , , , , , , ) ) ) , ( ( ( L x u v c x d u b Ax B v e Hx K c A v x d B x x x u H u K v x u b v e                     , 0, (0, _j , 0, , 0) x   x  ( )x (0, , 0,_j(x_j ) ,,0 ,0)     ( , , ) _j, _{j j j}( _j) , , L x u v    x    x  u b  v e 大事な式(2)

補題３の証明(流れ)

次の三つの場合にわけ，それぞれで を示す 場合１： のとき 場合２： のとき 場合３： のとき ( , )u v



  ( ) j j

 

 _{ } ) ( 0 j j   _ ( ) (0, ) j j

 

 _{ }

場合１

：

のとき

このとき， を定義する最大化問題： より，任意の に対して となる が存在する． さらに， となる に対して となる が存在する． 実際， のとき， であるから， 正斉次性より， の存在性を示せる．





( ) sup , ( ) 1 j j xj j j xj   _   _ ( ) j j   ( ) j x 

(

)

(0, )

j j

 



_

_

( ) , ) ( )) 1 ( _j , ( _j j j j x j x   _{ }     _

0





) ( 0 j j

 

 _{ }



( ) , ) ( )) 1 ( _j , ( _j j j j x j x   _{ }     _ ( ) j x  , ( ) 0  _j x_j  x_j()  0 ( ) j x 



場合１

：

_{のとき(続き)}

いま， とおく． さらに， とすると， よって， ( )t (0, , 0, _j( ),0, , 0), x   tx   t R









( ( , , ) , ) ( ( ) , , ( ) ( ) ) ) ( ) ) ( ) ( , , ( , , , , 2 j j j j j j j j j j j j j j j j x b e b L u v u v u v u v e b t t t t t x x t u v e e b x                                          

lim

(

( ), ,

)

t

L

x t

u v

 

(

)

(0, )

j j

 



_

_

大事な式(2) 大事な式(１)



( ) , (



1 min 0 2 j j j j j)  _   _    _ ( ) , ( ) j j j xj   _{ }   ( ( )) 1 j xj    大事な式(１) ( 2 ) j j j       

場合２

：

のとき

より となる点列 が存在する． いま， とすると， よって， 0

(

_j

)

j

 

 





( ) sup , ( ) 1 j j xj j j xj   _   _ ( k) 1, k, j xj xj j     

{

x

k_j

}



dom



, 0, , 0) (0, , 0, k k j x   x  ( k, , ) _j, k_{j j j}( k_j ) , , L x u v    x    x  u b  v e ( im , , ) l k k L x u v   大事な式(2)

場合３

：

のとき

より

(a)

が仮定２の(I)を満たすとき

よって矛盾．この場合は存在しない．

)

(

0

j j

 



_

( ) j j j   _ 

0





_j 大事な式(１)

j

(

)

0

j j j j tj t t t j t t

d

B

v

d

B u

K v

u

K





















0, 0 0 0 , , j tj tj t d B K v t t t       

場合３

：

のとき

(b) が仮定2 の (II) を満たすとき (b-1) のとき となる が存在する． となり矛盾．このような場合は存在しない．

)

(

0

j j

 



_

0





_j

0

j





( ) 1 j j      0





( ) sup , ( ) 1 , 0 j j xj j j xj j j   _   _{ }    _

j

場合３

：

のとき

(b) が仮定2 の (II) を満たすとき (b-2) のとき 仮定より となる が存在する． とすると，

よって，



( , )

u v

 

)

(

0

j j

 



_

0





_j 大事な式(2)

0

j





ˆ ( ) 0 j xj



 xˆ_j ˆ( ) (0, , 0, ˆ_j,0, ,0), x t   tx  t R ( ˆ( ), , ) , ˆ ( ˆ ) , ( ) , , , j j j j j j j j x t tx x b e x b t t L u v u v u v e             

j

Lagrange双対問題との等価性

•

凸性は仮定していない 定理２ 仮定２を満たすとする． さらに，ラグランジュ双対問題が最適解をもつとする． このとき，（ ）とラグランジュ双対問題の最適値 および最適解が一致する． M D

定理の証明

max

( , )

s.t

0

u v

v





m ( ax ( , ) ) s.t 0 A u H B u v v c u K v d v          max s.t 0 , , ( ) b u e v A u H v c B u K v d v          補題３ 補題1 Lagrange双対 (D_M)

双対問題の双対問題

max , , s.t. ( ) 0 b u e v A u H v d B v v u K d              min , , ( ) s.t. ( ) ( ) c x d x x b x Ax B Hx K e             min , , s.t. ( ) Ax B Hx z z c x d b e x Kz z            0 B  0 d  0 , ij K  i j min , , ( ) s.t. ( ) ( ) c x d x x b x Ax B Hx K e             主問題 双対問題 双対問題の双対問題 _凸な場合

双対問題の関係

Lagrange双対問題 Fenchel 双対問題 Gauge 双対問題 等価 変数変換で等価 一般化ゲージ最適化問題問題 凸最適化問題 Gauge 最適化問題 Mangasarianによる 双対問題の一般化

等価

非凸な場合の残念な結果

０－１変数をもつ問題は単なる連続緩和．

, | ( min s.t. 1 ( 1), | 1 , ) 2 1, i i i e y c x n x H x y i       , ( | | 1 min s.t. 1 ( 1), , ) 2 1, i i i e y c x n x H x y i       双対の双対 ＊0-1制約以外が凸な場合でも同様

まとめ

• 1次式とノルム(ゲージ関数)で構成された最適化問題を 紹介した • それらの問題は，双対ノルム(極関数)が陽に表せるとき， 双対問題が陽に書き下せる． • 適当な仮定(仮定２)のもとで，その双対問題はラグランジュ 双対問題と等価になる． 今後について • 双対性を利用したモデル化や解法の開発．

ノルムと一次式で構成された最適化問題とその双対問題

参考文献とその他の話題

京都大学大学院情報学研究科 山下信雄

参考文献

凸解析

_{(Convex Analysis)}

[1] R.T. Rockafellar, Convex Analysis,

Princeton University Press, Princeton, 1970.

*共役関数と双対性．凸集合の関係など，ゲージ関数の基本的な性質

[2] 福島雅夫，非線形最適化の基礎，朝倉書店, 2001.

参考文献

絶対値計画問題

_{(Absolute Value Programming)}

[3] O. L. Mangasarian, Absolute value programming,

Computational Optimization and Applications, Vol. 36, pp. 43-53, 2007.

*絶対値計画問題の定義と双対問題．弱双対性の証明． [4] O. L. Mangasarian,

Linear complementarity as absolute value equation solution, Optimization Letters, Vol. 8, pp. 1529-1534, 2014.

*線形相補性問題と絶対値方程式の関係．

参考文献

Gauge optimization problem and Gauge duality

.

[5] M. Freund, Dual gauge programs, with applications to quadratic programming and the minimum-norm problem,

Mathematical Programming, Vol. 38, pp. 47-67, 1987.

* Gauge duality の元論文

[6] M. P. Friedlander, I. Macedo, and T. K. Pong, Gauge optimization and duality, SIAM Journal on Optimization, Vol. 24, pp. 1999-2022, 2014.

*Gauge最適化問題の定義とその双対性．Gauge関数の諸性質

[7] A. Y. Aravkin, J. V. Burke, D. Drusvyatskiy, M. P. Friedlander, and K. MacPhee, Foundations of gauge and perspective duality, arXiv:1702.08649, 2017.

*非負の凸関数のGauge関数への変換とその諸性質． gauge dualの解と主問題の解の関係

参考文献

一般化ゲージ最適化問題とその双対性

[8] S. Yamanaka and N. Yamashita, Duality of nonconvex optimization with positively homogeneous functions,

to appear in Computational Optimization and Applications.

＊一般化ゲージ最適化問題とその双対問題．Lagrange双対との等価性 凸性は仮定せず，ゲージ関数よりも一般的な正斉次関数で議論． ただし，正斉次関数の実効定義域は全空間としている

[9] S. Yamanaka and N. Yamashita, Duality of optimization problems with gauge functions, arXiv:1712.04690, 2017.

* 未完成．論文[7]の内容を一般化ゲージ最適化問題に

[10] 加茂寛也，山下信雄，正斉次最適化問題の一般化とその双対問題， 2018年秋季研究発表会，日本オペレーションズリサーチ学会，2018．

その他の話題

• 数学的な話

• さらなる一般化の話

ゲージ関数の一般化  非負性，正斉次性がない一般の凸関数  非凸な関数 問題の一般化  不等式制約から錐制約

数学的な話題

[Rockafellar, 1970]

ゲージ関数の定義： _{を0を含む凸集合とする．} 極集合(polar set)の定義： が錐のとき 極関数：





inf ( ) 0 f x    x C



, 1



C  y x y   x C C

C

C 



y x y,   0 x C







inf

0

,

)

)

(

x y

f

(

f



y











x



x

は の recession function

より一般的な凸関数への拡張

Gauge関数： 正斉次かつ非負な凸関数 • 非負でない凸関数 ⇒ 非負な凸関数 ＋ _1次関数 として • 非負な凸関数 ⇒ 正斉次な凸関数 0 0 0 0 ₀ 0 if 0 ˆ ( , ) _{if 0, 0} 0 if 0 o ( therwia ) se x x x x f x f x x _f x x x x             _{  }  _{ }     ( ) ( ( ) f x f y) , ( ) , x f x     x  y  f y    y , dom ( ) y  f  f y f  f 非負な凸関数 _1次関数