半正定値計画の組合せ最適化への応用に向けて

東京工業大学情報理工学研究科 小島政和 （Masakazu Kojima）

1. はじめに．

G. B. Dantzig が線形計画問題（Linear Program, LP と略）とその数値解法である単体法（シンプレックス法）を提案したのは，今から５０年ほど前である．それ以来，単体法は，コンピュータや過粗行列に対する線形計算技術等の進歩に支えられられて，着実な発展を遂げ，オペレーションズ・リサーチの最も基本的な手法として主要な役割を果たしてきた． Karmarkar 法 [6] が出現したのは１９８４年である．単体法は「許容領域を形成する多面体の頂点通って最適解に到達する」のに対して， Karmarkar 法は「許容領域の内部を横切って最適解に接近する」という全く別の考え方に基づいている．この１０年間に， Karmarkar 法が生み出した “内点法” は長足の進歩を遂げている．特に，双対定理を内点法に取り込んだ主・双対内点法は単体法を凌ぐほどに成長し，超大規模な線形計画問題を高速に解く手法として確立している（[10] 等参照）．

タイトルに含まれる半正定値計画 (Semidefinite Program, SDP と略) に内点法を最初に拡張したのは Nesterov-Nemirovskii [11] の仕事である．彼らは新しい概念 “self-concordance” を導入し，この性質を満たすように内点罰金関数あるいはポテンシャル関数が構成できる凸計画問題を対象として内点法の一般理論を展開した． SDP はそのような凸計画問題の一種で， LP に対する内点法の基礎理論が非常に美しい形で拡張されている（SDP およびそれを解くための内点法に関しては文献 [7] を参照）．

SDP は組合せ最適化の分野 [3, 4, 9, 他] でも盛んに研究されている． SDP の魅力は線形を越えた記述能力にあり，組合せ最適化問題の緩和に使用されたときには，従来の LP 緩和より理論的に優れていることが知られている．しかし，これまでの研究では最大クリーク問題，最大カット問題等の特殊な組合せ最適化問題に対する理論的な成果が誇張され，より一般的な組合せ的最適化問題の中での SDP の役割に関して論じたものは少ない．本稿の目的は組合せ最適化問題および非凸型２次計画問題に対する SDP 緩和の基本的な原理を解説することにある．

第２節では，対象とする組合せ最適化問題について記述した後に， SDP が担う役割である緩和とその重要性について述べる．第３節では，第４節以降の議論を統一的に行うために，組合せ最適化問題を特殊な非凸型２次計画問題に帰着する．第４節では非凸型２次計画問題の３種類の緩和， Lagrange 双対問題，凸２次不等式を用いる緩和，および， SDP 緩和について議論する．そこでは，この３種類の緩和のなかで SDP 緩和が最強であることが述べられる．第５節では，第４節の主要結果を 0-1 整数計画問題の SDP 緩和に応用する．第３，４，５節の内容は論文 [1] に基づいている．

2. 組合せ最適化問題と緩和問題．

2.1. 組合せ最適化問題．

R^{n} で n 次元空間を表す． R^{n} の点 x は縦ベクトルとするが，その第 j 要素 x_{j} との対応をとるときには，紙面を節約するために， x = (x_{1}, x_{2}, …, x_{n}) と記す．数理計画問題は R^{n} の各点 x = (x_{1}, x_{2}, …, x_{n}) で実数値をとる関数 f と， S_{0} ⊆ R^{n} の組を使って，

P_{0} 目的：f(x) → 最小化; 条件：x ∈ S_{0}

と表される． f を目的関数， S_{0} を許容領域と呼ぶ．また，条件 x ∈ S_{0} を満たす x を許容解，許容解のなかで目的関数を最小にする x を最小解あるいは最適解と呼ぶ．数理計画問題は目的関数 f と許容領域 S_{0} の性質によって，さまざまなに分類されている．本稿が対象とする組合せ最適化問題は，許容領域 S_{0} を記述する際に

x_{i} は 0 または 1,  (1)
x_{i} = 0 または x_{j} = 0,  (2)
A^{k}x ≤ b^{k} (1 ≤ k ≤ m) の少なくとも１つを満たす  (3)

等の組合せ的な条件を含むような数理計画問題である．施設配置問題，巡回セールスマン問題，２次割当問題，さまざまなスケジューリング問題等の実用上重要な非常に多くの問題がこのような制約条件の下で線形または２次の目的関数を最小化する組合せ最適化問題に定式化されることが知られている．

