1. はじめに．

表題に含まれる内点法は，線形計画問題（Linear Program, LP と略）を解く新解法として 1984 年に提案された Karmarkar 法 [10] を契機としている． LP は最も基本的な数理計画問題で，その数値解法である単体法（シンプレックス法）とともに G. B. Dantzig によって 1947 年に提案されて以来，オペレーションズ・リサーチの分野で強力な数理モデルとして主要な役割を果たしてきた．この問題では，線形等式および不等式条件のもとで線形の目的関数を最小化（または最大化）する．標準形の LP は以下のように定式化される．

\begin{matrix}目的 & c^{T} x → 最小化 \\ 条件 & Ax = b, x ≥ 0. \end{matrix} \}  (1)

ただし， R^{n} : n 次元ユークリッド空間， c ∈ R^{n} : 定数ベクトル， x ∈ R^{n} : 変数ベクトル， A : m × n 定数行列， b ∈ R^{m} : 定数ベクトルであり， T はベクトルまたは行列の転置を表す．

内点法はこの 10 年間にめざましい発展を遂げている．特に，主・双対内点法 [11, 22] は従来の単体法では解けなかったような超大規模な LP を高速に解く計算手法として確立され（[15] 等参照），凸２次計画問題，凸計画問題等のより高度な数理計画問題にも拡張されている（[12, 16] 等参照）．主題である半正定値計画問題（Semidefinite Program, SDP と略）は凸計画問題の一種で， LP に対する内点法の基礎理論が非常に美しい形で拡張されている [1, 9, 13, 16, 17, 23] 他． SDP の研究は主として，

(a) SDP を用いた緩和（組み合わせ最適化， 0-1 整数計画，非凸２次計画への応用） [1, 4, 6, 7, 14, 18, 19] 他，

(b) システムと制御への応用 [3, 8] 他，

(c) SDP に対する内点法 [1, 2, 9, 13, 16, 17, 23] 他，

の３つの方向からなされてきている．本稿では (a) と (c) に焦点を絞って解説を行う．第２節では SDP を LP と対比させながら記述し SDP の特徴について述べる．第３節では上記 (a) について，第４節では上記 (c) について述べる．

2. 半正定値計画問題．

2.1. 線形計画問題と半正定値計画問題．

SDP （半正定値計画問題）との比較を明確にするために， LP （線形計画問題）の標準形 (1) とその双対問題を通常とは少し違った形で表現する：

\begin{matrix}主問題 & 目的 & a_{0} • x → 最小化 \\ & 条件 & a_{i} • x = b_{i} (i = 1, 2, …, m), \\ & & R^{n} ∋ x ≥ 0. \\ 双対問題 & 目的 & ∑_{i=1}^{m} b_{i}z_{i} → 最大化 \\ & 条件 & ∑_{i=1}^{m} a_{i}z_{i} + y = a_{0}, \\ & & R^{n} ∋ y ≥ 0. \end{matrix} \}  (2)

ただし， a_{i} ∈ R^{n} (i = 0, 1, 2, …, m) : 定数ベクトル， b_{i} ∈ R (i = 1, 2, …, m) : 実定数， z_{i} ∈ R (i = 1, 2, …, m) : 実変数， u • v : u, v ∈ R^{n} の内積である．

SDP の等式標準形の主問題とその双対問題は，上記の LP (2) の主問題とその双対問題を対称行列の空間に拡張した問題といえる．

\begin{matrix}主問題 & 目的 & A_{0} • X → 最小化 \\ & 条件 & A_{i} • X = b_{i} (i = 1, 2, …, m), \\ & & S^{n} ∋ X ⪰ O. \\ 双対問題 & 目的 & ∑_{i=1}^{m} b_{i}z_{i} → 最大化 \\ & 条件 & ∑_{i=1}^{m} A_{i}z_{i} + Y = A_{0}, \\ & & S^{n} ∋ Y ⪰ O. \end{matrix} \}  (3)

ただし，

S^{n} : n × n 実対称行列の空間，

O ∈ S^{n} : ゼロ行列，

