修士論文 要旨

共正値計画問題に対する単体細分アルゴリズムとその拡張
数理情報学専攻 48166228
指導教員

平手 一成
平井 広志 准教授と表せることがわかる．

1 はじめに

このままでは１つの行列の共正値判定が複数の行列⊤n × n の実対称行列 A が x Ax ≥ 0 (∀x ∈ Rn+ ) を満たすとき，A は共正値であるという．ただし，Rn+ はnの共正値判定に置き換わっただけであるが，ある行列が次元非負実数空間を表す．最大クリーク数を求める問

似錐 M ⊂ C を用いることを考えると，単体分割の意義題や標準２次計画問題などの様々な組合せ最適化問題が現れる．M と共正値行列 A ∈ S に適当な仮定を入や２次計画問題が共正値計画問題で表せることが知られれば，∆ が十分小さい（１番長い辺が十分に短い）なれている．共正値計画問題を解くのは NP-hard である

らば，V∆⊤ AV∆ ∈ M が示される．∆ が十分小さいならため，近似解法が主に研究されている．また，ある行列ば，条件 V∆⊤ AV∆ ∈ M と条件 V∆⊤ AV∆ ∈ C がほとんが共正値であるかそうでないか判定する問題は，共正値ど変わらないことを意味している．

共正値か判定するのは co-NP-complete であるため近判定問題と呼ばれ，co-NP-complete である．共正値計

Sponsel ら [4] は V∆⊤ AV∆ ∈/ M であるような単体画問題を共正値判定を行うことで解く方法もさかんに∆ を分割し続けるというアルゴリズムを提案した．こ研究されている．のアルゴリズムは Bundfuss と Dür [1] が考案した単

本論文では，Bundfuss と Dür [1] が考案した単体体細分を用いた共正値判定アルゴリズムの拡張であり，細分を用いた共正値判定アルゴリズムおよび Sponsel

Bundfuss と Dür [1] が考案したアルゴリズムは，近ら [4] の拡張を元にした研究を行った．この先行研究に似錐として非負対称行列錐を当てはめたものとなってついて第２章で説明した後，第３-５章で本研究の成果いる．

を述べる．

3 頂点番号のランダマイズ化

2 先行研究Bundfuss と Dür [1] が提案したアルゴリズムを用い単体細分を用いた共正値判定アルゴリズムを考えるて最大クリーク数を求める際に，グラフの頂点番号を上で，まず，標準単体と呼ばれる単体 ∆st = {x ∈ Rn+ :ランダムに入れ替えたグラフにも用いることによって，

x1 + x2 + · · · + xn = 1} を用いて，実対称行列 A ∈ S が最大クリーク数のより良い下限が求まることを発見しn共正値である条件の x⊤ Ax ≥ 0 (∀x ∈ Rn+ ) の ∀x ∈ R+た．そして，複数の頂点番号をランダムに入れ替えたグの部分を ∀x ∈ ∆st に置き換える．

ラフについて提案されたアルゴリズムを適用すること

単体細分を用いた共正値判定アルゴリズムでは，こで，[1] の手法を用いた [2] で求まっている解よりも良の ∆st を int∆i ∩ int∆j = ∅ (i ̸= j) となるようない解を求めることに成功した．実験結果をまとめたも{∆ , ..., ∆ } を用いて，のが表 1. となっている．実験で用いたグラフは，The1m∆st =m∪Second DIMACS Implementation Challenge [5] の最i∆i=1

大クリーク問題のベンチマークである．クリーク数は，グラフに含まれるクリークの中で最も頂点数が大きいと単体 ∆st を分割し，∀x ∈ ∆st でなく，∀x ∈ ∆i (i =クリークの頂点数である．実験は 100 個の頂点番号を1, . . . , m) の様に小さい単体に分けて共正値の条件を考ランダムに入れ替えたグラフに対して行った．

える．ここで，単体 ∆ 上の点 x についての共正値の条件 x⊤ Ax ≥ 0 (∀x ∈ ∆) は，単体 ∆ の頂点をなら4 C 1 への適用

べた行列 V∆ を用いて，x⊤ V∆⊤ AV∆ x ≥ 0 (∀x ∈ ∆st )Sponsel ら [4] が提案した共正値判定アルゴリズムをと言い換えることができることに注意する．共正値錐

