本講演の概要

(1)

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

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

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

2018

年

7

月

25

日

(本資料は7月30日に改訂)

(2)

本講演の概要

第 1 部一般化ゲージ最適化問題とその応用問題第 2 部ゲージ関数とその諸性質

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

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

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

(3)

用語

• 凸関数 (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  

(4)

第 1 部概要

1. 今回考える問題

•

ノルムとその一般化した関数

(

ゲージ関数

)

• 1

次式とゲージ関数で構成された最適化問題

2. 応用問題

ゲージ最適化問題

•

L1-L2

最適化問題

• 半正定値計画問題

2

次錐計画問題絶対値計画問題

•

0-1

整数計画問題

• 線形な均衡制約つき最適化問題

(MPEC)

(5)

今回考える問題の準備：

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

定義

以下の性質を満たす関数

をゲージ関数

(gauge function)

という

(i)

非負の関数

(ii)

凸関数

(iii)

正斉次

(Positively homogeneous)

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

: V R { }

   

( ) tx t ( ) x t 0

    

(6)

ノルムとゲージ関数

norm:

標準，基準

…..

gauge:

基準，規格，標準寸法

….

注意：今回の話はゲージ理論とは関係ないノルムはゲージ関数

非負性：

正斉次性：

凸性：に対して

0 x 

( 0) tx  t x t 

(1 )

(1 ) (1 )

x y x y x y

             

[0,1]

 

三角不等式

(7)

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

ベクトルのノルム

• p

ノルム

•

無限大ノルム

• 1

ノルム

⇒

正則化やスパース化によく使われる行列のノルム

• Frobenius

ノルム

• Nuclear

ノルム

⇒ Nuclear

ノルムは

rank(A)

の凸緩和として使われる

| _i |^p

p

p x

x 



max | _i | x _  i x

1

|

_i

|

x   x

( ) A A



を行列の特異値を並べたベクトルとする

( ) 2

A F   A

* ( ) 1

A 



A

(8)

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

：

の成分を，絶対値の大きい順に並べたときの番目

利用例

CVaRノルム

(largest-k

ノルム

)

ある線形計画問題の最適値として表せるため，

最適化モデルで使いやすい

応用：金融の

CVaR, ν-SVM

( )i

x _x _ _R

ⁿ

i

(1)

| |

(2)

|

( )

| x  x   | x

_n

|

1

(1) ( ) 1

1 1

, ( ) i

n

i

i i

x x x x x

 



 







CVaR , ( )

1

| |

n n

i i

x x







 

(9)

ノルムでないゲージ関数

• 0

との

Max

関数

₍

演習問題

)

＊損失関数やペナルティ関数に使われる

•

凸錐の標示関数

凸関数の標示関数

⇒

非負の凸関数錐の標示関数

⇒

正斉次関数

 

1

( ) max 0,

n

i i

x x





 

C ^

_C

^{( )} ^x

(10)

今回考える問題の準備

•

変数を個に分割する．

•

ベクトル値ゲージ関数：

ただしはゲージ関数

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 ,  , )

(11)

一般化ゲージ最適化問題

ただし，は適当な大きさの

ベクトルや行列

(

線形写像

)

が非負ベクトル，の各成分が０以下

凸最適化問題

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

(12)