2.2. 緩和問題 — その役割および重要性．

組合せ最適化問題は非凸型最適化問題と並んで難しい数理計画問題とされている．線形計画問題に対する単体法あるいは内点法のような万能手法はなく，個々の問題の特性を利用したさまざまな解法が提案されている．特に，規模の大きい組合せ最適化問題では正確な最適解を計算することは困難で，近似的な最適解で我慢せざるを得ない．そのような問題を対象とする解法では

(i) より小さい目的関数値 f(x) を達成する許容解 x ∈ S_{0} を生成する仕組み

が盛り込まれており（[8] 等参照），計算を打ち切った時点までに求めた許容解のなかで最小の目的関数値を達成する許容解 x̂ を “近似最適解” として採用する．しかし，これだけでは求めた “近似最適解” がどれだけ良いかが判断できない． f(x̂) よりもはるかに小さい目的関数値を達成する許容解があるかもしれない．この不安を打ち消すためには

(ii) 未知の最小値を見積もる仕組み

が必要となる．緩和問題はその仕組みの１つとして重要な役割を果たしている．

条件 S_{0} ⊆ S̃_{0}, かつ g(x) ≤ f(x) (∀x ∈ S_{0}) を満たす R^{n} の部分集合 S̃_{0} と実数値関数 g : R^{n} → R に対して，数理計画問題

P̃_{0} 目的：g(x) → 最小化; 条件：x ∈ S̃_{0}

を考える．元の問題 P_{0} と比較すると， P̃_{0} の許容領域 S̃_{0} は広く， P̃_{0} の目的関数 g は元の許容領域 S_{0} 内で元の目的関数 f を下から支えている．したがって， P_{0} の未知の最小値を f^{∗}， P̃_{0} の最小値を g^{∗} とすると， g^{∗} ≤ f^{∗} であることが分かる．すなわち， P̃_{0} の最小値 g^{∗} は P_{0} の未知の最小値 f^{∗} の下界値を与える．このように作られた P̃_{0} を P_{0} の緩和問題と呼ぶ．

緩和問題 P̃_{0} から得られる P_{0} の最小値 f^{∗} の下界値 g^{∗} は以下のように使われる． P_{0} の “近似最小解” （と思われる） x̂ ∈ S_{0} が求まったと仮定すると， g^{∗} ≤ f^{∗} ≤ f(x̂) が成り立つ．したがって， f(x̂) − g^{∗} が十分小さいか，許容範囲にあれば， “近似最小解” x̂ ∈ S_{0} を安心して使えることになる．当然，緩和問題は

• その最小値 g^{∗} が元の問題 P_{0} の未知の最小値 f^{∗} に近いこと，および，

• 簡単に解けることが望ましいが，この２つ両立させるのは難しい場合が多い．

2.3. 分枝限定法と緩和問題．

分枝限定法は組合せ最適化問題に対する汎用的な手法としてよく知られている．この手法では問題 P_{0} の許容領域 S_{0} をその部分集合 S_{k} (1 ≤ k ≤ ℓ) の和集合で表し，すなわち， S_{0} = ∪_{k=1}^{ℓ}S_{k} として， P_{0} をより規模の小さい ℓ 個の問題

P_{k} 目的：f(x) → 最小化; 条件：x ∈ S_{k}

(1 ≤ k ≤ ℓ) で置き換える． P_{k} を P_{0} の子問題， P_{0} を P_{k} の親問題と呼ぶ． S_{0} = ∪_{k=1}^{ℓ}S_{k} より，子問題 P_{k} (1 ≤ k ≤ ℓ) をすべて解けば，それらの親問題 P_{0} が解けることが分かる．より正確には，各子問題 P_{k} の最小解を x^{k}，目的関数値を f^{k} = f(x^{k}) とすると，それらの中で最小の目的関数値 f^{k} を達成している x^{k} が親問題 P_{0} の最小解となる．このように１つの問題をいくつかの子問題に “分解する操作” を分枝操作と呼ぶ．

これらのすべての子問題が解ければ元の問題 P_{0} が解けるはずであるが，いくつかの（あるいは，すべての）子問題はそれらの規模がまだ大きいために解けない可能性が高い．そこで，各子問題に対して， (A) その子問題の最小解が求まる，あるいは， (B) その子問題には許容解が存在しないことが分かる，あるいは， (C) 元の問題 P_{0} を解くためには，その子問題を解かなくてもよいことが分かるまで分枝操作を繰り返す．

