双対問題

Transcription

1 一次式とノルムで構成された最適化問題とその双対問題 第一部ゲージ最適化問題とその応用問題 2018 年 7 月 25 日 ( 本資料は 7 月 30 日に改訂 ) 京都大学大学院情報学研究科 山下信雄

2 本講演の概要 第 1 部一般化ゲージ最適化問題とその応用問題 第 2 部ゲージ関数とその諸性質 第 3 部一般化ゲージ最適化問題の双対問題 I. ラグランジュ双対問題とFenchel 双対問題 II. Gauge 双対問題 III. 新しいタイプの双対問題

3 用語 凸関数 (convex function) f ( x (1 ) y)) f ( x) (1 ) f ( y) 標示関数 (indicator function) 0 if x S S ( x) otherwise 実効定義域 (effective domain) dom f x V f ( x)

4 第 1 部概要 1. 今回考える問題 ノルムとその一般化した関数 ( ゲージ関数 ) 1 次式とゲージ関数で構成された最適化問題 2. 応用問題ゲージ最適化問題 L1-L2 最適化問題 半正定値計画問題 2 次錐計画問題絶対値計画問題 0-1 整数計画問題 線形な均衡制約つき最適化問題 (MPEC)

5 今回考える問題の準備 : ゲージ関数 ( ノルムの一般化 ) 定義 以下の性質を満たす関数 をゲージ関数 (gauge function) という (i) 非負の関数 (ii) 凸関数 : V R{ } (iii) 正斉次 (Positively homogeneous) ( tx) t( x) t 0 例 : ノルムは上記の条件を満たす

6 ノルムとゲージ関数 norm: 標準, 基準.. gauge: 基準, 規格, 標準寸法. 注意 : 今回の話はゲージ理論とは関係ない ノルムはゲージ関数非負性 : x 0 正斉次性 : 凸性 : tx t x ( t 0) [0,1] に対して x (1 ) y x (1 ) y x (1 ) y 三角不等式

7 ノルムの例 ( 有名なもの ) ベクトルのノルム pノルム 無限大ノルム 1ノルム p x x p p i x max xi i x x 1 i 正則化やスパース化によく使われる 行列のノルム Frobenius ノルム Nuclear ノルム ( A) を行列 Aの特異値を並べたベクトルとする A A F ( A) ( A) 2 * 1 Nuclear ノルムは rank(a) の凸緩和として使われる

8 ノルムの例 ( 有名でないもの?) x() i : n の成分を, 絶対値の大きい順に並べたときの番目 利用例 x R CVaR ノルム (largest-k ノルム ) x ある線形計画問題の最適値として表せるため, 最適化モデルで使いやすい x x x (1) (2) ( n) 応用 : 金融の CVaR, ν-svm 1 x x x, x x CVaR, (1) ( i) 1 i1 i1 nn i1 x () i n () i i

9 ノルムでないゲージ関数 0 との Max 関数 ( 演習問題 ) n ( x) max0, x i1 i * 損失関数やペナルティ関数に使われる 凸錐 C の標示関数 ( x C ) 凸関数の標示関数 非負の凸関数錐の標示関数 正斉次関数

10 今回考える問題の準備 変数を 個に分割する. x ( x, x,, x ) V V V ベクトル値ゲージ関数 : ただし x V ( x1) ( x ) 2 2 ( x) ( x ) : V ( i 1,, ) i i R : V ( R{ }) dom xxdom ( 1,, ) i i i はゲージ関数

11 一般化ゲージ最適化問題 min c, x d, ( x) s.t. Ax B( x) b Hx K( x) e 一般化ゲージ最適化問題特別な凸最適化問題 Gauge 最適化問題 絶対値計画 ただし, c, b, d, e, A, B, H, K ベクトルや行列 ( 線形写像 ) は適当な大きさの B 0, d が非負ベクトル, K 凸最適化問題 の各成分が 0 以下

12 ゲージ最適化問題 (Gauge Optimization) [Freund, 1987], [Friedlander, Macedo, and Pong, 2014], etc min ( x) s.t. ( Ax b) とはゲージ関数 A は線形写像, は定数ベクトル は非負の定数 b 凸最適化問題である. x 1 ( x) min 0,, y 0 ( y) s.t. x ( x) A I b y ( y) x ( x) y ( y)

13 ゲージ最適化の応用例 1: L1-L2 最適化 基底追跡ノイズ除去 (Basic pursuit denoising) min s.t. x 1 Ax b