A_{i} ∈ S^{n} (i = 0, 1, 2, …, m) : 定数行列， b_{i} ∈ R (i = 1, 2, …, m) : 実定数， X ∈ S^{n}, Y ∈ S^{n} : 変数行列， z_{i} ∈ R (i = 1, 2, …, m) : 実変数，

U • V : U, V ∈ S^{n} の内積 ∑_{i=1}^{n} ∑_{j=1}^{n} U_{ij}V_{ij}，

U ⪰ O ⟺ U ∈ S^{n} が半正定値．

LP (2) のデータ a_{i} ∈ R^{n}, (i = 0, 1, 2, …, m) と変数ベクトル x ∈ R^{n}, y ∈ R^{n} に対して，それらを対角成分にもつ n × n 対角行列を

A_{i} = Diag a_{i} (i = 0, 1, 2, …, m), X = Diag x, Y = Diag y

と定義すると， LP (2) を SDP (3) に埋め込むことができる．これによって， LP (2) を SDP (3) の特殊な場合とみなし， LP (2) と SDP (3) の理論および計算手法を同じ土俵で議論することができる． U ∈ S^{n} が正定値であるとき， U ≻ O と記す．以下では， SDP (3) の主問題と双対問題をひとまとめにして扱うことが多い． (X, Y , z) が SDP (3) のすべての制約条件を満たすとき，許容解であるという．さらに，許容解 (X, Y , z) が条件 X ≻ O, Y ≻ O を満たすとき，内点許容解と呼ぶ．また， X が主問題の最小解で， (Y , z) が双対問題の最大解であるとき， (X, Y , z) は SDP (3) の最適解であるという．

2.2. 半正定値計画問題の特徴．

SDP は凸計画問題の特殊な場合であり，線形計画問題，凸２次計画問題を含んでいる．以下のような特徴がある．

• 目的関数（主問題） A_{0} • X は線形． • 等号条件（主問題） A_{i} • X = b_{i} は線形．

• “非負条件” X ⪰ O （主問題）， Y ⪰ O （双対問題）は非線形．

線形計画問題と異なるのは最後の特徴であるが， SDP において “非負条件” を満たす集合（すなわち，半正定値行列の集合）

S_{+}^{n} = {X ∈ S^{n} : X ⪰ O}

が，線形計画問題において非負条件を満たす x の集合（すなわち，非負象限） R_{+}^{n} = {x ∈ R^{n} : x ≥ 0} と非常によく似た以下のような構造をしている．

• S_{+}^{n} = {X ⪰ O} は閉凸錐．

