半正定値計画とその応用^{1}

第１回半正定値計画問題の基礎

東京工業大学大学院情報理工学研究科

小島政和

2000 年 4 月

1 はじめに

最適化問題 (数理計画問題) は大ざっぱに

(i) 凸型連続最適化問題（線形計画問題，凸型２次計画問題，半正定値計画問題等）

(ii) 非凸型連続最適化問題（非凸型２次計画問題，一般の非線形計画問題等）

(iii) 組合せ最適化問題（整数計画問題，最大クリーク問題，巡回セールスマン問題等）

に分類される．凸型連続最適化問題は他の２つと比べると，解くのが容易で，理論，計算手法の両面でも充実している． Karmarkar 法を契機として急速に発展した線形計画問題に対する内点法も凸型連続最適化問題全体に拡張されている [11]．このクラスの問題の特徴は，局所的な最適解が大域的な最適解となることであり，局所的に目的関数を改善する通常の最適化手法 (内点法もそのような手法の一種) で大域的最適解を計算することが可能である．他方，非凸型連続最適化問題と組合せ最適化問題では局所的な最適解が大域的な最適解になるとは限らず，各反復で局所的に目的関数を改善する最適化手法だけでは大域的な最適解に到達するのは難しい．

半正定値計画問題 (Semidefinite Programming Prob -lem) は凸型連続最適化問題のクラスに属し，線形計画問題と凸型２次計画問題をその特殊場合として含む．この問題の特徴は

(a) モデル記述能力が高い

(b) 上記 (ii) および (iii) のクラスの問題の最適値を見積もるためにの緩和問題として利用可能

(c) 内点法が適用可能にある．

1日本オペレーションズ・リサーチ学会誌掲載予定

(a) に関連しては，特に対称行列の固有値に関する条件を含めることが可能である．安定な制御システムの設計，建造物の構造最適化，不確実性を持った数理計画問題に対するロバスト最適化，データマイニング等に応用されている ([1,2,3,4,14,15] 等参照)．従来は， (b) で述べた緩和のために線形計画問題が使われてきたが，半正定値計画問題も多項式時間で解くことができ，かつ，線形計画問題による緩和よりも，理論的に優れた特徴を有していることが示されて以来 ([5,10] 等参照)， (b) に関する研究が盛んに行われるようになった．さらに， (c) により実用規模の半正定値計画問題が効率よく解けることが示されるにつれ，半正定値計画問題の応用範囲も広がっていった．これらの特徴は，数理計画法，システムと制御，構造最適化等のさまざまな分野の研究者の交流を深めることに寄与している．

本講座は合計４回の連載で第２回目以降は，以下のように， (b) の話題を取り上げる．

第２回半正定値計画による緩和 (1)

(神戸商科大学藤江哲也)

第３回半正定値計画による緩和 (2)

(神戸商科大学藤江哲也)

第４回半正定値計画を用いた近似アルゴリズム (中央大学浅野孝夫)

線形計画法を始めとする数理計画法では線形代数の知識が必要であるが，そこでは Euclid 空間におけるベクトル変数が主役で，行列はその線形変換として登場した．半正定値計画問題においては対称行列が変数で，対称行列からなる線形 (ベクトル) 空間の上で議論が展開される．さらに，２次形式，固有値等のより高度な線形代数の知識を要求される．これらのことが，半正定値計画問題を取っつき難くしている．半正定値計画問題に関する和文文献もすでにいくつかあり ([3,7,8,9,12,13] 等)，半正定値計画問題の応用，内点法等が解説されている．しかしながら，それらの文献では半正定値計画問題の根底にある数学的基礎にふれていないか，あるいは，それらの知識を前提として書かれている．そこで，本講座の第１回目の今回は半正定値計画問題を線形代数の基礎まで掘り下げて説明することとした．予備知識としては理工系の大学の１年生のときに習う線形代数 (線形空間，２次形式，固有値等) をうっすらと憶えている (あるいは，忘れかけている) 程度を仮定している．ここでは半正定値計画問題そのものの数学的基盤の解説を目的としている．応用や内点法に興味がある読者も，他の文献と本稿を合わせて読むことにより，それらの話題の理解がより深まることを願っている．