14 ゲージ最適化の応用例 2: 半正定値計画問題 ( ちょっとトリッキーですが..) min s.t. CX, A, X b ( i 1,, m) i X S i m max biy i1 m s.t. C i i1 y i A i S S C, X trace( C X ) は半正定値対称行列の集合 半正定値行列の集合の標示関数 : 双対問題の実行可能解 : y S ( X ) C C y A i i X が実行可能解であれば, n C, X C y A, X C, X b y 0 i i i1 i1 n i i よって, ( X) C, X ( X ) 0 S ( 実行可能集合上で )Gauge 関数

15 SDP ゲージ最適化問題 min s.t. CX, A, X b ( i 1,, m) i X S i min s.t. C, X m i1 A, X b ( i 1,, m) i X S i b y i i min s.t. C, X Ai, X bi ( i 1,, m) X S min s.t. C, X S ( X ) A, X b ( i 1,, m) i i min ( X ) s.t., X A i b i ( i 1,, m) min ( X ) s.t. ( AX b) 0 AX A, X A 1 m, X, ( y) y

16 SDP 一般化ゲージ最適化問題 min s.t. CX, A, X b ( i 1,, m) X i S i 一次式が使えるので簡単 min CX, s.t. Ai, X bi ( i 1,, m) ( X ) 1 S

17 2 次錐計画問題 (Second-order cone programming problem) min s.t. cx, Ax x K b ただし, K p K K K K, n n 1 2 は p 次元の 2 次錐 : n n n i1 p K p x R x1 x2 x3 x p i x 1 x x x 2 3 p 一次式とノルム

18 凸 2 次不等式制約 2 次錐制約 x Ax b x c 0 ただし A は半正定値対称 Cx 2 b x c 0 A C C, C r n R Cx (1 b x c) ( 1b x c) Cx (1 b x c) 1 b x c 1 1 b x b x 2Cx c c Kr 2 凸 2 次関数とノルムで表された目的関数や凸 2 次不等式制約は一次式とノルムで表せる

19 絶対値計画問題 [Mangasarian, 2007] min c, x d, x s.t. Ax B x b Hx K x e ただし, x x x x 1 2 n 非凸な問題 モデル化能力は高いがあまり研究されていない.

20 絶対値計画問題の応用例 :0-1 最適化問題 min s.t. cx, Hx e x i {0,1} ( i 1,, n) 1 xi {0,1} yi 1, xi ( yi 1) 2 min s.t. c, x Hx e 1 xi ( yi 1), yi 1 ( i 1,, n ) 2

21 絶対値方程式と線形相補性問題 (Absolute Value Equations and Linear Complementarity Problem) [Mangasarian, 2014] 絶対値方程式 : Ax B x b 線形相補性問題 z 0, Mz q 0, z ( Mz q) 0 ( M I ) z q ( M I ) z q y ( M I ) z q ( M I ) z q y I I M y 0 0 y q 0 I M z I 0 z q

22 LCP z 0, Mz q 0, z ( Mz q) 0 AVE ( M I ) z q ( M I ) z q 各成分ごとに考えればよい. (( M I ) z q) i 0 のとき, zi 0, ( Mz q) i 0 (( M I ) z q) i 0 のとき,( Mz q) i 0, zi 0 よって, ( Mz q) 0, z 0, ( Mz q) z 0 ( i 1,, m) i i i i ( Mz q) 0, z 0 i i のとき 0 ( Mz q) (( M I ) z q) (( M I ) z q) ( M I ) z q i i i ( Mz q) i 0, zi 0 のとき 0 ( Mz q) z (( M I ) z q) i i i ( Mz q) ( z ) (( M I ) z q) ( M I ) z q i i i

23 LCP 制約つき最適化問題 ( 線形な MPEC) min s.t. c x c y 1 2 Ax b y 0, My Nx q 0, y ( My Nx q) 0 この問題は一般化ゲージ最適化問題として書ける. ( 演習問題 )

24 一次式とノルムで構成された最適化問題とその双対問題 第 2 部ゲージ関数とその性質 京都大学大学院情報学研究科 山下信雄

25 第 2 部の概要 1. ゲージ関数 2. 共役関数 3. ゲージ関数の極関数 4. ゲージ関数の共役関数

26 ゲージ関数 ( 再掲 ) 定義以下の性質を満たす関数 をゲージ関数 (gauge function) という (i) 非負の関数 (ii) 凸関数 : V R{ } (iii) 正斉次 (Positively homogeneous) ( tx) t( x) t 0