(B)， (C) を限定操作と呼ぶ．それらの判定においては緩和問題が主要な役割を果たす．分枝限定法の途中の段階までに計算した最良の目的関数値（暫定最小値）を達成する P_{0} の許容解を x̂ とする．このとき，対象とする子問題の緩和問題に許容解がないならば，上記の (B) を導ける．また，その緩和問題の最小値 g^{∗} が g^{∗} ≥ f(x̂) を満たせば (C) を結論できる（その時点までに得られている最良の許容解 x̂ よりも，その子問題の最小解は良くなる可能性がない）．後者は下界値テストと呼ばれている．下界値テストが有効に働いて，分枝操作の早い時点で多くの子問題をさらに小さく分枝する前に終端することができれば，分枝限定法の計算効率は高まる．そのためには，より小さい暫定最小値を早い時点で見つけると同時に，各子問題のより大きい下界値を計算効率よく生成することが重要となる（分枝限定法について詳しくは [5] 等参照）．

3. 組合せ最適化から非凸型２次計画へ．

この節では前節で述べた (1), (2) および (3) ような組合せ的な条件のもとで，２次の目的関数を最小化する問題を導入し，それを特殊な非凸型２次計画問題に帰着する．次節ではその非凸型２次計画問題の緩和について論じる．

２次関数を用いると多くの組合せ的な条件が表現できる．例えば，前節の条件 (1), (2) および

(3) は，それぞれ，

x_{i}(x_{i} − 1) = 0,  (1)’
x_{i}x_{j} = 0,  (2)’
∑_{k=1}^{m} y_{k} ≥ 1, y_{k}(1 − y_{k}) = 0, y_{k}(A^{k}x − b^{k}) ≤ 0 (1 ≤ k ≤ m)  (3)’

これらの条件は，一般的な２次不等式または２次等式

x^{T} Qx + q^{T} x + π ≤ 0 または = 0  (4)

で表せる．ただし，

x ∈ R^{n} : 変数,

Q : n × n 対称行列, q ∈ R^{n}, π ∈ R : 定数, T : ベクトルと行列の転置を表す.

また，このような条件の下で２次の目的関数を最小化する問題は，制約条件に不等式 “２次の目的関数” ≤ t を加えれば，目的関数を t に置き換えられる．したがって， (4) のような２次不等式条件または２次等式条件のもとで２次関数を最小化する問題では，目的関数を線形関数としても一般性を失わない．

さらに，変数 y_{0} を導入すると (4) は

x^{T} Qx + y_{0}q^{T} x + πy_{0}^{2} ≤ 0 または = 0 y_{0} = 1  (4)’

と書き直せる．そこで，これ以後の議論では，以下のような２次計画問題（QP と略）を考える．

\begin{matrix}目的： & q_{0}^{T} x → 最小化 \\ 条件： & x^{T} Q_{i}x + q_{i}^{T} y_{0}x + π_{i}y_{0}^{2} ≤ 0 (1 ≤ i ≤ ℓ), \\ & x^{T} Q_{k}x + q_{k}^{T} y_{0}x + π_{k}y_{0}^{2} = 0 (ℓ < k ≤ m), y_{0} = 1. \end{matrix} \}  (5)

ただし，

\begin{matrix}x ∈ R^{n} : 変数, \\ Q_{i} : n × n 対称行列, q_{i} ∈ R^{n}, π_{i} ∈ R : 定数 \end{matrix}

次節以降のために以下の記号を導入しておく．

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

S_{+}^{n} : n × n 半正定値対称行列の空間,

F = \{y ∈ H : \begin{matrix}y^{T} P_{i}y ≤ 0 (1 ≤ i ≤ ℓ), \\ y^{T} P_{k}y = 0 (ℓ < k ≤ m) \end{matrix} \} ,

H = {y = (y_{0}, x) ∈ R^{1+n} : y_{0} = 1} ,

Q_{0} = O ∈ S^{n}, π_{0} = 0 ∈ R,

P_{k} = ( \begin{matrix}π_{k} & q_{k}^{T} /2 \\ q_{k}/2 & Q_{k} \end{matrix} ) ∈ S^{1+n} (0 ≤ k ≤ m).