• X, Y ∈ S_{+}^{n} ⇒ \{ \begin{matrix}X • Y ≥ 0, \\ X • Y = 0 ⇔ XY = O. \end{matrix}

• {Y ∈ S^{n} : X • Y ≥ 0 for ∀X ∈ S_{+}^{n}} = S_{+}^{n} （自己双対性）．

LP と似たこのような SDP の性質は， LP に対する内点法を SDP に拡張する際に本質的な役割を果たしている．

2.3. 双対定理．

(X, Y , z) を SDP (3) の許容解とすると，主問題の目的関数値 A_{0} •X と双対問題の目的関数値 ∑_{i=1}^{m} b_{i}z_{i} の間に，不等式

X • Y = A_{0} • X − ∑_{i=1}^{m} b_{i}z_{i} ≥ 0

が常に成り立つ（弱双対性）．したがって，それらの目的関数値が一致すれば, あるいは， X • Y = 0 （相補性条件）が成り立てば， (X, Y , z) は SDP (3) の最適解であることが分かる．以下の双対定理はこの逆を保証している．

定理 2.1. （[16], Theorem 4.2.1 参照） SDP (3) に内点許容解が存在すると仮定する．このとき，

(i) SDP (3) に最適解が存在する．

(ii) SDP (3) の許容解 (X^{∗}, Y^{∗}, z^{∗}) が最適解であるための必要十分条件は主問題と双対問題の目的関数値が一致することである．すなわち，

X^{∗} • Y^{∗} = A_{0} • X^{∗} − ∑_{i=1}^{m} b_{i}z_{i}^{∗} = 0

この双対定理は SDP (3) の理論の中核をなしている． LP (2) の場合と比較すると定理の仮定が少し強くなっている（ LP (2) の場合には許容解の存在を仮定すれば十分である）．

2.4. 半正定値計画問題の一般形．

2.1 節では SDP の標準形とその双対問題を導入した．応用上はさまざまな形の SDP が現れる．より一般的には，複数個のユークリッド空間のベクトル x_{1}, x_{2}, …, x_{p}，矩形行列 Y_{1}, Y_{2}, …, Y_{q}，対称行列 Z_{1}, Z_{2}, …, Z_{r} の線形関数を目的関数とし，これらを含む線形関数に関する等式，不等式（LMI, Linear Matrix Inequality と呼ばれる， [3] 参照）を条件に含めることが出来る． LP の場合と同様に，どのような SDP も適当な変換を施すことによって標準形に帰着することができ，理論的には標準形で議論すれば十分である．しかしながら， LP の場合と違って標準形への帰着はさほど自明ではなく，強引に標準形に帰着しようとするとそのサイズが非常に大きくなってしまう場合がある．そのような場合には，その問題を標準形に帰着するのではなく，標準形に対して開発された数値解法をその問題に適した形に変更したほうが計算効率がよい．

3. 半正定値計画問題を用いた緩和．

SDP による緩和は主として組み合わせ最適化の分野で， 0-1 整数計画問題（0-1 Integer Program，以下 0-1 IP と略）を対象として研究されている（[1, 6, 7, 14, 18] 他）．その基本的な考え方は２次計画問題（Quadratic Program，以下 QP と略）の緩和に拡張されている（[4, 18, 19] 他）． 3.1 節では， [4] に基づいて QP の SDP による緩和について説明し， 3.2 節では 0-1 IP の QP への帰着について述べる．

3.1. ２次計画問題の SDP 緩和．

ここでは，以下の QP について考える．

\begin{matrix}目的： & c^{T} y → 最小化 \\ 条件： & y ∈ F. \end{matrix} \}  (4)

ただし，

\begin{matrix}F & ≡ & \{y ∈ H : \begin{matrix}y^{T} P_{k}y & = & 0 (k = 1, 2, …, ℓ), \\ y^{T} P_{k}y & ≤ & 0 (k = ℓ + 1, …, m) \end{matrix} \} , \\ H & = & \{y = ( \begin{matrix}y_{0} \\ x \end{matrix} ) ∈ R^{1+n} : y_{0} = 1\} , c ≡ ( \begin{matrix}γ \\ d \end{matrix} ) ∈ R^{1+n}, \\ P_{k} & ≡ & ( \begin{matrix}π_{k} & q_{k}^{T} /2 \\ q_{k}/2 & Q_{k} \end{matrix} ) ∈ S^{1+n} (k = 1, 2, …, m), \\ π_{k} & ∈ & R, q_{k} ∈ R^{n}, Q_{k} ∈ S^{n} (k = 1, 2, …, m). \end{matrix} \}  (5)

定義より，任意の y = ( \begin{matrix}y_{0} \\ x \end{matrix} ) ∈ H に対して， y^{T} P_{k}y = π_{k} + q_{k}^{T} x + x^{T} Q_{k}x となる．したがって， Q_{k} = O

（または， Q_{k} ∈ S_{+}^{n}）のとき，かつ，そのときに限って, 関数 H ∋ y → y^{T} P_{k}y ∈ R は線形（または，凸）であることが分かる． QP (4) の目的関数 c^{T} y は線形である．したがって， QP (4) を凸計画問題

\begin{matrix}目的：c^{T} y → 最小化 \\ 条件：y ∈ coF \end{matrix} \}  (6)

で置き換えることができる．ここで， coF は F の凸包を表す．しかしながら，一般には coF を計算可能な形に表現することは難しく，凸計画問題 (6) を解くことはできない．ここで，