27 共役関数とその諸性質 ( 室田先生の予習資料 ) 凸関数 f の共役関数 ( ルジャンドル変換 ) f * ( y) sup x y, x f ( x) 共役関数の諸性質 : ** * * f ( f ) f f ( x) f * ( y) xy, f * は凸関数 Fenchel 双対の Fenchel 双対を考える上で重要 Fenchel 双対の凸性で重要 Fenchel 双対の双対性で重要

28 ゲージ関数の極関数 ゲージ関数 f の極関数 (polar function) f ( y) sup x, y f( x) 1 f がノルムのとき, f は双対ノルム 参考 : 共役関数 f * ( y) sup x y, x f ( x)

29 双対ノルムの例 L1ノルム pノルム x p p x 1 x i p 無限大ノルム x 1 1 x ただし 1 q p q CVaR ノルム x CVaR, x x n n 1 max, CVaR, x

30 極関数の例 0 との Max 関数 m g( x) max{0, xi} i1 g ( y) max yi if y 0 i otherwise 錐 C の標示関数極錐 C の標示関数ただし ( x ) C C ( x) { y x, y 0 x C} C

31 極関数の諸性質 共役関数の諸性質 ( 再掲 ) ** * * f ( f ) f f ( x) f * ( y) * f は凸関数 xy, ゲージ関数の極関数の諸性質 f ( f ) f f ( x) f ( y) x, y x dom f, y dom f f はゲージ関数 Gauge 双対の凸性で重要 Gauge 双対の Gauge 双対を考える上で重要 Gauge 双対の双対性で重要

32 極関数 f はゲージ関数 の証明 非負性 : f (0) 0 より f ( y) sup x, y f ( x) 1 0 x 正斉次性 : 凸性 : f ( ty) sup x, ty f ( x) 1 t sup x, y f ( x) 1 tf ( y) x x, xˆ f ( y (1 ) z) sup x, y (1 ) z f ( x) 1 x x sup x, y xˆ,(1 ) z f ( x) 1, f( xˆ ) 1, x xˆ x, y f ( x) up xˆ,(1 ) z f( xˆ ) 1 sup 1 s x f ( y) ( 1 ) f ( z) xˆ

33 f ( x) f ( y) xy, (i) f( x) 0 のとき, の証明 x, y 0 y dom f そうでないとすると xy, 0 よって, x, y x, y as f ( x) f( x) 0 1 より f ( y) sup x, y f ( x) 1 これは ydom f に矛盾

34 f ( x) f ( y) xy, の証明 ( 続き ) (ii) f( x) 0 のとき, z x f( x) よって, f とすると x 1 f ( z) f f ( x) 1 f ( x) f ( x) ( y) sup x, y f ( x) 1 z, y 1 f ( x) x, y

35 ゲージ関数の共役関数 ( 演習問題 ) f をゲージ関数とする. C f を錐とする. 0 if f ( y) 1 * ( y) otherwise * C C C ただし C y x, y 0 xc

36 一次式とノルムで構成された最適化問題とその双対問題 第 3 部双対問題 京都大学大学院情報学研究科 山下信雄

37 第 3 部概要 1. 双対問題とその応用 2. ゲージ最適化問題の双対問題 I. ラグランジュ双対問題とFenchel 双対問題 II. Gauge 双対問題 III. 新しいタイプの双対問題 4. まとめ

38 数理最適化問題 ( 主問題 ) mn i f( x) s.t. h ( x) 0, i 1,, m i g ( x) 0, 1,, r x X 以下では F x h ( x) 0 ( i 1,, m), g ( x) 0 ( 1,, r) 実行可能集合 i S x x F, x X

39 双対問題とは 双対問題 max (, ) s.t. m R, 0 R r 主問題 mn i f( x) s.t. h ( x) 0, i 1,, m i g ( x) 0, 1,, r x X 元の問題 ( 主問題 ) を鏡で映したようなもの. 主問題 双対問題 最小化 最大化 決定変数の数 制約条件の数 制約条件の数 決定変数の数

40 双対問題の望ましい性質 ( 弱 ) 双対性 : それぞれの実行可能解 f( x) (, ) x,(, ) に対して ( 適当な仮定の下 ) 双対問題の双対問題は主問題になる. 例 min s.t. x i Ax x 0 b max s.t. b, 1 1 A 1 max i s.t. 0