2 半正定値計画問題

等式標準形線形計画問題

\begin{matrix}目的： & ∑_{j=1}^{n} c_{j}x_{j} → 最小化 \\ 条件： & ∑_{j=1}^{n} a_{ij}x_{j} = b_{i} (i = 1, 2, …, m), \\ & x_{j} ≥ 0 (j = 1, 2, …, n) \end{matrix} \}

から始めよう．ただし， b_{i}, a_{ij}, c_{j} ∈ R (実数の集合) は定数， x_{j} ∈ R は変数．半正定値計画問題は， n × n 実対称行列

X = [X_{ij}] = ( \begin{matrix}X_{11} & X_{12} & ⋯ & X_{1n} \\ X_{21} & X_{22} & ⋯ & X_{2n} \\ ⋯ & ⋯ & ⋯ & ⋯ \\ X_{n1} & X_{n2} & ⋯ & X_{nn} \end{matrix} ) ,

ただし X_{ij} = X_{ji},

からなる線形 (ベクトル) 空間 S^{n} への線形計画問題の拡張である．この意味を明確にするために，上記の等式標準形線形計画問題を

\begin{matrix}目的： & a_{0} · x → 最小化 \\ 条件： & a_{i} · x = b_{i} (i = 1, 2, …, m), \\ & x ≥ 0 \end{matrix} \}  (1)

と書き換える．ただし，

a_{0} ≡ (c_{1}, c_{2}, …, c_{n})^{T} ∈ R^{n},
a_{i} ≡ (a_{i1}, a_{i2}, …, a_{in})^{T} ∈ R^{n},
x ≡ (x_{1}, x_{2}, …, x_{n})^{T} ∈ R^{n},
x ≥ 0 ⇔ x_{j} ≥ 0 (j = 1, 2, …, n),
u · v ≡ ∑_{j=1}^{n} u_{j}v_{j} (u, v ∈ R^{n} の内積),
T : ベクトルまたは行列の転置

(紙面の都合で縦ベクトルを横ベクトルの転置で表す)

を表す．次に，等式標準形線形計画問題 (1) において，

a_{i} ∈ R^{n} ⇒ A_{i} ∈ S^{n} (n × n 対称行列の空間)
x ∈ R^{n} ⇒ X ∈ S^{n}
· ⇒ • (行列の内積)
x ≥ 0 ⇒ X ⪰ O (半正定値条件)

の置き換えを行うと等式標準形半正定値計画問題

\begin{matrix}目的： & A_{0} • X → 最小化 \\ 条件： & A_{i} • X = b_{i} (i = 1, 2, …, m), \\ & X ⪰ O \end{matrix} \}  (2)

が得られる．これで形式的には半正定値計画問題の定義が完了したわけであるが，以下では，未定義な記号 “•”, “⪰” の説明，および，この問題を支える数学的基盤を順次説明する．

2.1 対称行列からなる線形空間

m×n 行列全体 R^{m×n} はスカラー倍と行列の和が定義された線形（ベクトル）空間である．すなわち， m×n 行列 A = [A_{ij}] のスカラー倍 (α 倍) と２つの m×n 行列 A = [A_{ij}], B = [B_{ij}] の和が，それぞれ，

αA ≡ [αA_{ij}], A + B ≡ [A_{ij} + B_{ij}]

で定義されている．さらに， A ∈ R^{m×n} をその n 本の m 次元縦ベクトルを縦に並べた mn 次元縦ベクトル

vec(A) ≡ (A_{11}, …, A_{m1}, …, A_{1n}, …, A_{mn})^{T}

と対応させると， R^{m×n} は mn 次元 Euclid 空間とみなすこともできる． E^{ij} で (i, j) 要素のみが 1 で他の要素はすべて 0 の m × n 行列を表すと， mn 個の行列