これらの記号を使うと， QP (5) は

目的：y^{T} P_{0}y → 最小化; 条件：y ∈ F  (5)’

と書き直せる．定義より，任意の y = (y_{0}, x) ∈ H に対して， y^{T} P_{k}y = π_{k} + q_{k}^{T} x + x^{T} Q_{k}x となる．したがって， Q_{k} ∈ S_{+}^{n} （または， Q_{k} = O）のとき，かつ，そのときに限って，２次関数 H ∋ y → y^{T} P_{k}y ∈ R は凸（または，線形）であることが分かる．特に， QP (5)’ の目的関数 y^{T} P_{0}y は

y^{T} P_{0}y = q_{0}^{T} x (∀y = (y_{0}, x) ∈ H)

を満たし， H 上で線形である． (1)’, (2)’ および (3)’ のような組合せ的な条件から導かれる y^{T} P_{k}y ≤ 0 あるいは y^{T} P_{k}y = 0 では y^{T} P_{k}y の H 上での凸性や線形性は満たされない．

4. 非凸型２次計画問題の緩和．

この節以降では， QP (5)’ の条件に表れる y^{T} P_{k}y の線形性や凸性を仮定しない一般の非凸型２次計画問題を扱う．議論を簡単にするために QP (5)’ の許容領域 F は有界で，かつ，空でないと仮定する．

QP (5)’ の目的関数 y^{T} P_{0}y は H ⊇ F 上で線形である．したがって，許容領域 F をその凸包 coF （F を含む最小の凸集合）に取り替えた凸計画問題

目的：y^{T} P_{0}y → 最小化; 条件：y ∈ coF  (6)

は QP (5)’ と同じ最小値を達成し， “理想的な緩和” になっている．一般には coF を計算可能な形に表現することは難しく，凸計画問題 (6) を解くことはできない．以下では， “より具体的な緩和” である Lagrange 緩和，無限個の凸２次不等式を用いた緩和，および， SDP 緩和について論ずる．これらの緩和のうち， SDP 緩和が， QP (5)’ の最良の下界値を達成し，かつ，内点法によって解くことが出来る．いわゆる Slater 条件（制約想定）の下では，この３つの緩和は QP (5)’ の同じ下界値を与える．最初の２つの緩和はその最小値を計算するのは困難であるが， SDP 緩和を調べるのに有用である．

4.1. Lagrange 緩和．

QP (5)’ の Lagrange 乗数ベクトル λ の集合 Λ と Lagrange 関数 L : H × Λ → R を

Λ = {λ ∈ R^{m} : λ_{i} ≥ 0 (1 ≤ i ≤ ℓ)} ,
L(y, λ) = y^{T} P_{0}y + ∑_{k=1}^{m} λ_{k}y^{T} P_{k}y

で定義し， QP (5)’ の Lagrange 緩和問題

目的：L(y, λ) → 最小化; 条件：y ∈ H  (7)

を導入する．この問題 (7) では λ ∈ Λ は外から与えるパラメータで，最小値は λ の選び方に依存する． QP (5)’ と問題 (7) を比較すると，それらの許容領域は F ⊆ H を満たす．また，それらの目的関数の間には

y^{T} P_{0}y ≥ L(y, λ) (∀y ∈ F)

が成り立つ．よって問題 (7) は QP (5)’ の緩和問題になっている．

y ∈ H に関する２次目的関数 L(y, λ) が H 上で非凸になるような λ ∈ Λ を選んだ場合には，２次目的関数 L(y, λ) は H 上で −∞ に発散し， Lagrange 緩和問題 (7) から導かれる QP (5)’ の下界値は −∞ になる．したがって， Lagrange 緩和問題 (7) を考える際には， Lagrange 乗数ベクトル λ ∈ Λ の範囲を

Λ_{+} = {λ ∈ Λ : L(λ, ·) が H 上で凸}
= {λ ∈ Λ : ∑_{k=1}^{m} λ_{k}Q_{k} ∈ S_{+}^{n}}

に限定して差し支えない．そのような λ ∈ Λ_{+} の中で Lagrange 緩和問題 (7) の最小値が最大になるように λ を選びたい．すなわち，

目的：min{L(y, λ) : y ∈ H} → 最大化; 条件：λ ∈ Λ_{+}.  (8)