\begin{matrix}C & ≡ & ( \begin{matrix}γ & d^{T} /2 \\ d/2 & O \end{matrix} ) ∈ S^{1+n}, \\ Ĝ & ≡ & \{Y ∈ S_{+}^{1+n} : \begin{matrix}Y_{00} = 1, \\ P_{k} • Y = 0 (k = 1, 2, …, ℓ), \\ P_{k} • Y ≤ 0 (k = ℓ + 1, …, m), \end{matrix} \} , \\ F̂ & ≡ & \{y ∈ R^{1+n} : y = Y e_{0}, Y ∈ Ĝ\} , \\ e_{0} & ≡ & (1, 0, 0, …, 0)^{T} ∈ R^{1+n} \end{matrix} \}  (7)

で定義し， SDP

\begin{matrix}目的： & C • Y → 最小化 \\ 条件： & Y ∈ Ĝ \end{matrix} \}  (8)

とその R^{1+n} への “射影”

\begin{matrix}目的： & c^{T} y → 最小化 \\ 条件： & y ∈ F̂ \end{matrix} \}  (9)

を導入する． C, Ĝ, F̂ の作り方より，

Ĝ ⊆ S_{+}^{1+n} : 凸集合, F̂ ⊆ R^{1+n} : 凸集合,
[y ∈ F , Y = yy^{T}] ⇒ c^{T} y = C • Y , Y ∈ Ĝ, y ∈ F̂ ,
F ⊆ coF ⊆ F̂

であることが分かる．ゆえに， (9) は QP (4) の緩和問題であり， (9) の最小解は SDP (8) を解くことによって計算できる．特に，

Q_{k} = O (k = 1, 2, …, ℓ), Q_{k} ∈ S_{+}^{1+n} (k = ℓ + 1, …, m)

のときには， F = coF = F̂ となり， SDP (8) を解くことにより QP (4) の最小解を求めることができる．

上述した QP (4) の SDP 緩和は， QP (4) の Lagrange 緩和および Lagrange 双対問題と関連づけることができる．実際，条件

Y ≻ O, Y_{00} = 1,
P_{k} • Y = 0 (k = 1, 2, …, ℓ),
P_{k} • Y < 0 (k = ℓ + 1, …, m)

を満たす点 Y （SDP (8) の内点許容解）が存在するとき， SDP (8) の最小値は QP (4) の Lagrange 双対問題

\begin{matrix}目的： & min\{c^{T} y + ∑_{k=1}^{m} λ_{k}y^{T} P_{k}y : y ∈ H\} → 最大化 \\ 条件： & λ_{i} ∈ R (i = 1, 2, …, ℓ), 0 ≤ λ_{k} ∈ R (k = ℓ + 1, …, m) \end{matrix} \}

の最適値と一致する．ただし， λ_{k} (k = 1, 2, …, m) は Lagrange 乗数である．より詳しくは [4] 参照．

3.2. 0-1 整数計画問題の非凸２次計画問題への帰着．

一般の 0-1 IP は以下のような２次計画問題として書ける．

\begin{matrix}目的： & c^{T} y → 最小化 \\ 条件： & y_{0} = 1, y_{0}a_{j}^{T} y ≤ 0 (j = 1, 2, …, ℓ), \\ & y_{i}(y_{i} − y_{0}) = 0 (i = 1, 2, …, n). \end{matrix} \} ,  (10)

この問題 (10) は QP (4) の特殊な場合とみなせるから，前節で述べた SDP 緩和をこの問題に適用できる．しかしながら，問題 (10) から導かれる SDP 緩和は， LP 緩和

\begin{matrix}目的： & c^{T} y → 最小化 \\ 条件： & y_{0} = 1, a_{j}^{T} y ≤ 0 (j = 1, 2, …, ℓ), \\ & 0 ≤ y_{i} ≤ 1 (i = 1, 2, …, n) \end{matrix} \} ,  (11)

と一致してしまい， SDP 緩和を用いる効果はない． SDP 緩和の効果を出すためには 0-1 IP の許容領域が満たす２次不等式