41 ラグランジュの双対問題 ラグランジュ関数 : 標示関数 : m L( x,, ) f ( x) h ( x) g ( x) i i i1 1 r ( x) F 0 if x F { x hi( x) 0, g ( x) 0} otherwise m r F ( x) sup m ( ) ( ) R, 0 ihi x g x i1 1

42 主問題 ( 元の問題 ) の min-max 表現 min f ( x) ( x) s.t. x 主問題の目的関数 X, 0 F m r f ( x) F ( x) f ( x) sup m ( ) ( ) R, 0 ihi x g x i1 1 m r sup m f( x) ( ) ( ), 0 ihi x R g x i1 1 sp u L( x,, ) R m

43 ラグランジュ双対問題 [ 主問題 ] m in p (,, ) su Lx xx m R, 0 [ 双対問題 ] max inf (,, ) s. t. xx Lx R m, 0

44 弱双対定理 双対問題の目的関数 ( 必ず凹関数 ): w (, ) inf (,, ) Lx xx 弱双対定理 m f( x) w(, ) x S, R, 0 下界値の計算に利用できる

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

46 双対問題の利用 1: 感度解析 ラグランジュ双対問題の最適解には経済的な意味がある. 最適値関数 ( u) min{ f ( x) h ( x) u ( i 1,, m), g ( x) 0( 1,, r)} i i * * ラグランジュ双対問題の最適解を (, ) とする. (0) * i u i を制約条件 hi ( x) 0 * i の潜在価格 ( シャドウプライス ) という

47 双対問題の利用 2: 解法の開発, 解析 [ 解法 ] ラグランジュ緩和 ( 応用例 : オンライン広告, 火力発電計画,etc) 並列化, 逐次計算を可能にする. サポートベクターマシン etc [ 解析 ] 乗数法 ( 拡張ラグランジュ法 ) 双対問題では近接点法 *Dual Augmented Lagrangian method [Tomioka,etc, 2011] はこの逆 Alternating Direction Method of Multipliers (ADMM) 双対問題ではDouglas-Rachford Splitting ( 近接勾配法みたいなもの )

48 双対問題の利用 3: ロバスト最適化 データが不確実なとき, 最悪の場合を考えての最適化 ロバスト最適化 min s.t. f( x) g( x; u) 0 u U 不確実なデータ 不確実性集合 min s.t. f( x) max g( x; u) 0 uu 半無限計画 (semi-infinite programing) か, 制約条件中に最適化問題が含まれる問題になる.

49 双対問題の利用 3: ロバスト最適化 制約条件中の問題 max s.t. g( x; u) u U ロバスト最適化 min s.t. f( x) max g( x; u) 0 uu 双対問題 min ( x; ) s.t. min s.t. 強双対性が成り立てば等価 f( x) wx ( ; ) 0, ( x; ) 0 max g( x, u) ( x, ) 0 uu 弱双対

50 第 3 部概要 1. 双対問題とその応用 2. ゲージ最適化問題の双対問題 I. ラグランジュ双対問題とFenchel 双対問題 II. Gauge 双対問題 III. 新しいタイプの双対問題 4. まとめ

51 一般化ゲージ最適化問題 一般化ゲージ最適化問題 特別な凸最適化問題 min c, x d, ( x) s.t. Ax B( x) b Hx K( x) e Gauge 最適化問題 絶対値計画 ただし, c, b, d, e, A, B, H, K は適当な大きさのベクトルや行列

52 一般化ゲージ最適化問題の補正 一般化ゲージ最適化問題は, 実効定義域外では, 定義が不明瞭になる場合がある. そこで以下では, 制約条件に実効定義域を加えた次の問題を考える. min c, x d, ( x) s.t. Ax B( x) Hx K( x) x dom b e

53 ラグランジュ双対問題 ラグランジュ関数 : 目的関数 : L( x, u, v) c, x d, ( x) 陽に表しにくい. 制約がないときはどうする? Fenchel 双対問題 他のタイプはないの? Gauge 双対問題 u, b Ax B( x) v, e Hx K( x) ( u, v) i nf L( x, u, v) xdom

54 Fenchel 双対問題 凸最適化問題 min f ( Ax) g( x) min s.t. f( x) x S * 標示関数を使えば, 制約つきの問題も扱える. min f( x) ( x) S min f ( y) g( x) s.t. y Ax