E^{ij} (i = 1, 2, …, m, j = 1, 2, …, n)

は R^{m×n} の基底をなしている．さらに，２つの行列 A, B ∈ R^{m×n} の内積

A • B ≡ vec(A) · vec(B) = ∑_{i=1}^{m} ∑_{j=1}^{n} A_{ij}B_{ij}

が， mn 次元 Euclid 空間の内積として，自然に導入される．内積を使うと行列 A ∈ R^{m×n} のノルム (Frobenius ノルムと呼ばれる)

∥A∥_{F} ≡ (A • A)^{1/2} = (∑_{i=1}^{m} ∑_{j=1}^{n} A_{ij}^{2})^{1/2}

も定義される．このようにして， R^{m×n} は mn 次元 Euclid 空間と等価な線形空間になる．

明らかに， n × n 対称行列の集合 S^{n} は線形空間 R^{n×n} の部分集合であり，かつ，上述した代数演算 (行列のスカラー倍と和) も S^{n} の中で閉じている．すなわち，任意の α ∈ R, A, B ∈ S^{n} に対して αA ∈ S^{n}, A + B ∈ S^{n} が成り立つ．したがって， S^{n} は R^{n×n} 線形部分空間になっている．自明な直交基底としては， n(n + 1)/2 個の n × n 対称行列

(E^{ij} + E^{ji}) (1 ≤ i ≤ j ≤ n)

が取れる． R^{n×n} は n^{2} 次元 Euclid 空間と見なせるから， S^{n} もそこに埋め込まれた n(n+1)/2 次元の線形部分空間と見なすことができる．

2.2 対称行列に関する線形関数，線形写像

一般に， f : R^{n} → R^{k} が，任意のα, β ∈ R, x, y ∈ R^{n} に対してf(αx+βy) = αf(x)+βf(y) を満たすとき線形写像であるという．特に， k = 1 のときには線形関数， n = k のときには線形変換とよばれることも多い． R^{n} から R^{k} への線形写像 f は k × n 定数行列 M を用いて， f(x) = Mx (∀x ∈ R^{n}) と，また， R^{n} 上の線形関数 g は n 次元定数ベクトル a との内積を用いて g(x) = a · x (∀x ∈ R^{n}) と表現できることが知られている．

前節で述べたように m × n 行列 A を mn 次元ベクトル vec(A) に対応させることにより， m × n 行列の空間 R^{m×n} を mn 次元 Euclid 空間とみなすことができる．このことは Euclid 空間で定義した線形写像，線形関数，線形変換が R^{m×n} に流用できることを意味している．したがって， R^{m×n} 上の線形写像 f と線形関数 g は，それぞれ，

f(X) = Mvec(X),  (3)
g(X) = A • X = vec(A) · vec(X)

と表現できる．ここで， M は k × mn 定数行列， A は m × n 定数行列．

R^{n×n} 上の線形関数 g(X) = A • X を n × n 対称行列の空間 S^{n} に限定すると，

A • X = ((A + A^{T})/2) • X (∀X ∈ S^{n})

が成り立つ．ここで ((A + A^{T})/2) は対称行列となる．したがって， S^{n} 上の線形関数 f は， n × n 定数対称行列 A を用いて

g(X) = A • X (∀X ∈ S^{n})

と表現できる．等式標準形半正定値計画問題 (2) においても，係数行列 A_{i} が対称であることを仮定している．

しかしながら，行列に関する線形写像はさまざまな形で現れる．例えば， AXB +CXD は， X に関する線形写像である．ただし， A, B, C, D は定数行列で上記の行列の積と和が矛盾無く行えることを仮定する．行列のクロネッカー積を用いると，このような写像も行列を Euclid 空間に対応させることにより (3) のように表現できる．詳しくは [6] 等参照．

2.3 半正定値性 — 対称行列の非負性

