752

c オペレーションズ・リサーチ
要約■
■学生論文賞受賞論文
行列の共正値性を判定する新しいアルゴリズムの提案
田中彰浩
筑波大学大学院システム情報工学研究科
指導教員：吉瀬章子教授
VΔ の集合を M (P) とする．最後に P の最長辺 δ(P)
1. はじめに
を定義する．
本研究は n 次実対称行列が共正値性 (copositivity)
δ(P) = max max ||u − v||
Δ∈P u，v∈Δ
を有するか否かの判定問題を扱う．共正値性を有する
行列の集合 C n は以下で与えられる．
次に [2] で紹介されている，行列が共正値性を有する
か否かの判定を行うアルゴリズムについて述べる．
C n = {A ∈ S n : ∀x ∈ Rn+ ，xT Ax ≥ 0}
n
n
+
ただし S は n 次元対称行列の集合であり，R は n
n
次元の非負ベクトルの集合である．半正定値錐を S+
，
n
+ N n ⊆ Cn
非負錐を N n とすると，定義より S+
定理 1. [Theorem 2.1 [2]] Mn は Mn ⊆ C n を満た
すとする．A ∈ S n が以下を満たすとき，A は共正値
行列である．
∀Δ ∈ P,
が成立することがわかる．共正値行列の集合 C n は
VΔT AVΔ ∈ Mn
クリーク問題と密接な関係があることが示されてい
定理 1 は Mn = C n の場合について，簡単な計算によ
る．n 個の頂点からなる無向グラフ G の最大クリー
り導出される．
ク数を ω とし，AG を隣接行列，e を要素がすべて
1 であるベクトル，E = eeT とする．[3] は
1
ω
=
minx {xT (E − AG )x : eT x = 1, x ≥ 0} が成立す
ることを示した．また [1] はこの問題を，C n を用いて
ω = miny {y ∈ N : y(E − AG ) − E ∈ C n } と定式
化できることを示した．しかし，与えられた行列が共
定理 2. [Theorem 2.2 [2]] A ∈ S n は，ΔS 上の任意
の x に対して xT Ax > 0 を満たす (狭義共正値行列) と
する．また，Mn ⊇ N n とする．このとき，δ(P) < ε
を満たす任意の分割 P に対して，以下の式が成立する
ような ε > 0 が存在する．
∀Δ ∈ P,
正値性を有するか否かの判定は co-NP 完全であり [4]，
そう簡単ではない．以降ではこの判定を行う [2] の提
案に加え，われわれの新たな提案の紹介を行う．
2. 共正値性の判定
定理 3. [Lemma 2.3 [2]] 以下の 2 条件は同値である．
1. A ∈
/ Cn
2. δ(P) < ε を満たす任意の分割 P にたいして，
v ∈ V (P) が存在し v T Av < 0 となるような，
標準単体 ΔS を，ΔS = {x ∈ Rn
+ : ||x||1 = 1} と定
義する．行列 A が共正値行列であるための必要十分条
件は，ΔS 上の任意の x に対して xT Ax ≥ 0 を満たす
ことである．また，単体 Δ を標準単体上の n 本のア
フィン独立な点 v1 ，. . . ，vn の凸包とする．さらに，集
Δm } が以下の条件を満たすとき
合族 P = {Δ1 ，. . . ，
P を Δ の単体分割という．
Δ=
m
VΔT AVΔ ∈ Mn
ε > 0 が存在する．
定理 2 と定理 3 は xT Ay の連続性から導出される．
アルゴリズム 1：行列 A の共正値性の判定を行う．
Input：A ∈ S n ，Mn ⊂ C n
Output：“A は共正値行列”または“A は共正値
行列でない”
Δi かつ ∀i = j ，int(Δi ) ∩ int(Δj ) = ∅
i=1
1. P ← {ΔS }
2. while P = ∅ do
次に，単体分割 P の頂点の集合 V (P) を定義する．
3.
Δ ∈ P を選択;
V (P) = {v : v はあるΔ ∈ P の頂点 }
4.
if ∃v ∈ V ({Δ}) : v T Av < 0 then
さらに単体 Δ の頂点を列ベクトルにもつ行列を VΔ と
5.
する．単体分割 P 内の単体 Δ によって構成される行列
6.
752 （66）Copyright
return“A は共正値行列でない”；
end
c by ORSJ. Unauthorized reproduction of this article is prohibited.
オペレーションズ・リサーチ
7.
8.
9.
(PA ) の最適値が 0 であるならば，行列 A は A ∈
if VΔT AVΔ ∈ Mn then
S+n + N n ⊆ C n である. この考えから G n を以下の
P ← P \ {Δ};
ように定義する．
else
10.
Δ を Δ = Δ1 ∪ Δ2 に分割;
G n := {A ∈ S n : PA の最適値が 0}
11.
P ← P \ {Δ} ∪ {Δ1 ，
Δ2 };
上記の Hn , G n について，クリーク問題を用いて比較
12.
実験を行ったところ，クリーク数の上界値を求める問
end
題に対して G n は有効であることが確認された．
13. end
14. return“A は共正値行列”
4. 分割規則の改良
定理 2 と定理 3 より，行列 A が狭義共正値行列である
場合と，共正値行列でない場合についてアルゴリズム
1 の収束性が保証される．
tion を用いた．しかし，この分割規則は VΔT AVΔ の情
3. M の選び方
アルゴリズム 1 で用いられる Mn の選択は，反復
回数や計算時間に大きな影響を与える．まず初めに [2]
で紹介されている Mn = Hn について述べる．
N (A)ij :=
ム 1 は単体 Δ の分割を行う．δ(P) → 0 を満たすよく
知られた分割規則として，前章の比較実験では bisec-
n
行列 VΔT AVΔ が Mn の要素でないとき，アルゴリズ
報を利用しない分割規則である．これに対しわれわれ
は Mn = G n の場合について，(PA ) の有効な制約の
情報を用いた分割規則を提案した．この手法に対し計
算機実験を行った結果，いくつかの問題に対して有効
Aij
Aij > 0 かつ i = j
であることが確認された．しかし，既存研究において
0
その他
提案されている，Hn の分割規則改良と比較すると効
と定義し，S(A) := A−N (A) とする．このとき N (A)
は定義より明らかに非負行列であるから，S(A) が半
n
+ N n ⊆ C n が成立する．し
正定値であれば A ∈ S+
n
たがって H を以下のように定義する．
Hn := {A ∈ S n : S(A) ∈ S+n }
次に本研究の提案手法である Mn = G n について
述べる．行列 A が対称行列であるならば，P ΛP T と
固有値分解することが可能である．ただし P は直交
行列であり， Λ は固有値を要素として持つ対角行列
である．さらに対角行列 Ω ≤ Λ を用いて，P ΛP T =
P (Λ − Ω)P T + P ΩP T と分解する．Ω ≤ Λ であるか
ら P (Λ − Ω)P T 半正定値行列である．この条件の元で
P ΩP T ≥ O を満たせば，行列 A は A ∈ S+n +N n ⊆ C n
である．P ΩP T ≥ O を満たす対角行列 Ω が存在するか
果は十分でないため，今後より効果的な分割規則の開
発が必要である．
参考文献
[1] E. de Klerk and D. V. Pasechnik, “Approximation
of the stabirity number of a graph via copositive programming,” SIAM Journal on Optimization, 12, 875–
892, 2002.
[2] J. Sponcel, S. Bundfuss, and M. Dur, “An adaptive linear approximation algorithm for copositive programs,” Journal of Global Optimization, 52, 537–551,
2012.
[3] T. S. Motzkin and E. G. Straus, “Maxima for graphs
and a new proof of a theorem of Turan,” Canadian
Journal of Mathematics, 17, 533–540, 1965.
[4] K. G. Murty and S. N. Kabadi, “Some NP-complete
problems in quadratic and nonlinear programming,”
Mathmatical Programming, 39, 117–129, 1987.
否かを判定するために，以下の線形計画問題を考える．
(PA )
min
Ω，θ
s.t.
2013 年 12 月号
θ
Ω≤Λ
P ΩP T + θE ≥ O
θ≥0
c by ORSJ. Unauthorized reproduction of this article is prohibited.（67）
Copyright 753

Download Report