代数的組合せ最適化part III

(1)

代数的組合せ最適化 part III

1. 劣モジュラ性と CAT(0) 空間緩和に基づくアルゴリズム

2. 重み付き ( 非可換 ) Edmonds 問題（時間があれば）

(2)

２部マッチングにおける劣モジュラ性

グラフ

|�|+¿ � ∨¿

¿ � ∨¿=� +� − max . ¿ max

❑

�:マッチング ¿

Obs ( 劣モジュラ性 )

• 安定

•

 ２部マッチングの双対は，劣モジュラ関数最小化とみなせる．

2

(3)

nc-rank

における劣モジュラ性

s.t. ⁽^{∀ �)}

,

0

∗ ∗

∗

� ∗

�

� �

_�

� =¿

Thm (Fortin-Reutenauer 2004)

実は，この問題が

劣モジュラ関数最小化とみなせる

(4)

最大消滅部分空間問題 MVSP Maximum Vanishing Subspace Problem

MVSP:

: ベクトル部分空間

Obs ( 劣モジュラ性 )

•

4

• ２次形式とみる

( � , � ) ↦ �

^�

�

_�

�

この劣モジュラ性を利用できないか？

(5)

古典的劣モジュラ関数最小化

: 劣モジュラ

� : {0,1}^� →ℝ´

000 100

110 111 101

001 010 011

凸関数

Lovasz 拡張

の最小化

¿

の最小化多項式時間アルゴリズム

⇐

楕円体法

の劣勾配

Greedy algorithm Grotschel-Lovasz-Schrijver 1981

ℝ´ =ℝ ∪{^∞ }

(6)

Hamada-Hirai 2017 のアプローチ

6

劣モジュラ : モジュラ束

ℒ オーソスキーム複体

� ( ℒ )

Lovasz 拡張凸関数

CAT ( 0 ) 空間

の最小化

¿

の最小化

--- MVSP に特化 ---

分割近接点法多項式時間アルゴリズム

⇐

(7)

CAT(0) 空間

測地的距離空間３角形が痩せている

Cartan, Alexandrov, Topogonov, curvature

�

� � �

� (� ,�)≤

‖

�^´ −�´

‖

₂

� ´

� ´ � ´

ℝ²

� ´

(� ,�)

Gromov 1987

例：ユークリッド空間，ツリー，ユークリッド型ビルディング , ...

• CAT(0) 空間は一意測地的  測地的凸性

(8)

オーソスキーム

(orthoscheme)

named by Coxeter 1991

Def. - 次元オーソスキーム

- 次元単体，頂点が

000 100

110 111

00 10

ℝ² 11 ℝ³

8

(9)

: 高さ関数をもつ半順序集合

ℒ

�

�₁

�₂

�₃

ℝ (¿ ¿� ,�2)

¿

000 100

110 111

Brady-McCammond 2012

オーソスキーム複体

:= の元の凸結合で

がチェインとなるもの全体

～各単体をオーソスキームとして距離を入れる

(10)

10

ℒ ^� ⁽ ^ℒ ⁾

パスの長さが定義される .

� (� , �)≔inf

{

^�⁽ ^�⁾

|

^� ^:⁽^�^, ^� ⁾^{− path \}}

: 測地的距離空間

� � �

２点の距離の距離 :

(11)

Example

...

ℒ

^� ⁽^ℒ ⁾

....

ℒ=2^{1,2^{,… ,�}^} ^� ⁽ℒ )≃[0,1]^�

(12)

分配束

CAT(0)

Lem: 半順序集合のイデアル族

Birkhof

� (_ℒ )≃

{

^{� ∈}^[^0,1^]^�

|

^�⁽ ^�⁾^≤ ^�⁽^�⁾⁽^�^, ^{� ∈ �} ^:^�_≼ ^�^)}

12

ℒ ^� ⁽ ^ℒ ⁾

c.f. 順序多面体 [Stanley 86; Fujishige 84]

(13)

Thm (Chalopin et al. 2014) は CAT(0) 空間

Def. の Lovasz 拡張

Thm (Hirai 2018)