n 次元 Euclid 空間 R^{n} における “非負” は， n × n 対称行列の空間 S^{n} では “半正定値”(非負値，非負定値とも言う) に置き換えられる． X ∈ S^{n} に対する２次形式 u^{T} Xu が，すべての u ∈ R^{n} に対して非負な値を取るとき，すなわち， u^{T} Xu ≥ 0 (∀u ∈ R^{n}) であるとき，半正定値であるという．また，２次形式 u^{T} Xu が，すべての非ゼロな u ∈ R^{n} に対して正な値を取るとき，正定値 (または，正値) であるという． n = 1 であるときには， X は実数になり，実数 X が，それぞれ，非負あるいは正であることと一致する．

n × n 対称行列 X の固有値 (重複度を考慮に入れると n 個) はすべて実数であり，

半正定値 ⇔ 固有値がすべて非負
正定値 ⇔ 固有値がすべて正

であることが知られている．この事実は X がその固有ベクトルを列ベクトルとして並べた直交行列 P (P P^{T} = P^{T} P = 単位行列となる正方行列) によって，以下のように対角化できることから導かれる．

P^{T} XP = Λ ≡ ( \begin{matrix}λ_{1} & 0 & ⋯ & 0 \\ 0 & λ_{2} & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & λ_{n} \end{matrix} )

ここで， λ_{1}, λ_{2}, …, λ_{n} は X の固有値である．実際，

X が半正定値
⇔ u^{T} Xu ≥ 0 (∀u ∈ R^{n})
⇔ v^{T} P^{T} XP v ≥ 0 (∀v ∈ R^{n})
⇔ ∑_{i=1}^{n} λ_{i}v_{i}^{2} ≥ 0 (∀v ∈ R^{n})
⇔ λ_{i} ≥ 0 (i = 1, 2, …, n))

が成り立つ． X が正定値の場合も同様である．

半正定値計画問題の文献では， X ∈ S^{n} が半正定値，あるいは，正定値の場合に，それぞれ， X ⪰ O, あるいは， X ≻ O と書くことが多い．等式標準形半正定値計画問題 (2) でもこの記号を用いた．

3 線形行列不等式系と一般の半正定値計画問題

一般に，通常の線形不等式系に対称行列の変数を導入し，それに対する半正定値条件を許した線形不等式系を線形行列不等式 (Linear Matrix Inequality, [2] 参照) と呼ぶ．例えば，

∑_{i=1}^{q−1} A_{i}x_{i} + (A_{q}Y_{1} + Y_{1}A_{q}) + Y_{2} = A_{0},
S^{n} ∋ Y_{1} ⪰ O, S^{n} ∋ Y_{2} ⪰ O,
x_{i} ≥ 0 (i = 1, 2, …, q − 1),

(ただし, A_{i} ∈ S^{n} は定数行列 (i = 0, …, q))や

( \begin{matrix}A^{T} X + XA + Q & XB \\ B^{T} X & C \end{matrix} ) ⪰ O

(ただし, A ∈ R^{n×n}, Q ∈ R^{n×n}, B ∈ R^{n×m}, O ≺ C ∈ S^{m} は定数行列, X ∈ S^{n} は変数行列) は線形行列不等式である．このような線形行列不等式を半正定値計画問題の条件として含めることができる．

必要ならばスラック変数を導入し，また， s × t 矩形行列を st-次元ベクトルと同一視する等により，複数個のユークリッド空間のベクトル x_{1}, x_{2}, …, x_{q}, 対称行列 Y_{1}, Y_{2}, …, Y_{r} の線形写像 G と定数ベクトル b を用いて，一般の線形行列不等式を

G(x_{1}, x_{2}, …, x_{q}, Y_{1}, Y_{2}, …, Y_{r}) = b,
x_{j} ≥ 0 (j = 1, 2, …, p),
Y_{k} ⪰ O (k = 1, 2, …, r)

と表現できる．ただし， 1 ≤ p ≤ q である．線形計画問題の場合と同様に，どのような半正定値計画問題も適当な変換を施すことによって等式標準形に帰着することができ，理論的には等式標準形半正定値計画問題 (2) で議論すれば十分である (しかし，等式標準形への帰着は簡単ではない)．