−y_{i}y_{k} ≤ 0 (i = 1, 2, …, n, k = 1, 2, …, n),
y_{i}a_{j}^{T} y ≤ 0 (i = 1, 2, …, n, j = 1, 2, …, ℓ),
(y_{0} − y_{i})a_{j}^{T} y ≤ 0 (i = 1, 2, …, n, j = 1, 2, …, ℓ),
−y_{i}(y_{0} − y_{k}) ≤ 0 (i = 1, 2, …, n, k = 1, 2, …, n),
−y^{T} a_{j}a_{k}^{T} y ≤ 0 (= 1, 2, …, ℓ, k = 1, 2, …, ℓ)

を少なくともいくつか加える必要がある．これらの不等式は QP (10) にとっては冗長であるが， SDP 緩和を構成する際には重要な役割を果たす．理論的には， SDP 緩和は LP 緩和よりも強力である．特殊な 0-1 IP として定式化できる最大安定集合問題，グラフ分割問題等では計算実験も報告されている．しかしながら，上述した２次不等式の多くを加えてできる SDP 緩和問題はその規模が非常に大きくなってしまい，現時点では一般の 0-1 IP への SDP 緩和の適用は実用的であるとは言えない． SDP 緩和をさらに LP で緩和することも行われている．詳しくは [1, 4, 6, 7, 14, 18, 20, 21] 等参照．

4. 内点法．

Karmarkar 法 [10] を起点として発展した線形計画問題に対する内点法（[10, 11, 12, 15, 22] 等）が SDP (3) に拡張されている（[1, 2, 5, 9, 13, 16, 17, 23]）．ここでは， [2, 13] に基づき，実用上重要と思われる許容解でない初期点から出発できる主・双対内点法の基本的な考え方について簡単に説明する．

4.1. 中心パスと探索方向．

SDP (3) が内点許容解をもつと仮定する．このとき，任意の μ > 0 に対して，条件

A_{i} • X = b_{i} (i = 1, 2, …, m), S^{n} ∋ X ≻ O,

∑_{i=1}^{m} A_{i}z_{i} + Y = A_{0}, S^{n} ∋ Y ≻ O, XY = μI

を満たす (X(μ), Y (μ), z(μ)) = (X, Y , z) が存在する（[13] 等参照）．ただし， I は単位行列を表す．その集まり C ≡ {(X(μ), Y (μ), z(μ)) : μ > 0} は中心パスと呼ばれ，許容領域の内部を通って SDP (3) の最適解に収束する滑らかな曲線となる．中心パス C 上の各 (X(μ), Y (μ), z(μ)) は SDP の内点許容解であり，

nμ = X(μ) • Y (μ) = A_{0} • X(μ) − ∑_{i=1}^{n} b_{i}z(μ)_{i}

を満たす．したがって， μ > 0 が十分小さければ (X(μ), Y (μ), z(μ)) は SDP (3) の近似最適解となる（定理 2.1）．主・双対内点法（[2, 5, 9, 13, 17] 等）はこの曲線を，非線形方程式系に対するニュートン法を適用して，数値的に追跡する方法としてとらえることができる．

4.2. 主・双対内点法．

X^{0} ≻ O, Y^{0} ≻ O を満たす初期点 (X^{0}, Y^{0}, z^{0}) を選ぶ．以下では， k − 1 番目の反復で X^{k} ≻ O, X^{k} ≻ O を満たす点 (X^{k}, Y^{k}, z^{k}) が生成されたと仮定し， k 番目の反復について説明する． μ^{k} = X^{k} • Y^{k}/n と置く．

A_{i} • X^{k} − b_{i} (i = 1, 2, …, m), ∑_{i=1}^{m} A_{i}z_{i}^{k} + Y^{k} − A_{0}, μ^{k}

がすべて十分に小さい値を達成していれば， (X^{k}, Y^{k}, z^{k}) は SDP (3) の近似最適解になっているからこの時点で反復をやめる．そうでなければ探索方向パラメータ β ∈ [0, 1] を選び，次の反復点のための標的 (X(βμ^{k}), Y (βμ^{k}), z(βμ^{k})) （β > 0 のときには，中心パス上の点， β = 0 のときには SDP の最適解（β → 0 の極限））を決める．その標的が満たす方程式系は