ゲージ最適化問題 (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

A I x b

y

x y

y x x

y

x

y









 



     

      

     

   

    

   

   

 

   

   



(13)

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

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

min

1

s.t.

x

Ax   b 

(14)

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

(

ちょっとトリッキーですが．．

)

半正定値行列の集合の標示関数：

双対問題の実行可能解：

が実行可能解であれば，

よって， ⇒ (実行可能集合上で)Gauge関数

( )

S

X



_

y

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

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 

(15)

SDP ⇒ ゲージ最適化問題

1

,

( 1, min

, , )

s.t.

m i

i i

i

C X b i

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



 

 

  

 

 



(16)

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



_

  



一次式が使えるので簡単

(17)

2 次錐計画問題

(Second-order cone programming problem)

ただし，

は

p

次元の

2

次錐

:

min s.t.

, c x

Ax

K b x





1 2

1

n

,

i

n

K

n

K

K K n n



   

 

K

p



^p ¹ ²² ³² ²



p p

K  x  R x  x  x   x

2 3 1

p

x

x x

x

  

  

  

 

一次式とノルム

(18)

凸 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 2

4 Cx   (1 b x  c )   1 b x  c

2

1 1

2

r

b x c b x c

Cx

K

_

   

   

 



 

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

一次式とノルムで表せる

(19)

絶対値計画問題

[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

 

 

  

 

 

(20)

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

min s.t.

,

(

{0,1} 1, , )

i

c x Hx

x i

e

 n



 

{0,1} | 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 



   

(21)

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

(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

y

I I M y q

I M z I z q

  

      

   

       

       

(22)

LCP AVE

各成分ごとに考えればよい．

のとき，

よって，

のときのとき

0, 0,

( ) 0

Mz q z M

z

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

Mz q z M I z q

Mz q z M I z q M I z q

    

        



  

(23)

LCP 制約つき最適化問題

^（線形な

MPEC

）

この問題は一般化ゲージ最適化問題として書ける．

（演習問題）

1 2

min s.t.

0, 0

0 ,

( )

c x c y Ax

y My Nx q

y My Nx q b



 









(24)

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

(25)

第 2 部の概要

1.

ゲージ関数

2.

共役関数

3.

ゲージ関数の極関数

4.

ゲージ関数の共役関数

(26)

ゲージ関数（再掲）

定義

以下の性質を満たす関数

をゲージ関数

(gauge function)

という

(i)

非負の関数

(ii)

凸関数

(iii)

正斉次

(Positively homogeneous)

: V R { }

   

( ) tx t ( ) x t 0

    

(27)

共役関数とその諸性質

(

室田先生の予習資料

)

凸関数の共役関数

(

ルジャンドル変換

)

共役関数の諸性質

:

•

は凸関数

f

 

*

( ) sup

_x

, ( )

f y  y x  f x

** * *

( )

f  f  f

*

(

( ) y ) ,

f x  f  x y

^Fenchel^{双対性で重要}^双対の

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

f

* ^Fenchel^双対の

凸性で重要

(28)

ゲージ関数の極関数

ゲージ関数の極関数 (polar function)

がノルムのとき，は双対ノルム

参考：共役関数 f

 

( ) sup x , ( ) 1

f

^

y  y f x 

 

*

( ) sup

_x

, ( )

f y  y x  f x

f f

^

(29)

双対ノルムの例

• L1

ノルム無限大ノルム

• p

ノルム

• CVaR

ノルム

x

1 x _

p i

p p

x 



x ^x ^q ^ただし ¹_p ^{ }¹_q ¹

CVaR ,

x

_ ¹

CVaR , max x ,

n n x

x _





 

  

 

 

(30)

極関数の例

• 0

との

Max

関数

•

錐の標示関数極錐の標示関数ただし

C

( ) x



C

^

,

{ | 0 }

C

^

 y x y    x C

C

( ) x



 1

max{0

( ) , }

m

i i

g x x



  ^max ^if ⁰

ot ( )

herwise

i i

y

g y y







  

 

(31)

極関数の諸性質

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

•

• • は凸関数

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

•

• • はゲージ関数 ( )

f

^

 f

^{ }

 f

** * *

( )

f  f  f

*

(

( ) y ) ,

f x  f  x y

( ) , dom , d

( ) y x y x f y o m f

f x  f

^

    

^

f

^

f

*

Gauge双対の双対性で重要 Gauge双対のGauge双対を

考える上で重要

Gauge双対の凸性で重要

(32)

「極関数はゲージ関数」の証明

非負性：より正斉次性：

凸性：

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

   

 



 





    

   













 

(33)

の証明

(i)

^のとき，

そうでないとするとよって，

より

これはに矛盾

(

( ) y ) ,

f x f

^

 x y

( ) 0

f x  ^{x y} ^,    ⁰ ^y ^d ^om ^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

^

(34)

の証明 ( 続き )

(ii)

^のとき，

とすると

よって，

(

( ) y ) ,

f x f

^

 x y

( ) 0 f x 

 

sup , ( ) 1

( )

1 ,

( ) , f y

x

x y f x y

x z f y









( ) 1 ( ) 1

( ) ( )

f f x f x

f x x

z f

 

    

 

z ( )x

 f x

(35)

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

をゲージ関数とする．

を錐とする．

ただし

f

* if ( ) 1

o 0

( ) t

herwise y

f y f

 

  



 

C

*

C C C

  



  

 ^, ⁰ 

C

^

 y x y    x C

(36)

第 3 部双対問題

(37)

第 3 部概要

1. 双対問題とその応用

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

I.

ラグランジュ双対問題と

Fenchel

双対問題

II. Gauge

双対問題

III.

新しいタイプの双対問題

4. まとめ

(38)

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

( )

s.t. ( ) 0, 1, ,

( ) 0, 1

m n

, i

,

i j

f x

h x i m

g x j r

x X

  

  



以下では

実行可能集合



ⁱ

^{( )} ^x ⁰ ⁽ ^1, ^, ^{m g} ^),

^j

^{( )} ⁰ ⁽ ¹ ^, ^, ⁾ 

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

 ^F ^, 

S  x x  x  X

(39)

双対問題とは

元の問題

(

主問題

)

を鏡で映したようなもの．

主問題双対問題

最小化 ⇔ 最大化

決定変数の数 ⇔ 制約条件の数制約条件の数 ⇔ 決定変数の数

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

  

  



双対問題主問題

(40)

双対問題の望ましい性質

• (

弱

)

双対性：それぞれの実行可能解に対して

• (

適当な仮定の下

)

双対問題の双対問題は主問題になる．

,

( ) ( )

f x    

min s.t.

0 x

i

Ax b x







^max ₁

s.t. 1

1 ,

b

A



  

  

  

 

, , ( ) x  

max

s.t. 0



i

 



例

(41)

ラグランジュの双対問題

ラグランジュ関数

:

標示関数：

1 1

, ) (

( , ) ( ) ( )

m r

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

j

x x

x

_ _

h g



_ _

 

 

 

  

 

  

(42)

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

主問題の目的関数

min ( ( )

s

) .t.

f F

x

x x

X







0

1 1

0

1 1

0

,

( ) ( ) sup ( ) ( )

( ( )

sup ) ( ) ( )

( ,

s p u , )

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

 

  

 

 

 

 

 

 

 

    

 





 

 

 

 

 

(43)

ラグランジュ双対問題

[ 主問題 ]

[ 双対問題 ]

0 su ,

m in x X _ p _ _ R

m

_ _ L x ( , , )  

max ( , , )

s. t

i

0 nf

,

. ^m

x X L x R

 



 

(44)

弱双対定理

双対問題の目的関数

(

必ず凹関数

)

：

⇒

下界値の計算に利用できる

, ) )