4 半正定値行列からなる凸錐

線形計画問題と半正定値計画問題の差は非負条件 “x ≥ 0” と半正定値条件 “X ⪰ O” にある (2.2 節で述べたように線形等式条件については本質的な差は無い)．この２つの類似点と違いをより詳しく考察するために，非負ベクトルの集合 R_{+}^{n} と半正定値行列の集合 S_{+}^{n} を導入する．

R_{+}^{n} ≡ {x ∈ R^{n} : x ≥ 0},
S_{+}^{n} ≡ {X ∈ S^{n} : X ⪰ O}

まず， S_{+}^{n} が R_{+}^{n} と共有する重要な性質を指摘する．

S_{+}^{n} は凸錐である．すなわち，任意の λ, μ ≥ 0, X, Y ∈ S_{+}^{n} に対して， λX + μY ∈ S_{+}^{n} が成り立つ．この性質が，不等号 “⪰” が S^{n} 上の半順序で，かつ，代数演算 (スカラー倍と和) と矛盾がないこと，すなわち，

X_{1} ⪰ X_{2}, Y_{1} ⪰ Y_{2} ⇒ X_{1} + Y_{1} ⪰ X_{2} + Y_{2},
X_{1} ⪰ X_{2}, α ≥ 0 ⇒ αX_{1} ⪰ αX_{2}

であることを保証している．ここで， A ⪰ B は A − B ⪰ O の意味．

S_{+}^{n} は閉集合である．このことが不等号 ‘⪰” が連続であること，すなわち，

X_{k} ⪰ Y_{k}, X_{k} → X̄, Y_{k} → Ȳ ⇒ X̄ ⪰ Ȳ

が成り立つことを保証している．

S_{+}^{n} は自己双対である．すなわち，

{Y ∈ S^{n} : X • Y ≥ 0 (∀X ∈ S_{+}^{n})} = S_{+}^{n}

が成立する．言い換えると，

Y ⪰ O ⇔ X • Y ≥ 0 (∀X ∈ S_{+}^{n})

が成立する．さらに，任意の X ⪰ O と Y ⪰ O に対して，

X • Y = 0 ⇔ XY = O  (4)

も成り立つ (右側は XY ∈ R^{n×n} がゼロ行列の意味)．自己双対性は任意に与えた半正定値計画問題の双対問題 (5 節で述べる) が半正定値計画問題になることを保証している．

これまで述べてきた半正定値計画問題と線形計画問題の類似点は線形計画問題に対する主双対内点法の半正定値計画問題への拡張において主要な役割を果たしている．

R_{+}^{n} は n 個の線形不等式

x_{j} ≥ 0 (j = 1, 2, …, n)

で囲まれた多面集合である．他方， S_{+}^{n} を表現するには，無限個の線形不等式，例えば

( v^{T} Xv = ) X • vv^{T} ≥ 0 (∀v ∈ B),
ただし B ≡ {v ∈ R^{n} : ∥v∥ = 1},

を必要とする．言い換えると， S_{+}^{n} は “非線形な” 凸集合である．端線が無限個存在し，それらが連続的につながっている．このような違いが障害となって，有限個の頂点をそれらを結ぶ稜線を通ってたどる単体法は半正定値計画問題には拡張できず，内点法のような非線形な方法が必須となる理由もここにある．

5 双対問題，双対定理，相補性定理

等式標準形線形計画問題 (1) の双対問題は

\begin{matrix}目的： & ∑_{i=1}^{m} b_{i}y_{i} → 最大化 \\ 条件： & ∑_{i=1}^{m} a_{i}y_{i} + z = a_{0}, \\ & z ≥ 0 \end{matrix} \}  (5)

である．一方，等式標準形半正定値計画問題 (2) の双対問題は