55 Fenchel 双対問題 min f ( y) g( x) s.t. y Ax L( x, y, ) f ( y) g( x), Ax y xy, ( ) inf f ( y) g( x), y Ax xy, sup, y f ( y), Ax g( x) y f ( y) p A, x g( x) sup, su y * * f ( ) g ( A ) * ただし, f は以下で定義される共役関数 ( ルジャンドル変換 ) f * ( y) sup x y, x f ( x) x

56 Fenchel 双対問題 * * m ax f ( ) g ( A ) 共役関数の例 : 線形関数凸 2 次関数平行移動分離可能な和 * 0 if y c f( x) c x f ( y) otherwise 1 * 1 1 f ( x) x Ax f ( y) x A x 2 2 * * f ( x) g( x b) f ( y) g ( y) b y f ( x, x ) g ( x ) g ( x ) f ( y, y ) g ( y ) g ( y ) * 1 2 * 1 *

57 Fenchel 双対問題の例 T min C max 0, a x y b n t t xr, yr t1 1 2 x 2 Support Vector Regression min s.t. T 1 K btt 2 1 t t t1 C C ( t 1,, T) 1, 0, 0 t t t t t t t t 教科書によく出ている Lagrange 双対問題 T T 1 min ( ) K ( ) b ( ) ( ) 2 s.t. ( ) 1 t t 0, C ( t 1,, T) t t t t t t t t1 t1

58 第 3 部概要 1. 双対問題とその応用 2. ゲージ最適化問題の双対問題 I. ラグランジュ双対問題とFenchel 双対問題 II. Gauge 双対問題 III. 新しいタイプの双対問題 4. まとめ

59 Gauge 双対問題の動機 数学的興味 : Gauge 関数の特性を生かした, Lagrange 双対問題とは違った双対問題はあるか? 工学的動機 : 制約条件と目的関数にある定数行列を入れ替えたい. Gauge 最適化 min ( x) s.t. ( Ax b) Lagrange 双対問題 max b, ( ) s.t. ( A ) 1 大規模凸最適化の代表的な解法は, 実行可能集合の射影を計算することが多い.

60 Gauge 双対性 [Freund, 1987] をgauge 関数とし, 次の二つの問題を考える. min ( x) min ( y) 1 s.t. x C s.t. y C 1 ただし, C は凸集合で, C を次式で定義する. 1 C y x, y 1 yc 注意最小化問題 1 max ( y) s.t. y C anti-polar という 1 x C, y C 1 のとき, ( x) ( y) x, y 1 これを弱双対と考える ( x) 1 ( y)

61 Gauge 双対問題 [Friedlander, Macedo, and Pong, 2014] C { x ( Ax b) } 1 のとき C A y by, ( y) y Gauge 最適化問題 min ( x) s.t. ( Ax b) Gauge 双対問題 min ( A y) s.t. b, y ( y) 1 性質 Lagrange 双対の最適値を D,Gauge 双対の最適値を D とすると L DD 1 L G * Lagrange 双対の最適解を,Gauge 双対の最適解をとすると y D * * G y G *

62 第 3 部概要 1. 双対問題とその応用 2. ゲージ最適化問題の双対問題 I. ラグランジュ双対問題とFenchel 双対問題 II. Gauge 双対問題 III. 新しいタイプの双対問題 4. まとめ

63 絶対値計画問題の双対問題 [Mangasarian, 2007] min c, x d, x s.t. Ax B x b Hx K x e Mangasarian の双対問題 max b, u e, v s.t. A u H v c B u K v d v 0 凸最適化問題 ( 線形計画問題に変換可能 ) 弱双対定理が成り立つ [Mangasarian 2007]

64 これまでの双対問題のまとめ 陽に表せない 今考えている問題 特別な凸最適化問題 Lagrange 双対問題 等価 Gauge 最適化問題 Fenchel 双対問題 絶対値計画 変数変換で等価 Mangasarian による双対問題? Gauge 双対問題

65 一般化ゲージ最適化問題の双対問題の表現 [ 山中, 山下,2018?] ( D ) max b, u e, v M 0 s.t. ( A H ) v 0 u v c B u K v d ただし, ( y ) ( y2) 0 ( y), i 0 ( y ) は の極関数 i 凸最適化問題 A, B, H, K は, より一般的には随伴作用素とする

66 双対問題 ( ) D M の例 : SDP min CX, s.t. Ai, X bi ( i 1,, m) ( X ) 1 S min s.t. CX, 0 ( X ) A, X 0 ( X ) b ( i 1,, m) i 0, X ( X ) 1 S X dom S S S i 双対問題 max b, u v m s. t. Au 0 ( S ) i i C v i1 v 0 ( S ) S max bu, s.t. m C Aiu i S i1