は劣モジュラは（測地的）凸ランク有限モジュラ束

(14)

14

証明のポイント

Lem (Birkhof-Dedekind)

: チェイン， : 部分分配束 s.t.

Lem (Chalopin et al. 2014) ) 内の凸集合

凸が上凸

, が上凸，ここで

部分分配束 , が上凸

部分分配束 , が上劣モジュラが劣モ

の support チェインを含む

部分分配束をとる．

通常の Lovasz 拡張

(15)

MVSP:

,

: ベクトル部分空間

のベクトル部分空間のなす束

: のベクトル部分空間のなす束，逆包含順序 Lem (Iwata,Murota 1995) は劣モジュラ

�=�+�+1にとれる

(16)

16

非可換ランク

この問題 -- CAT(0) 空間上の凸最適化 -- を解けばよい

特殊性 : 目的関数が凸関数の和なっている．

 分割近接点法を適用

(17)

分割近接点法

完備な CAT(0) 空間凸関数

�

^�⁺¹

≔ argmin

_{� ∈ �}

�

_�_mod_�

( � ) + 1

�

_�

� ( � , �

^�

)

²

目標の最小化

分割近接点法の更新式：

Bačák 2014

Thm (Ohta-Pálfia 2015) - リプシッツ , - 強凸 ,

(18)

18

として分割近接点法 + 収束評価を適用

注：本当は強凸性をもたせるため摂動も行う

poly 反復後に

整数性よりの support のなかに最適解存在

(19)

重要なポイント（分割近接点が実装できる）

Min .� rank´ �_�(�, �)+ 1

�

{

^�

⁽

^� ^,^�⁰

⁾

²⁺^�

⁽

^� ^, ^�⁰

⁾

²

}

�₀^⊥

ℒ ℳ

�₀

: - 直交

�₀

�₀^⊥

Lem (Hamada-Hirai 2017)

最適解

ブール束

nonzero supp. of ブール束

nonzero supp. of

凸２次計画に帰着

(20)

20

良い点・問題点

• コンセプチュアルにシンプル，他の問題にも応用できるかも

• 体がなんであっても動くが，ときは

変数 ( ＝ベクトル空間のチェイン ) を表現するための基底の

ビットサイズがバウンドできてない (- 直交操作に起因 )

• 改良の余地が大いにあり

(21)

重み付き

(

非可換

) Edmonds

問題

(22)

22

問題意識

重み付き２部マッチングなどの「重み付き」の問題を

このように「非可換」線形代数的にとらえることできるか？

1 2 3 4

�₁₂

�₄₃

例：最大重み完全マッチング問題

Max.

s.t. 完全マッチング

+¿ : 枝重み

�_�� ∈ ℤ_¿

(23)

重み付き２部マッチングの代数的解釈

1 2 3 4

�₁₂

�₄₃

4

¿

�^�¹² �₁₂

�^�²¹ �21

¿

�(�)=

(

^�

�14 �₁₄

�^�²³ �23

¿

�^�³² �₃₂

�^�⁴¹ �₄₁ �^�⁴³ �43 �^�⁴⁴ �44

)

1

3 4 2

1 2

¿

∑

� � ∈�

�^�^�� �_�� �_��

3

完全マッチングの最大重み

∵ deg det �= deg ∑

�

± �

^�⁽^�⁾

∏

� � ∈�

�

_��

= max

�

� ( � )

トロピカル化

(24)

24

重み付き（可換） Edmonds 問題変数付き多項式行列

のは効率的に計算できるか？

: 変数

これの非可換版を考える

(25)

をどうみるか ?

• ( 歪 ) 多項式環上の行列とみる

• 有理関数斜体 (Ore 商環 ) 上の行列とみる

• 次数

Ore 環 ---- 右 / 左公倍数が存在

≠ 0

(26)

26

Dieudonne

行列式～

^{斜体上の行列の行列式}

上の正則行列（今の場合�=�

( ^⟨

^�

^⟩ )

⁽^t⁾） Bruhat 分解～ ^{斜体上の行列の} ^LU ^分解

� = � � � �

下三角対角 1