この問題は QP (5)’ の Lagrange 双対問題と呼ばれ， Lagrange 緩和問題 (7) の中で， QP (5)’ の最良の下界値を与える．

4.2. 凸２次不等式を用いた緩和．

前節では (8) を QP (5)’ の Lagrange 双対問題として導いた． (8) は，以下の半無限計画問題の Lagrange 双対問題にも対応している．

目的：y^{T} P_{0}y → 最小化; 条件：y ∈ F̃ . (9)

ただし，

F̃ = {y ∈ H : ∑_{k=1}^{m} λ_{k}y^{T} P_{k}y ≤ 0 (∀λ ∈ Λ_{+})}.

問題 (9) の許容領域 F̃ は H 上で無限個の凸２次不等式 ∑_{k=1}^{m} λ_{k}y^{T} P_{k}y ≤ 0 (λ ∈ Λ_{+}) で表されているので， F̃ は閉凸集合になる．また， y ∈ F ならば y ∈ F̃ ，すなわち， F ⊆ F̃ を満たす．よって， (9) は QP (5)’ の緩和になっている．

4.3. SDP 緩和．

行列 A, B ∈ S^{1+n} の内積を A • B = ∑_{i=0}^{n} ∑_{j=0}^{n} A_{ij}B_{ij} で表す．内積を使うと QP (5)’ の２次不

等式条件および２次等式条件の左辺 y^{T} P_{i}y は P_{i} • yy^{T} と一致し， QP (5)’ の許容領域 F は

F = \{Y e_{0} ∈ R^{1+n} : \begin{matrix}Y = yy^{T} , y ∈ H, \\ P_{i} • Y ≤ 0 (1 ≤ i ≤ ℓ), P_{k} • Y = 0 (ℓ < k ≤ m) \end{matrix} \}

と表現できる．ただし， e_{0} = (1, 0, 0, …, 0) ∈ R^{1+n} で，任意の y ∈ H に対して (yy^{T})e_{0} = y が成り立つ．さらに， “rank Y = 1, Y ∈ S_{+}^{1+n}, Y_{00} = 1” は，ある y ∈ H に対して Y = yy^{T} が成り立つための必要十分条件である．ただし， rank Y は行列 Y の階数を表す．したがって， QP (5)’ の許容領域 F は

F = \{Y e_{0} ∈ R^{1+n} : \begin{matrix}rank Y = 1, Y ∈ S_{+}^{1+n}, Y_{00} = 1, \\ P_{i} • Y ≤ 0 (1 ≤ i ≤ ℓ), P_{k} • Y = 0 (ℓ < k ≤ m) \end{matrix} \}

と書き直せる．ここで， F を記述する条件のうち， rank Y = 1 を除いた集合を

F̂ = \{Y e_{0} ∈ R^{1+n} : \begin{matrix}Y ∈ S_{+}^{1+n}, Y_{00} = 1, \\ P_{i} • Y ≤ 0 (1 ≤ i ≤ ℓ), P_{k} • Y = 0 (ℓ < k ≤ m) \end{matrix} \}

で定義する． F̂ の作り方より， F̂ は F を含む凸集合になり， QP (5)’ の SDP 緩和

目的：y^{T} P_{0}y → 最小化; 条件：y ∈ F̂  (10)

を得る．問題 (10) の最小解 y^{∗} を求めるには以下の SDP の最小解 Y^{∗} を計算し， y^{∗} = Y^{∗}e_{0} とすればよい．

目的：P_{0} • Y → 最小化; 条件：Y ∈ Ĝ  (11)

ただし，

Ĝ = {Y ∈ S_{+}^{1+n} : Y_{00} = 1, P_{i} • Y ≤ 0 (1 ≤ i ≤ ℓ), P_{k} • Y = 0 (ℓ < k ≤ m), }

問題 (10) の許容領域 F̂ ⊂ R^{1+n} は SDP の許容領域 Ĝ ⊂ S^{1+n} の R^{1+n} への射影 {Y e_{0} ∈ R^{1+n} : Y ∈ Ĝ} になっている．

4.4. ３種類の緩和の関係．

これまでに， QP (5)’ に関連して，凸計画問題 (6)， Lagrange 双対問題 (8) ，無限個の凸２次不等式を用いた緩和問題 (9)， SDP 緩和問題 (10) を導入した．これらの最小値および許容領域の関係は以下のようにまとめられる．