67 弱双対定理 定理 1 [ 山中, 山下 2018?] x を一般化ゲージ最適化問題の実行可能解とし, ( uv, ) を双対問題 ( D M ) の実行可能解とする. このとき cx, d, ( x) b, u e, v 凸性は仮定していない 双対問題の実行可能解なら A u H v c dom

68 弱双対定理の証明 c, x d, ( x) b, u e, v 双対問題の実行可能性ゲージ関数の非負性 c, x ( A u H v c) B u K v, ( x) b, u e, v c, x ( A u H v c), ( x) u, B( x) v, K( x) b, u e, v ( y), ( z) y, x, x dom, y dom c, x A u H v c, x 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 u, Ax B( x) b v, Hx K( x) e 0 主問題, 双対問題の実行可能性

69 Lagrange 双対問題との関係は? Lagrange 関数 : L( x, u, v) c, x d, ( x) u, d Ax B( x) v, e Hx K( x) Lagrange 双対問題の目的関数 ( uv, ) inf xdom L( x, u, v) L(0, u, v) b, u e, v ( D ) max b, u e, v M 0 s.t. ( A H ) v 0 u v c B u K v d Lagrange 双対よりもよい双対問題? ( 双対ギャップが小さい?)

70 残念!! 補題 1 ( uv, ) が双対問題 ( D M ) の実行可能解のとき ( u, v) b, u e, v ( D ) max b, u e, v M 0 s.t. ( A H ) v 0 u v c B u K v d ( D ) max ( u, v) M 0 s.t. ( u v ) A H c B u K v d v 0 ( D ) max ( u, v) L s.t. v 0 Lagrange 双対のほうがよい双対問題? ( 双対ギャップが小さい?)

71 補題 1 の証明 任意のに対して, L( x, u, v) c A u H v, x d B u K v, ( x) u, b v, e A u H v c, ( x) d B u K v, ( x) u, b v, e d B u K v A u H v c, ( x) u, b v, e u, b v, e 等号はのときに成り立つ. よって, x dom x 0 ( uv, ) in f L( x, u, v) b, u e, v xdom ( y), ( x) y, x 双対問題の実行可能性ゲージ関数の非負性

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

73 [ 山中, 山下 2018] の結果 仮定 1 すべての i に対して dom i は全空間で, が成り立つ ( x ) 0 x 0 i i 補題 2 [ 山中, 山下 2018] v 0 とする. 仮定 1が成り立つとする. ( uv, ) が双対問題 ( D M ) の実行可能解でなければ uv xdom (, ) in f L( x, u, v) 絶対値計画は仮定 1を満たす. 標示関数は仮定 1を満たさないので,SDPではこの結果が使えない gx ( ) max{0, x i } は仮定 1を満たさない.

74 仮定 1 を弱めた仮定 仮定 2 i すべてのに対して, 次の (I) と (II) どちらかが成り立つ. (I) di 0, Bti 0 t, Kti 0 t (II) dom i が全空間で, ˆ i( xi) 0 となる xˆi が存在. Remark すべての i に対して (I) が成り立てば, 一般化ゲージ最適化は凸最適化になる (II) は実質的には, dom i が全空間 で十分. もし, i ( x) 0 x であれば, i を適当なノルムに置き換えて, にかかる係数 d, B, K を0とすればよい. i i i i

75 新しい仮定のもとでの補題 仮定 2 のもとで次の補題が成り立つ. 補題 3 v 0 とする. 仮定 2が成り立つとする. ( uv, ) が双対問題 ( D M ) の実行可能解でなければ uv xdom (, ) in f L( x, u, v)

76 補題 3 の証明 ( 記号の定義 ) 制約条件は (( A u H v c) ) ( B u K v) d ( i 1,, ) i i i i この制約条件を満たしていないため, ある (( A u H v c) ) d ( B u K v) が存在して いま, ( A u H v c), d ( B u K v) とおくと ( ) 大事な式 (1)

77 補題 3 の証明 ( ラグランジュ関数の表記 ) ラグランジュ関数は以下のように書ける. L( x, u, v) c, x d, ( x) u, b Ax B( x) v, e Hx K( x) c A u H v, x d B u K v, ( x) u, b v, e いま, x (0,,0, x,0,,0) とすると ( x) (0,,0, ( x ),0,, 0) となり, さらに L( x, u, v), x ( x ) u, b v, e 大事な式 (2)