対角行列置換行列上三角対角 1 ユニーク

Dieudonne 行列式 ^{乗法群の可換化の元}

Det �≔ sgn ( � ) �

₁₁

�

₂₂

… �

_��

mod [ �

^∗

, �

^∗

]

交換子群

Lem: ^:^{非正則のときは，}

(27)

重み付き「非可換」

Edmonds

問題

変数付き多項式行列

のは効率的に計算できるか？

: 変数�_� � _�≠� _� �_�

※ 交換子上では，はゼロなのでは well-defined

deg (��⁻¹�⁻¹¿=0

Hirai 2018

(28)

28

最大最小定理（ Fortin-Reutenauer の定理の拡張）

deg Det � =¿ Min. −deg det � − deg det Q

s.t.

, Thm (Hirai 2018)

(29)

弱双対性の証明

deg

(

^{� �}��

)

_�� ^≤⁰⁽^{∀ �} ^,^{∀ ��}⁾

⇒ deg ( � � � )

_��

≤ 0 ( ∀ �� )

⇒ deg Det �� ≤ 0

⇒ deg ( Det � Det � Det � ) ≤ 0

⇒ deg Det � + deg Det � + deg Det � ≤ 0 deg det ¿ � deg det ¿ �

c.f. Murota 95

(30)

30

強双対性

+

アルゴリズム

(SDA)

(� �₁ �)⁰⁺(� �₂�)⁰�₁+…+(� �_��)⁰ �_�

over

上で非正則

We can augment s.t.

deg det �^′+deg det �^′>deg det �+deg det �

¿

最適

deg Det �� =0

over

proper

(31)

0

∗ ∗

�

� � +�>�

nc − rank ( �� )

⁰

< �

nonsingular over

deg det �^′+deg det �^′=(� +�−�)+deg det � +deg det �

¿0

��

�⁻¹�⁻¹

� ′ � ′

Long-step: use , ,

(32)

32

Remarks

• このアルゴリズムは， deg det を計算する

組合せ緩和法（ Murota 1990,1995 ）の変種とみなせる．

• 双対問題 MVMP は，一様モジュラ束 (Hirai 2017) というモジュラ束上の L 凸関数最小化とみなせる．

• さらにアルゴリズムは， L 凸関数に対する

最急降下法 (SDA) とみなせる  反復回数の解析

離散凸解析 beyond

(33)

• ２部マッチング

• 線形マトロイド

• 線形マトロイド交差

SDA + long-step ハンガリー法

SDA + long-step 貪欲アルゴリズム

SDA + long-step weight splitting algorithm (Frank 1981)

古江弘樹，卒業論文 2019 ，論文準備中

既存のアルゴリズムとの関係

(34)

34

さらなる展開

Oki 2019

• deg Det を nc-rank に帰着させる方法

• 一般の歪多項式行列の deg Det の計算

歪多項式環

例 : Weyl 代数

• 微分方程式，制御論への応用

(35)

Part III

まとめ

• nc-rank における劣モジュラ性

• CAT(0) 空間の凸最適化をつかうアプローチ

• 重み付き ( 非可換 )Edmonds 問題， deg Det

(36)

36

総括

• ２部マッチングのランク解釈からはじまる組合せ最適化の一つの展開

• 非可換ランクの概念，アルゴリズムは，

従来の多面体的手法とは異なる視点を提供し，

新しい発展の方向性を示しているように感じる．

(37)

今後の課題・研究の方向性

• IQS アルゴリズムの簡略化

• 歪対称行列に対する理論 :

非２部マッチング，線形マトロイドマッチング etc に対する枠組み cf. Iwata, Kobayashi 2017

• モジュラ束上の劣モジュラ最適化

cf. Kuivinen 2011, Fujishige, Kiraly, Makino, Takazawa, Tanigawa 2014

• 離散凸解析 beyond

• CAT(0) 空間上のアルゴリズムと最適化

e.g., Hamada, Hirai 2017 の洗練・改良

• 剛性理論との関連 c.f. Lovasz 1989, Raz, Wigderson 2019

⋮

(38)

38

代数的組合せ最適化part III