\begin{matrix}目的： & ∑_{i=1}^{m} b_{i}y_{i} → 最大化 \\ 条件： & ∑_{i=1}^{m} A_{i}y_{i} + Z = A_{0}, \\ & Z ⪰ O \end{matrix} \}  (6)

で与えられる．これら２つの問題を比較すると，対応する主問題を比較したときと同様に，

a_{i} ∈ R^{n} ⇒ A_{i} ∈ S^{n}
z ∈ R^{n} ⇒ Z ∈ S^{n}
z ≥ 0 ⇒ Z ⪰ O

と置き換わっていることが分かる．半正定値計画問題の主問題 (2) と (6) の間には以下の定理が成り立つ．

定理１．

(i) 主問題 (2) の任意の許容解 X ∈ S^{n} と双対問題 (6) の任意の許容解 (y, Z) ∈ R^{m} × S^{n} に対して

双対問題の目的関数値 = ∑_{i=1}^{m} b_{i}y_{i}
≤ A_{0} • X = 主問題の目的関数値.

(弱双対定理)

(ii) 主問題 (2) の内点許容解 X ∈ S^{n}(条件 X ≻ O を満たす許容解 X ∈ S^{n}) と，双対問題 (6) の内点許容解 (y, Z) ∈ R^{m} × S^{n} (条件 Z ≻ O を満たす許容解 (y, Z) ∈ R^{m} × S^{n}) が存在すると仮定する．このとき，主問題 (2) の許容解 X^{∗} ∈ S^{n} が最適解で，かつ，双対問題 (6) の許容解 (y^{∗}, Z^{∗}) ∈ R^{m} × S^{n} が最適解であるための必要十分条件は主問題と双対問題の目的関数値が一致することである：

∑_{i=1}^{m} b_{i}y_{i}^{∗} = A_{0} • X^{∗} .

(強双対定理)

(iii) (ii) と同様の仮定をする．主問題 (2) の許容解 X^{∗} ∈ S^{n} が最適解で，かつ，双対問題 (6) の許容解 (y^{∗}, Z^{∗}) ∈ R^{m} × S^{n} が最適解であるための必要十分条件は相補性条件

X^{∗}Z^{∗} = O  (7)

が成り立つことである． (相補性定理)

これら結果 (i), (ii), (iii) は線形計画問題の主問題 (1) と双対問題 (5) の間に成り立つ弱双対定理，強双対定理，相補性定理の一般化になっている．ただし， (ii), (iii) においては，線形計画問題の場合には必要のない “内点許容解の存在” が仮定されている．この仮定は，非線形の凸計画問題でしばしば用いられる Slater の制約想定と同種で， S_{+}^{n} が多面集合でないことに起因している．

(4) より，相補性条件 (7) は， X^{∗} • Z^{∗} = 0 とも書ける．また，主問題 (2) の任意の許容解 X ∈ S^{n} と双対問題 (6) の任意の許容解 (y, Z) ∈ R^{m} × S^{n} に対して

A_{0} • X − ∑_{i=1}^{m} b_{i}y_{i}

= (∑_{i=1}^{m} A_{i}y_{i} + Z) • X − ∑_{i=1}^{m} (A_{i} • X) y_{i}
= X • Z ≥ 0

であることが検証できる．このことより，弱双対定理，および，強双対定理と相補性定理の等価性が導かれる．

相補性条件 (7) の両辺の転置を取ることにより，

X^{∗}Z^{∗} = Z^{∗}X^{∗} = O

が導かれる．このことは主問題 (2) の任意の最適解 X^{∗} ∈ S^{n} と双対問題 (6) の任意の最適解 (y^{∗}, Z^{∗}) ∈ R^{m} × S^{n} において，互いに双対をなしている変数対称行列 X^{∗} と Z^{∗} が交換可能であることを意味している．交換可能な２つの対称行列は共通の直交行列によって対角化できることが知られている．したがって，ある直交行列 P ∈ R^{n×n} が存在して，