A_{i} • X = b_{i} (i = 1, 2, …, m), ∑_{i=1}^{m} A_{i}z_{i} + Y = A_{0}, XY = βμ^{k}I

となるが，３番目の方程式 XY = βμ^{k}I が非線形であるため正確な解を計算することは出来ない．そこで， Newton 法を適用すると探索方向 (U, V , w) に関する線形方程式系

A_{i} • U = b_{i} − A_{i} • X^{k} (i = 1, 2, …, m),  (12)
∑_{i=1}^{m} A_{i}w_{i} + V = A_{0} − ∑_{i=1}^{m} A_{i}z_{i}^{k} − Y^{k},  (13)
X^{k}V + UY^{k} = βμ^{k}I − X^{k}Y^{k}  (14)

X^{k}V + UY^{k} + (X^{k}V + UY^{k})^{T} = 2βμ^{k}I − X^{k}Y^{k} − Y^{k}X^{k}  (14)’

S^{k}V + U(S^{k})^{−1} = βμ^{k}S^{k}(X^{k})^{−1} − S^{k}Y^{k}  (14)”

S^{k} = (X^{k})^{1/2}((X^{k})^{1/2}Y^{k}(X^{k})^{1/2})^{−1/2}(X^{k})^{1/2} 新しい反復点は，ステップ長 α_{p}, α_{d} ∈ [0, 1] を

X^{k} + α_{p}U ≻ O, Y^{k} + α_{d}V ≻ O

を満たすように適当に選んで

(X^{k+1}, Y^{k+1}, z^{k+1}) = (X^{k} + α_{p}U, Y^{k} + α_{d}V , z^{k} + α_{d}w)

で定める．例えば，

ᾱ_{p} = max{α ∈ [0, 1] : X^{k} + αU ⪰ O},
ᾱ_{d} = max{α ∈ [0, 1] : Y^{k} + αV ⪰ O},

を計算して，

(X^{k+1}, Y^{k+1}, z^{k+1}) = (X^{k} + γᾱ_{p}U, Y^{k} + γᾱ_{d}V , z^{k} + γᾱ_{d}w)

とすればよい．ただし， γ ∈ (0, 1) は定数．

主・双対内点法の計算効率，大域的な収束性，および，局所的な収束性は，各反復での探索方向パラメータ β とステップ長 α_{p}, α_{d} の取り方に依存する．最良の計算の複雑度としては以下の結果が知られている．初期点 (X^{0}, Y^{0}, z^{0}) が内点許容解で，中心パスに十分に近いと仮定する．このとき，各反復で探索方向パラメータとステップ長を β = (1 − 0.1/\sqrt{n}), α_{p} = α_{d} = 1 にとると， O(\sqrt{n} log(X^{0} • Y^{0}/ϵ)) 回の反復後に，条件 0 ≤ A_{0} • X^{k} − ∑_{i=1}^{m} b_{i}z_{i}^{k} ≤ ϵ を満たす近似解 (X^{k}, Y^{k}, z^{k}) が得られる．詳しくは， [13, 17] 等参照．

5. おわりに．

SDP が盛んに研究され始めたのはここ２〜３年のことである．まだ，雑誌に掲載されていなかったり，ここでは紹介しなかった重要な論文も多い．また，本稿ではごく基本的なことしか紹介していない． SDP および内点法に関するより最新の情報は， Internet を通して以下に接続することにより得られるので，興味ある読者は参照されたい．

• http://www.mcs.anl.gov/home/otc/InteriorPoint — LP および SDP の内点法に関する情報．

• http://rutcor.rutgers.edu:80/˜ alizadeh — Alizadeh の SDP に関するホームページ．

• http://cs.nyu.edu/cs/faculty/overton/sdpevopt.html — Overton の SDP に関するホームページ．

• http://www.zib-berlin.de/˜ bzfhelmb/semidef.html — Helmberg の SDP に関するホームページ．