de Klerk と Pasechnik [3] によって提案されている共{}C = A ∈ S : x⊤ Ax ≥ 0 for all x ∈ Rn+ を用いると，「A が共正値」⇔A ∈ C⇔V∆⊤i AV∆i ∈ C (i = 1, . . . , m)正値錐の近似錐を用いることで拡張した．これによっ

共正値計画問題に対する単体細分アルゴリズムとその拡張 (平手 一成)

表 1. 先行研究と本研究で求まったクリーク数の下限

グラフ名頂点

Brock200 1200

Brock200 2200

表 2. Brock16 のクリーク数での共正値判定結果

Keller4

手法名

単体数

反復回数

時間 (s)

171

C -23-in

889953116255602

1335.065831

11辺14834

9876

9435

C -23-out

8829635

17659269

1258.007799

クリーク数

211211C 1 -32-in

17829614

33648926

2612.610559

1

先行研究

13108

C -32-out

16872170

33744339

2564.303332

本研究141111

既存手法

56062305

112124609

3784.309601て，[2] よりもアルゴリズムの実行時間及び反復回数やとなっている．この新しい近似錐を用いることによっ生じる単体が少ない手法を提案することができた．て，既存研究とは違った近似錐を用いて，１つ１つの単de Klerk と Pasechnik [3] の考えた近似錐は次の様に定義される:体をみる必要のない共正値判定アルゴリズムを考案することができた．

()rnn∑∑C r = {A ∈ S : Aij xi xj xii,j=1i=1のすべての単項の係数が非負 }.

6 今後の課題第４章の内容について，最大クリークの下限しか求まらないような難しい問題に対して，[2] よりも良い結果

先行研究の M に C を当てはめると，１つの頂点につが得られるような，もしくは頂点番号についてロバストいての条件と２つの頂点についての条件（１つの辺につな結果が得られるような細分規則の考案が今後の課題いての条件）と３つの頂点についての条件（３つの辺にといえる．また，深さ優先探索でなく，切る辺を決めそついての条件）が出てくる．２つの頂点についての条件の辺を持つすべての単体をその辺について分割する手が破れていたときは先行研究と同様の単体分割を行い，法を当てはめることが可能と考えられるので，実際に当３つの頂点についての条件が破れていたときは以下のてはめることも今後の課題である．

1分割方法を考案した．３つの頂点が成す３角形の内部

第５章の内容について，新しい近似錐を使って実際にに３角形上の点の中で最小となる点が存在するならば，アルゴリズムを組む際に，入力として [4] で述べられてその点をとってきて３つに分割，そうでないならば，３いる１つの近似錐を採用したが，他の近似錐を入力の近つの辺の条件の中から，条件を破っている辺をとってき似錐として採用することが考えられる．また，単体細分てその辺について２つに分割，という方法である．の規則について，この新しい近似錐に適した規則を考え

実験は The Second DIMACS Implementation Chal-lenge [5] のグラフジェネレーターを用いて生成したグ
ラフのクリーク数についての共正値判定の実験を行った．実験結果の内の１つが表２である．実験で用いた

Brock16 は頂点１６辺７１クリーク数５のグラフである．この実験で扱われた C 1 から始まる分割手法が本研究の手法で複数あるのは条件をみる順番等のためである．単体数は実験終了時にできていた単体の数を表す．
本研究の手法はどの項目においても元となった手法より優れているといえる．

5 新しい近似錐
３つ目は，単体分割と近似錐が与えられると定義される新しい近似錐を考案したことである．この近似錐は，単体分割によって定義されるが，単体分割の単体の情報は必要とせず，頂点集合と辺集合から定義される近似錐ることがあげられる．

参考文献[1] S. Bundfuss and M. Dür: Algorithmic copositivity
detection by simplicial partition. Linear Algebra andits Applications, 428(2008), pp. 1511–1523.
[2] M. Dür and J. Žilinskas: Depth-first simplicial partition for copositivity detection, with an application
to Maxclique. Optimization Methods and Software,26(2011), pp. 499–510.
[3] E. de Klerk and D. V. Pasechnik: Approximation ofstability number of a graph via copositive programming. SIAM Journal on Optimization, 12(2002), pp.
875–892.
[4] J. Sponsel, S. Bundfuss and M. Dür: An improved
algorithm to test copositivity. Journal of Global Optimization, 52(2012), pp. 537–551.
[5] The Second DIMACS Implementation Challenge,
http://dimacs.rutgers.edu/Challenges/