P^{T} X^{∗}Z^{∗}P
= P^{T} X^{∗}P P^{T} Z^{∗}P
= ( \begin{matrix}λ_{1} & ⋯ & 0 \\ ⋮ & ... & ⋮ \\ 0 & ⋯ & λ_{n} \end{matrix} ) ( \begin{matrix}μ_{1} & ⋯ & 0 \\ ⋮ & ... & ⋮ \\ 0 & ⋯ & μ_{n} \end{matrix} )
= O.

したがって， X^{∗} 固有値 λ_{1}, λ_{2}, …, λ_{n} と Z^{∗} の固有値 μ_{1}, μ_{2}, …, μ_{n} の間に相補性条件

λ_{j} ≥ 0, μ_{j} ≥ 0, λ_{j}μ_{j} = 0 (j = 1, 2, …, n)

が成り立っていることが分かる．

6 おわりに

本稿では数学的な基礎に焦点を絞って半正定値計画問題の紹介を行った．応用および計算手法に関して興味のある読者は文献 [3,7,8,9,12,13,14,15] 等を参照されたい．この講座の次回以降では組合せ最適化問題への応用に関する解説がなされる．また，以下のホームページでも半正定値計画法に関連する情報が得られる．いずれも文献データベースおよびこの分野の研究者リストを含んでいる．

http://www-unix.mcs.anl.gov/otc/InteriorPoint/ http://www.zib.de/helmberg/semidefinite.html

参考文献

[1] Ben-Tal, A. and Nemirovski, A., “Robust convex programming,” Mathematics of Operations Research, 23 (1998) 769–805.

[2] Boyd, S., Ghaoui, L. E., Feron, E. and Balakrishnan, V., Linear Matrix Inequalities in System and Control Theory, (SIAM, Philadelphia, 1994).

[3] 藤沢克樹, “SDPA(半正定値計画問題に対するソフトウエア)”, オペレーションズ・リサーチ 45 (2000) 125-131.

[4] Fujisawa, K., Hamuro, Y., Katoh N., Tokuyama, T., and Yada, K., “Approximation of optimal two-dimensional association rules for categorical attributes using semidefinite programming”, The Proceedings of the Second International Conference on Discovery Science, (Springer, Berlin, 1999) 148–159.

[5] Goemans, M. X., and Williamson, D. P., “Improved approximation algorithms for maximum cut and satisability problems using semidenite programming”, Journal of Assoc. Comput. Mach., 42 (1995) 330–343.

[6] Graham, A., Kronecker Products and Matrix Calculus with Applications, (Ellis Horwood Limited, John Willey & Sons, New York, 1981).

[7] 小島政和, “半正定値計画問題と内点法”, 応用数理 6 (1996) 270-279.

[8] 小島政和, “半正定値計画の組み合わせ最適化への応用に向けて”, オペレーションズ・リサーチ 40 (1997) 216-221.

[9] 小島政和, “半正定値計画とその組合せ最適化への応用”, 離散構造とアルゴリズム５，近代科学社 (1998) 203-249.

[10] Lovasz, L., and Schrijver, A. , “Cones of matrices and set functions and 0-1 optimization,” SIAM J. on Optimization 1 (1991) 166–190.

[11] Nesterov, Ju. E., and Nemirovskii, A. S., Interior Point Polynomial Methods in Convex Programming: Theory and Applications, (SIAM, Philadelphia,1993).

[12] 進藤晋, “半正定値計画法 (SDP) – 主双対内点法アルゴリズム –”, シミュレーション 16 (1997) 46–52.

[13] 土谷隆, “最適化アルゴリズムの新展開 – 内点法とその周辺 – I 〜 VIII (連載)”, システム／制御／情報 42 (1998), 43 (1999).

[14] Vandenberghe, L., and Boyd, S., ”Semidefinite Programming”, SIAM Review 38 (1996) 49–95.

[15] Wolkowicz, H., Saigal, R., and Vandenberghe, H., Handbook on Semidefinite Programming, (Kluwer Academic Publishers, 2000).