( inf

_{x X}

L x ( , , w   

_

 

弱双対定理

( ) w ( , ) x , R

^m

, 0

f x      S    

(45)

強双対定理

:

凸関数

：１次関数適当な制約想定が成り立つ．

主問題に最適解が存在する．

↓

主問題と双対問題の最適値は一致する．

, )

, ( 1,

, ) ( 1,

j i

r

h m

f g j i









(46)

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

ラグランジュ双対問題の最適解には経済的な意味がある．

最適値関数

ラグランジュ双対問題の最適解をとする．

を制約条件の潜在価格

(

シャドウプライス

)

という

| ( 1,

( ) u min{ ( ) f x h

_i

( ) x u

_i

i , m ) , g x

_j

( ) 0( j 1 , , r )}

       

* *

(  ,  )

(0) * i

u i



 



*



i

^{h x}

ⁱ

^{( )} ^ ⁰

(47)

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

[

解法

]

• ラグランジュ緩和

(

応用例：オンライン広告

,

火力発電計画，

etc)

⇒ 並列化，逐次計算を可能にする．

• サポートベクターマシン

•

etc

[

解析

]

• 乗数法

(

拡張ラグランジュ法

)

⇔ 双対問題では近接点法

＊

Dual Augmented Lagrangian method [Tomioka,etc, 2011]

はこの逆

•

Alternating Direction Method of Multipliers (ADMM)

⇔ 双対問題では

Douglas-Rachford Splitting

(

近接勾配法みたいなもの

)

(48)

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

データが不確実なとき，最悪の場合を考えての最適化

半無限計画

(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





ロバスト最適化

不確実なデータ

不確実性集合

(49)

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

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

x

u U

g x u x

    







   

弱双対

min s.t.

( )

; ) 0 (

f x w x 





 

強双対性が成り立てば等価

(50)

第 3 部概要

1. 双対問題とその応用

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

I. Fenchel

双対問題

II. Gauge

双対問題

III. 4. まとめ

(51)

一般化ゲージ最適化問題

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

min , , ( )

s.t. ( )

( )

c x d x

x b x

Ax B

Hx K e

     

 



 



, , , , , , , c b d e A B H K

一般化ゲージ最適化問題

絶対値計画

(52)

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

min , , ( )

s.t. ( )

( ) dom

Ax B

c x d x

x x x

e K

b Hx



    









 



一般化ゲージ最適化問題は，実効定義域外では，

定義が不明瞭になる場合がある．

そこで以下では，制約条件に実効定義域を加えた次の問題を考える．

(53)

ラグランジュ双対問題

ラグランジュ関数：

目的関数：

•

陽に表しにくい．制約がないときはどうする？

→ Fenchel

双対問題

•

他のタイプはないの？

→ Gauge

双対問題

( ) (

( , , ) , ,

, ) , ( )

L x u v c x d

u b Ax B v e Hx K

x

x x



 

      

( , ) i

dom

nf ( , , )

x

L u v

v x

 u

 



(54)

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

(55)

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

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





(56)

Fenchel 双対問題

共役関数の例：線形関数

凸2次関数平行移動分離可能な和

* *

( )

m a x  f    g A (  )

* if

otherwi

( ) ) 0

( y cse

f x c x f y 

  



 

* 1

) 1

( 21

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

(57)

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

b K

C t T

        

 

 

     





  

 



,

|

0, 0

|

t t t t t

t t t

    

  

 

 

  

 

1

2 ,

min max 0,| | 1

2

n t t

T

x R y R Ct a x y b  x

  

   



(58)

第 3 部概要

1. 双対問題とその応用

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

I. Fenchel

双対問題

II. Gauge

双対問題

III. 4. まとめ

(59)

Gauge 双対問題の動機

数学的興味：

Gauge

関数の特性を生かした，

Lagrange

双対問題とは違った双対問題はあるか？

工学的動機：

制約条件と目的関数にある定数行列を入れ替えたい．

• 大規模凸最適化の代表的な解法は，実行可能集合の射影を計算することが多い．

本講演の概要

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

2018

7

25