• http://www.is.titech.ac.jp/labs/kojimalab/kojima/sdp.html — 著者のグループによる論文 [4, 13] およびソフトウエア [5] 等．

このサーベイ論文を勧めて下さった土谷隆先生，論文を読んで貴重なコメントを下さった田村明久先生，村松正和先生，中田和秀君に感謝します．

参考文献

[1] W. F. Alizadeh, “Interior point methods in semidefinite programming with application to combinatorial optimization,” SIAM Journal on Optimization 5 (1995) 13–51.

[2] W. F. Alizadeh, J.-P. Haeberly and M. L. Overton, “Primal-dual interior-point methods for semidefinite programming,” Computer Science Department, Rutgers University, Berkeley, August, 1994

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

[4] T. Fujie and M. Kojima, “Semidefinite relaxation for nonconvex programs,” Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152, Japan, May 1995, Revised March 1996.

[5] K. Fujisawa and M. Kojima, “SDPA (Semidefinite Programming Algorithm) – User’s Manual –,” B-308, Dept. of Mathematics and Computing Sciences, Tokyo Institute of Technology, Meguro, Tokyo 152, 1995.

[6] M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” Journal of Assoc. Comput. Mach. to appear.

[7] M. Grötschel, L. Lovász and A. Schrijver, Geometric algorithms and combinatorial optimization (Springer, New York, 1988).

[8] 原辰次， “ロバスト制御理論の動向 – 実用的な制御設計法を目指して –， ” Proceedings of the 38th Annual conference of the ISCIE (1994) 25–27.

[9] C. Helmberg, F. Rendl, R. J. Vanderbei and H. Wolkowicz, “An interior-point method for semidefinite programming,” SIAM Journal on Control and Optimization 掲載予定．

[10] N. Karmarkar, “A new polynomial-time algorithm for linear programming,” Combinatorica 4 (1984) 373–395.

[11] M. Kojima, S. Mizuno and A. Yoshise, “A primal-dual interior point algorithm for linear programming,” In N. Megiddo, ed., Progress in Mathematical Programming, Interior-Point and Related Methods (Springer-Verlag, New York, 1989) 29–47.

[12] M. Kojima, N. Megiddo, T. Noma and A. Yoshise, A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Sciecnes 538 (Springer-Verlag, New York, 1991).

[13] M. Kojima, S. Shindoh and S. Hara, “Interior-point methods for the monotone semidefinite linear complementarity problems,” SIAM Journal on Optimization 掲載予定．

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

[15] I. J. Lustig, R. E. Marsten and D. F. Shanno, “Interior point methods for linear programming: Computational state of the art,” ORSA Journal on Computing 6 (1994) 1–14.

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

[17] Ju. E. Nesterov and M. J. Todd, “Self-scaled cones and interior-point methods in nonlinear programming,” Working Paper, CORE, Catholic University of Louvain, Louvain-la-Neuve, Belgium, April 1994.

[18] S. Poljak, F. Rendl and H. Wolkowicz, “A recipe for semidefinite relaxation for (0,1)-quadratic programming,” Global Optimization 7 (1995) 51–73.

[19] M. V. Ramana, An algorithmic analysis of multiquadratic and semidefinite programming problems, PhD thesis, Johns Hopkins University, Baltimore, MD, 1993.

[20] H. D.Sherali and A. R.Alameddine, “A new reformulation-linearization technique for bilinear programming problems,” Journal of Global Optimization 2 (1992) 379–410.

[21] H. D.Sherali and and C. H.Tuncbilek, “A reformulation-convexification approach for solving nonconvex programming problems,” Journal of Global Optimization 7 (1995) 1–31.

[22] K. Tanabe, “Centered Newton method for mathematical programming,” In M. Iri and K. Yajima, eds., Systems Modeling and Optimization (Springer-Verlag, New York, 1988) 197-206.

[23] L. Vandenberghe and S. Boyd, “A primal-dual potential reduction method for problems involving matrix inequalities,” Mathematical Programming, Series B 69 (1995) 205–236.