定理： (論文 [1] の Theorems 2.1, 2.2)

(i) F ⊆ coF ⊆ F̂ ⊆ F̃.

(ii) 条件

Y ≻ O, P_{i} • Y < 0 (1 ≤ i ≤ ℓ), Y_{00} = 1, P_{k} • Y = 0 (ℓ < k ≤ m)  (12)

を満たす点 Y （SDP (10) の内点許容解）が存在するとき（この仮定は穏当な仮定）， F̂ の閉包は F̃ に一致する．

(iii) inf_{y∈F̂} y^{T} P_{0}y ≥ inf_{y∈F̃} y^{T} P_{0}y ≥ sup_{λ∈Λ_{+}} inf_{y∈H} L(y, λ)

(iv) 条件 (12) を満たす点 Y が存在するとき， (iii) の不等号はすべて等号で満たされる．

ただし， F ： QP (5)’ の許容領域， F̃ ：凸２次不等式を用いた緩和問題 (9) の許容領域， F̂ ： SDP 緩和問題 (10) の許容領域， L(y, λ) ： Lagrange 関数．

この定理より，

• Lagrange 双対問題 (8) ，凸２次不等式を用いた緩和問題 (9)， SDP 緩和問題 (10) の３つの緩和のなかでは， SDP 緩和問題 (10) が最強，

• 条件 (12) を満たす点 Y が存在するときは，この３つの緩和は等価，

であることが分かる．さらに，

• SDP 緩和問題 (10) は内点法によって解ける

ことも重要である．しかしながら，

• SDP 緩和問題 (10) では元の QP (5)’ をどのように緩和しているのかが非常に見えにくく，緩和の性質を調べるには凸２次不等式を用いた緩和問題 (9) が一番分かりやすい．

ゆえに，計算は SDP 緩和問題 (10) で行って，緩和の性質を調べるのに凸２次不等式を用いた緩

和問題 (9) を用いるとよい． (9) が示唆するのは， ∑_{i=1}^{m} λ_{i}y^{T} P_{i}y ≤ 0 (λ ∈ Λ_{+}) の形をしたなるべ

く多くの，かつ，有効な凸２次不等式が生成出来るように QP (5) の許容領域を表現せよということになる．次節では 0-1 整数計画問題を例にとってこのことをもう少し詳しく説明する．

5. 0-1 整数計画問題の SDP 緩和．

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

目的：c^{T} y → 最小化; 条件：y_{0} = 1, y_{0}a_{j}^{T} y ≤ 0 (1 ≤ j ≤ ℓ), y_{i}(y_{i} − y_{0}) = 0 (1 ≤ i ≤ n).

(13)

この問題 (13) は QP (5) の特殊な場合とみなせるから，前節で述べた SDP 緩和（凸２次不等式を用いた緩和）をこの問題に適用できる．しかしながら，問題 (13) から導かれる SDP 緩和は， LP 緩和

目的：c^{T} y → 最小化; 条件：a_{j}^{T} y ≤ 0 (1 ≤ j ≤ ℓ), 0 ≤ y_{i} ≤ 1 (1 ≤ i ≤ n)  (14)

と一致してしまい， SDP 緩和（凸２次不等式を用いた緩和）を用いる効果はない．緩和の効果を出すためには， LP 緩和 (14) の制約条件に表れる１次不等式を２つ取り出してかけ合わせた２次不等式

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

を少なくともいくつか加える必要がある．これらの不等式は QP (13) にとっては冗長であるが，

前節で述べた “ ∑_{i=1}^{m} λ_{i}y^{T} P_{i}y ≤ 0 (λ ∈ Λ_{+}) の形をしたなるべく多くの，かつ，有効な凸２次不

等式が生成 ” するのに重要な役割を果たす．しかし，このように多くの２次不等式を加えた QP から出来る SDP 緩和問題はその規模が非常に大きくなってしまい，現状では解くことが難しい． SDP 緩和をより簡単な LP でさらに緩和することも提案されている（[12] 他）．

6. 今後の発展．