78 補題 3 の証明 ( 流れ ) 次の三つの場合にわけ, それぞれで ( uv, ) を示す 場合 1: ( ) (0, ) のとき 場合 2: ( ) のとき 場合 3: ( ) 0 のとき

79 場合 1: ( ) (0, ) のとき このとき, ( ) を定義する最大化問題 : より, 任意の に対して となる x ( ) が存在する. さらに, ( ) 0 となるに対して となる x ( ) が存在する. 実際,, x ( ) のとき, x ( ) 0 であるから, 正斉次性より, x ( ) の存在性を示せる. ( ) sup x, ( x ) 1 0 ( ), x ( ), ( x ( )) 1 ( ), x ( ), ( x ( )) 1 0

80 場合 1: ( ) (0, ) のとき ( 続き ) いま, とおく. さらに, x( t) (0,,0, tx ( ), 0,,0), tr とすると, よって, 1 min ( ), ( ) 0 2 L( x( t), u, v), tx ( ) ( tx ( ) ) u, b v, e t ( ) ( x ( )) u, b v, e t ( ) u, b v, e ( ) t u, b v, e 2 lim L( xt ( ), uv, ) t 大事な式 (1) ( x ( )) 1 大事な式 (2) ( ), x ( ) ( ) 2 大事な式 (1)

81 場合 2: 0 ( ) のとき ( ) sup x, ( x ) 1 より k k ( x ) 1, x, k となる点列 { x } dom が存在する. x (0,,0, x,0,,0) k k いま, とすると, k k k L( x, u, v), x ( x ) u, b v, e 大事な式 (2) よって, k lim L( x, u, v) k

82 場合 3: ( ) ( ) 0 より 0 のとき 大事な式 (1) (a) が仮定 2 の (I) を満たすとき 0 d ( B u K v) d B u K v t t t t t よって矛盾. この場合は存在しない. t d K t 0, B 0 t, t 0t, v 0t t

83 場合 3: ( ) 0 0 のとき (b) が仮定 2 の (II) を満たすとき (b-1) のとき 0 ( ) 1 となる 0 が存在する. ( ) sup x, ( x ) 1, 0 となり矛盾. このような場合は存在しない.

84 場合 3: ( ) 0 0 のとき (b) が仮定 2 の (II) を満たすとき (b-2) 0 のとき仮定より ( xˆ ) 0 となる xˆ が存在する. xˆ ( t) (0,,0, txˆ, 0,, 0), t R とすると, 大事な式 (2) L( xˆ ( t), u, v), txˆ ( txˆ ) u, b v, e t( x ) u, b v, e よって, ( uv, )

85 Lagrange 双対問題との等価性 定理 2 仮定 2 を満たすとする. さらに, ラグランジュ双対問題が最適解をもつとする. D M このとき,( ) とラグランジュ双対問題の最適値および最適解が一致する. 凸性は仮定していない

86 定理の証明 Lagrange 双対 max ( uv, ) s.t v 0 補題 3 max ( uv, ) s.t ( A u H v c) B u K v d v 0 ( D M ) 補題 1 max s.t b, u e, v ( A u H v c) B u K v d v 0

87 双対問題の双対問題 双対問題 max b, u e, v s.t. ( A u H v d ) B u K v d v 0 主問題 min c, x d, ( x) s.t. Ax B( x) b Hx K( x) e 双対問題の双対問題 min c, x d, z s.t. Ax Bz b Hx Kz e ( x) z 凸な場合 B 0 d 0 0, Ki i min c, x d, ( x) s.t. Ax B( x) b Hx K( x) e

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

89 非凸な場合の残念な結果 0-1 変数をもつ問題は単なる連続緩和. min c, x s.t. Hx e 1 xi ( yi 1), yi 1 ( i 1,, n ) 2 双対の双対 min s.t. c, x Hx e x i 1 ( yi 1), yi 1 ( i 1,, n ) 2 *0-1 制約以外が凸な場合でも同様

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

91 ノルムと一次式で構成された最適化問題とその双対問題 参考文献とその他の話題 京都大学大学院情報学研究科 山下信雄

92 参考文献 凸解析 (Convex Analysis) [1] R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, * 共役関数と双対性. 凸集合の関係など, ゲージ関数の基本的な性質 [2] 福島雅夫, 非線形最適化の基礎, 朝倉書店, * 凸関数の共役関数の諸性質.Lagrange 双対問題と Fenchel 双対問題.

93 参考文献 絶対値計画問題 (Absolute Value Programming) [3] O. L. Mangasarian, Absolute value programming, Computational Optimization and Applications, Vol. 36, pp , * 絶対値計画問題の定義と双対問題. 弱双対性の証明. [4] O. L. Mangasarian, Linear complementarity as absolute value equation solution, Optimization Letters, Vol. 8, pp , * 線形相補性問題と絶対値方程式の関係. なお, 絶対値方程式の論文は多々ある.

94 参考文献 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 , * Gauge duality の元論文 [6] M. P. Friedlander, I. Macedo, and T. K. Pong, Gauge optimization and duality, SIAM Journal on Optimization, Vol. 24, pp , *Gauge 最適化問題の定義とその双対性.Gauge 関数の諸性質 [7] A. Y. Aravkin, J. V. Burke, D. Drusvyatskiy, M. P. Friedlander, and K. MacPhee, Foundations of gauge and perspective duality, arxiv: , * 非負の凸関数の Gauge 関数への変換とその諸性質. gauge dual の解と主問題の解の関係

95 参考文献 一般化ゲージ最適化問題とその双対性 [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: , * 未完成. 論文 [7] の内容を一般化ゲージ最適化問題に [10] 加茂寛也, 山下信雄, 正斉次最適化問題の一般化とその双対問題, 2018 年秋季研究発表会, 日本オペレーションズリサーチ学会,2018. * 9 月にOR 学会で発表予定.[8] の内容を錐制約に拡張

96 その他の話題 数学的な話 さらなる一般化の話 ゲージ関数の一般化 非負性, 正斉次性がない一般の凸関数 非凸な関数 問題の一般化 不等式制約から錐制約

97 数学的な話題 [Rockafellar, 1970] ゲージ関数の定義 : C を0を含む凸集合とする. f ( x) inf 0 xc 極集合 (polar set) の定義 : C y x, y 1 x C C が錐のとき C y x, y 0 x C 極関数 : f ( y) inf 0 x, y f ( x) x

98 より一般的な凸関数への拡張 Gauge 関数 : 正斉次かつ非負な凸関数 非負でない凸関数 非負な凸関数 + 1 次関数 ydom f, f( y) として f( x) f ( x) f ( y), x y f( y), x y 非負な凸関数 非負な凸関数 正斉次な凸関数 x x0f if x0 0 x0 ˆ(, 0 ) f x x f ( x) if x0 0, x 0 0 if x0 x 0 otherwiase 1 次関数 f は f の recession function

99 例 : f ( x) x, f ˆ( x, x) x 0 x 1 2 f ˆ ( y 0, y) sup x, y x 0 y 0 x 1 x0 y0 0 のとき ˆ f ( y, 0 y) y のとき 0 0, y 0 ˆ f ( y, 0 y) y0 0, y 0 のとき ˆ f ( y, 0 y) 0 それ以外のとき : KKT 条件を書くと y 2x 0, y 0, ( x x ) 0 y, x 0 0 y y0 4 y0, x ˆ y f ( y, y) y, y y y0 4y0 4y0 y y

100 例 : f ( x) x, f ˆ( x, x) x 0 x 主問題 min s.t. x 2 Hx e 1 min x 0 s.t. x 1 0 x Hx e 2 min 0, x 1, fˆ ( x) s.t. (1 0) x 0 fˆ ( x) 1 (0 H ) x 0 fˆ ( x) e Lagrange 双対問題 双対問題 双対問題 1 T 2 max H v e, v 4 s. t. v 0 max u e, v s.t. 1 4 H 0 u v 0 T v 2 u max u ev, ˆ 1 0 s.t. f u v T 0 H v 0 1

101 正斉次最適化問題 [ 山中, 山下 2018] (positively homogeneous optimization) min c, x d, ( x) s.t. Ax B( x) b Hx K( x) e 1( x1) ( x ) 2 2 ( x) ( x ) ただし 正斉次 非負 i : V ( i 1,, ) i i R (0) 0 ( i 1,, ) は 凸性を仮定していない

102 正斉次最適化問題の性質 極関数 i を同じように定義でき, ( x) ( y), i i xy ( D M ) を構成でき, 適当な仮定のもとでLagrange 双対と等価 例 : ( x) x (0 p 1), ( y) y, ( x) x i p i i min s.t. x p Ax b 凸でない 双対の双対 min s.t. x 1 1 Ax b