理論的には， SDP 緩和は LP 緩和よりも強力である． SDP のソフトウエアもも公開され（[2, 13] 等），最大クリーク問題，最大カット問題，グラフ分割問題，２次割当問題等対する計算実験も報告されている．しかしながら，現時点では一般の組合せ最適化問題への SDP 緩和の適用は実用レベルにあるとは言いがたい．その障害となっているのは “規模の大きい SDP を解くのは LP を解くのよりはるかに時間がかかる” ことにある．少なくとも， SDP を解くためのより強力なソフトウエアの開発とより強力な計算機能・計算能力を備えたハードウエアの出現をもうしばらく待たなければならい．さらに，そのようなソフトウエア・ハードウエア環境が整ったとき， SDP 緩和を分枝限定法，切除平面法，発見的手法等の他の手法とどのように適合させるかについての研究も必要となろう．

この原稿は，平成８年１１月１３日−１５日に京都大学数理解析研究所で行われた研究集会『科学技術における数値計算の理論と応用 II』の講究録の原稿，および，オペレーションズ・リサーチ誌の解説（ＯＲ研究の最前線）として書いた．ただし，研究集会で講演させていただいたのは『半正定値計画問題に対する主双対内点法』であり，この原稿に書いた内容に関しては少ししか説明しなかった．『半正定値計画問題に対する主双対内点法』に関しては [7] を参照されたい．研究集会へご招待下さった三井斌友先生およびオペレーションズ・リサーチ誌の解説を書くことを勧めて下さった水野真治先生に感謝いたします．また，福田光浩君は原稿を注意深く読んで誤りを指摘してくれました．ここに感謝いたします．

参考文献

[1] T. Fujie and M. Kojima, “Semidefinite relaxation for nonconvex programs,” Journal of Global Optimization 掲載予定．

[2] K. Fujisawa, M. Kojima and K. Nakata, “SDPA (Semidefinite Programming Algorithm) – User’s Manual –,” B-308, Dept. of Mathematics and Computing Sciences, Tokyo Inst. of Tech., Meguro, Tokyo 152, Dec. 1995, Revised Aug. 1996.

[3] M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” Journal of Assoc. Comput. Mach. 42 (1995) 1115–1145.

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

[5] 茨木俊秀，「組合せ最適化 – 分枝限定法を中心として –」，産業図書 (1983).

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

[7] 小島政和， “半正定値計画問題と内点法”，応用数理， 6 (1996) No.4 16–25.

[8] 久保幹雄，メタヒューリスティックス，室田一雄編，「離散構造とアルゴリズム IV」，近代科学社 (1995) 171–221.

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

[10] 水野真治， “内点法”，オペレーションズ・リサーチ Vol. 40 (1995)， (1) No.6 321–326， (2) No.7 376–381， (3) No.8 437–442， (4) No.9 508–512．

[11] Yu. E. Nesterov and A. S. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming (SIAM, Philadelphia, 1994).

[12] 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.

[13] K. C. Toh, M. J. Todd and R. H. Tütüncü, “SDPT3 – a MATLAB software package for semidefinite programming,” Department of Mathematics, National University of Singapore, Singapore, December 1996.

参考文献

[1] T. Fujie and M. Kojima, “Semidefinite relaxation for nonconvex programs,” Journal of Global Optimization 掲載予定．

[2] K. Fujisawa, M. Kojima and K. Nakata, “SDPA (Semidefinite Programming Algorithm) – User’s Manual –,” B-308, Dept. of Mathematics and Computing Sciences, Tokyo Inst. of Tech., Meguro, Tokyo 152, Dec. 1995, Revised Aug. 1996.

[3] M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” Journal of Assoc. Comput. Mach. 42 (1995) 1115–1145.

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

[5] 茨木俊秀，「組合せ最適化 – 分枝限定法を中心として –」，産業図書 (1983).

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

[7] 小島政和， “半正定値計画問題と内点法”，応用数理， 6 (1996) No.4 16–25.

[8] 久保幹雄，メタヒューリスティックス，室田一雄編，「離散構造とアルゴリズム IV」，近代科学社 (1995) 171–221.

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

[10] 水野真治， “内点法”，オペレーションズ・リサーチ Vol. 40 (1995)， (1) No.6 321–326， (2) No.7 376–381， (3) No.8 437–442， (4) No.9 508–512．

[11] Yu. E. Nesterov and A. S. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming (SIAM, Philadelphia, 1994).

[12] 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.

[13] K. C. Toh, M. J. Todd and R. H. Tütüncü, “SDPT3 – a MATLAB software package for semidefinite programming,” Department of Mathematics, National University of Singapore, Singapore, December 1996.