半正定値計画とその応用

第3回 半正足値計画による緩和（2）藤・江 哲也

1． はじめに入力

出力

前回に引続き「緩和問題としての半正定借計画」を取りあげろ．今回は，この話題の始まりであるLov乙szの論文［10］の紹介，そして，その後の展開についてまとめ為．なお，第2節，第3節の話題は川で詳しく紹介されている．

2．Shannon capacity
情報理論における通信路（channel）を考える．図1（左）は，入力アルファベットを（1，2，3，4，5），出力アルフ
ァベットを（A，β，C，β，β）とする通信路を表現する通図1：通信路線図（左）と5頂点ホールC5（右）信路線図である（一般に，入力アルファベット数と出力アルファベット数は等しくなくて良い）．さらに，例えよって，長さ1の最大入力数は要素数最大の安定集

ば入力が1であるときに出力がAと判定される確率が合の大きさに等しく，α（G）と書くことにする．特に1／2であることを示している．論文［12］の主題は，誤α（C5）＝2である．

り確率0の通信に関するものである．そこで，通信路次に長さ2の入力を考える．このとき，異なる2つ線図に村して，入力アルファベット集合を頂点集合Ⅴの人力壱1Jlと壱2J2が同じ出力になる可能性があるのとする無向グラフG＝（Ⅴβ）を考える．ただし，2頂は

点壱，ブ∈Ⅴに対して，壷に対する出力とブに対する出力が同じになる可能性があるとき枝で結ぶ（（壱，ブ）∈句．

「壱1＝壱2または（壱1，盲2）∈居」
かつ

図1（左）の場合，G＝（隼β）は図1（右）のようになる．
図1（右）のグラフは，ホールあるいはサイクルとよばれており，lVl＝5なのでC5と書くことにする．

「ム＝ブ2または（九メ2）∈β」となる場合である・そこで，頂点集合を（（壱，メ＝壱，J∈

ここで，与えられた通信路において，誤り確率0でⅤ），そして同じ出力になる可能性があるような相異あるような長さ1の入力を考える．例えば図1の場合，なる2頂点（壱1，力）と（転力）を枝で結んでできるグラ1と3が相異なる入力とすることができる．図1（右）のフG2を定義する．G2は，GとGの直積Gx GとようなグラフG＝（隼β）で考えると，して知られているものである．一般に，2つのグラフ任意の2頂点が枝で結ばれていないような

G＝（隼β）と∬＝（坊∫）の直積Gx∬は，頂点集合を伸，プ＝壱∈VJ∈打）とし，異なる2頂点（宜1，Jl）とⅤの部分集合gが相異なる人力とすることができる．グラフ理論で（五2，プ2）は「五1＝壱2または（盲1，ま2）∈β」かつ「ム＝プ2は，このような部分集合のことを安定集合（stableset）または（ム，J2）∈ダ」の場合に枝で結ばれているグラあるいは独立集合（independent set）とよんでいる．

フである．すると，誤り確率0である長さ2の最大入力数は，G2に関する要素数最大の安定集合の大きさ，

ふじえ てつや 神戸商科大学商経学部〒651−2103神戸市西区学園西町8−2−1
e−ma・il：fujie敗obe11C・aC．jp
2000年9月号

すなわちα（G2）に等しくなる．

C5の場合，（1，3）が安定集合であることから，4つの入力11，13，31，33を構成することができる．この方© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（39）459

法は，一般に適用できて諦≦⑳（C5）≦であることはわかった。［咽では5頂点以下のグラフ

α（α2）≧α（α）2であることがわかる。しかし，等号が成り立つとは限らない。実際，α（嘩）＝5（11，23，35，42，54が最大安定み正確な値が求められていない。そして，その値は，20年以上の月日を経て‰0V孟s盗によって解決されるこ集合），α（げ5）2＝4である．

このようにして，誤り確率0であるような長さ穐の入力の最大数は，錯の館個の直積￠陀に関する要素数最大の安定集合の大きさ，すなわちα（α侃）に等しくなる。情報理論では乱文字あたりの情報量、・、・：：JについてE拙ammomcapac軸を計算しているが，抗の＝且og2府とになる。

S。 mOV孟sz茸IuIllbermov壷汀呵は◎（C5）ニヽ作であることを証明した。
そのアイデアは次の通りである。グラフα＝（竹原）の各頂点宣∈yをⅣ次元単位長ベクトル鞘（叫∈Tlをレート（訂aもe，伝送効率）とよぶ。また，犯≧且の範囲での最大数は盟e好0血e訂rO訂CapaCiもyとよぼれている［且2］。
笈e貫かer雷0貯CapaC軸を求めるには且ogほ外して考えてもよい。すなわち，腰Ⅳ，髄㌘p髄￡＝且）として表わす・ただし，（盲，ブ）￠飢こ対して髄立と旭丘は直交（髄㌢髄ブ＝0）しているようにする。このような（髄宜l壱∈Ⅴ）をαの正規直交表現（0訂も駄omo『m融叩reSe離乳七iom）という。また，疋∈屁Ⅳを単位長ベクトルとする。このとき，⑳（G）＝SⅦp府。

且畔）＝謂）欝両孤≧1が問題の対象となる。⑳（α）はS駄ammomcapac玩yとよばれている。ぴ5の場合，α（Cg）＝5であることよりをmov孟szmⅧmbeFとよぶ．まず，㊥（α）は⑳（α）の上界であること，すなわち⑳（α）≦㊥（α）を示そう。

⑳（C5）≧へ序である。
補語且（臣且呵）粛（Gx甜）≦粛（α）β（∬）・

一般に証明…（町α（G侃）≧α（α）孤…，那花）および疋を∂（ぴ）を与える正規直交表現（勘，旺∈児Ⅳ），（働1，…，朋m）および逓を粛岬）が成り立つため，⑳（α）≧ α（G）である。すなわちを与える正規直交表現（閻メ，適∈風脚）とする。ここで，◎（G）の下界がα（α）で与えられる。また，［咽では謬∈兇Ⅳ，野∈児」ばに対して行列詔邸紆をベクトルとし⑳（踪）の上界が与えられている。これを説明するためて表現したものを謬。討と書く。すなわち，に，鍔＝（析腰）のクリーク（c孔軸e）を，任意の2頂点が枝で結ばれているⅤの部分集合打と定義し，C詔。野ニ（諾胤諾1即2，＝‥，正1鍬，脛2恥…）訂∈盈Ⅳ紺をすべてのクリークから成る集合族とする。さらに，である。このとき，（詔1。凱）訂（諺2・謬2）＝（詔ぎ謬2）（野ぎ野2）．ご・● 一 二 ・ こ ∴、こ ニー・・こ● − ・・一である。

すると，疋・逓は単位長ベクトルであり，（髄宜。閻Jl∀豆，メ）ときはα×甜の正規直交表現であることを示すことがで・∴・・∴￣二・きる。よってと定義すると，

且粛（α×呵 ≦ 甲轡 上LJ1月．m招（（疋・ば）ダ（髄古閻J））2∴−・・． 、、− −且誓言Ⅹ砕石平抑．・・・て「：・が成り立つ［且牲実は且／‰（α）と、・、∴・−−−、ゝご㊥（α）㊥（甜）となる。

認≧⑬，∴−・∴

宜 盲∈Ⅴニ．−こ・・‥は等しく9［咽ではÅ（α）を用いている。Å（α）は線形計画問題であり，A（げ5）＝喜と計算できる。したがって

哩6田（40）

実は，補遺且は等式で成り立つ．すなわち呵や×甜）＝㊥（α）粛岬）である［叫。
補遠望（［鼠⑬］）α（α）≦粛（￠）・© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチ

証明‥（叫， …，視れ）およびcを∂（G）を与える正規直交表現とする．また，（1，…，りを最大安定集合問題の最適解とする（すなわちα（G）＝り．このとき，11岬）＝票野て印≧戸研￣（J＝1，…，た）である．また，叫，‥．，≠たは互いに直交している（正規直交表現の定義）ことから
ゐ∑（cr叫）2≦erc＝1
ブ＝1

図3：正五角形AβCかβを示すことができる．以上よりた

1

α（G）＝た≦岬）∑（cruブ）2≦岬）㌔c＝畔）1

棉）≦票帯締一所

ブ＝1となる．

■である．そこでん2の値を求めよう．そのために，
Aβ＝α，AC＝d，Ag＝β

補遺1，2よりとおく（図3）．まず，△AβCと△A〟βが相似である
α（Gれ）≦♂（Cれ）≦せ（G）れこと，および音戸＝面否であることからである．したがって

dα

α d−α

㊤（G）＝S叩府≦♂（G）となる．この比丁＝旦は丁2一丁−1＝0を満たし，黄 11几≧1

金比（丁＝主宰）として知られている．次に，△A且Ⅳが示された．

そこで，0（q）＝ノ百を示すには，♂（q）≦ノ百を証と△AC′上が相似であることより明すれば十分である．そのために，図2のようなR3の正規直交表現を構成する．これは，Cを把手（handle）丁＋2とする傘（Ⅶmbre肋）を，ひとつおきの骨（rib）が90度が導かれる．ところでLov孟szⅦmbrellaの構成方法よになるように開いた図であり，【1］ではLov乙szl旺mbrel−り，△OAC（図2）は百万＝百斎＝1の直角二等辺三角1aと名付けている．AβC上）βは正五角形であり，gは形であり，d＝ノ豆である．また，△OAgは直角三角その重心である．

形であることから

九2＝1−㌔＝1＿≡＝

か〟1＝OA勉＝∂言
さ叫＝0（＝〟4＝0β＝〟5＝0ど

2 1＋ヽ作 1
丁＋2＝5＋諦￣ノ首となることがわかった．
以上をまとめると，

諦≦0（C5）≦叫q≦＝浦となり，したがって00（C5）＝ノす

図2：Lov乙s石umbre11aであることが証明された．
Lov乙sz■umbrenaにおいて

ん＝Cr叫＝…＝eru5であるから

2000年9月号［10］は，0（C5）の計算という20年来の問題を解決したばかりでなく，少（G）に関する様々な考察を行なっている・そのひとつが♂（G）の表現に関するものである．
例えば© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（41）461ミニ∴：ニ、軋ノぺ仙フェクトグラフ

目的：相原＋A）→最小化
対敵・鶴＝0（壱∈y），β（α）が多項式時間で計算できることによる重要な

鶴＝0（（壱，メ）ぼ屈）・帰結として，パーフェクトグラフに対する最大安定集という固有値最小イヒ問題の最適値が粛（α）に一致する合問題が多項式時間で解けることが示される［5］。

ことが証明されている．ただし，腰はすべての要素がこの事実を説明するために，まずパーフェクトグラ且である行列であるや 前回紹介したように，固有値最フを定義する。グラフα＝（町厨）の良一彩色とは，Ⅴカ、化問題は次の半正定借計画問題と同値である。の彪個の安定集合への分割である．ここで，（Ep且）

目的：g→最小化

揖（α）：αの最大クリークの要素数‥・、ト ー・ミー・ト≒：．〉、∴・∴7（α）＝ αが齢彩色をもつ最小の彪

・． −．い・∴ −∴と記号を導入する。揖（α）≦7（ぽ）を確認するのは難裁ゴ＝0（（痘，メ）￠腰）・しくない。しかし，等号が成り立つとは限らない。例（EPl）の変数はzと鶴（（壱，メ）∈腰）である。したがって，動メを第（壱，ガ）要素と第（メ，盲）要素が鼠で残りがす

ラフ（pe『臨cもg『札的）と定義をした：

べて0である行列とすると（Ep且）えば，2＝揖（げ5）＜7（C5）＝3である。Be呼は，α＝押牒）が次の条件を満たすときパーフェクトグ

任意の誘導部分グラフ飢こ対しては岬）＝7岬）

目的：Z→最小化が成り立つ。

・−トト∴二：・こ．ノ− ゴI∫

条件：岩原仙（との（壱，ゴ）∈厨（r，腰［紆］），腰［ア］＝挿，ブ）∈屠l盲，ブ∈耶として定義さとできる。よって（Epl）の双対問題は（SDP鼠）

ここで，誘導部分グラフとは，甘⊆Ⅴに対してα［訂］＝れるグラフのことである。

目的：腰⑳濫→最大化

パーフェクトグラフには様々な特徴付けが存在す

条件：g◎濫＝且，る（［句など）。その中でも，数理計画と関連の深い特腰宣ゴ⑳濫＝0（（壱，ゴ）∈∬），

徴付けを紹介するために，2つの多面体STAB（勒濫トのQS甘ÅB（α）を導入する．ぶ⊆Ⅴに対して㌦∈細且‡yを『Ⅹヂ＝且⇔壱∈ぶ』として定義される支持ベクトすなわちルとする。また，厨⊆原町の凸包をcomv岬）と記す．
（SDP）

目的：屈◎濫→最大化

このとき

条件：g⑳濫＝丑，∬盲ゴ＝0（（壱，ゴ）∈屈），濫トのSTAB（α）＝COmV（‡Ⅹぶ∈‡0，且〉y】ぶ：安定集合〉）と定義する。また，Å（α）の定義に現れる実行可能解集合をで与えられる。このとき
α（α）≦拶（α）＝即（SDP）

QS甘ÅB（α）＝；▲て十三ー、∴∴｛が成り立つ。この（SDP）が半正志値計画緩和の始ま二とする。このとき次の定理が成り立つ．

りと言われているものである。現在，半正定借計画問題は多項式時間で解けることが知られているため，粛（α）は多項式時間で計算できることがわかる。より正確には，与えられた誤差∈＞0の範囲内で拶（α）の定理3（［盟，認〕）
α＝パーフェクト ⇔ STAB（G）＝QSTÅB（α）・聞α（G），Å（α）はそれぞれ近似値を計算する。これは，㊥（ぴ）の値が無理数となる場合があるからである（例えば粛（C5）＝ヽ信）。粛（ぴ）が多項式時間で計算できる事実は，G灯るもsc駄e乱，mOV孟s盟
払md Sc臨訂毎veァ阿によって示された。その方法は楕円体法によるものである。

租6選（42）α（α）＝報沖∈Sm轍

咽＝報沖∈QST嘲© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

｝

オペレーションズ。リサーチとして計算される．また，記≧0，TH（G）＝影∈月Ⅴ

α（G）≦0（G）≦㊥（G）≦入（G）であることが示されている［10］．したがって，Gがパーフェクトのとき，STAB（G）＝ QSTAB（G）より〈諺はすべての正規直交表現制約を満たすと定義する．このとき∂（G，ぴ）＝maX（ぴr影l虎∈TH（q）

α（G）＝入（G），すなわちが成り立つのである［6］．

α（G）＝0（G）＝β（G）＝入（G）

正規直交表現制約は線形不等式であるが，その数はとなる．よってα（G）（および0（q，入（G））は多項式時間で計算することができる．

一般に無限なので，TH（G）は凸集合ではあるが多面体とは限らない．ただし，TH（G）上で線形関数（ぴr認）

実は，【5］ではパーフェクトグラフに対する重み付き最大安定集合問題が多項式時間で解けることを示している．ここで，重み付き最大安定集合問題とは，非を最大化する問題は多項式時間で解けることが示されている【6］．また，α（G）≦∂（G）≦入（G）であったから負ベクトルw∈RVに対してα（G，可 ＝ maX（ぴr認l諺＝X∫（g：安定集合））＝ maX（Ⅶr諺l正∈STAB（G）‡
として定式化される問題である．特にα（G）＝α（G，1）

である（1はすべての要素が1のベクトル）・いま，Wは整数ベクトルであるとしよう．このとき，Cとびよりα（G，ぴ）＝α（Gぴ）を満たすグラフCⅦを構成することができる．しかもGがパーフェクトならばGぴもパー フェクトであることが証明されている【9］．したがって，パーフェクトグラフGに対してα（G，W）＝

STAB（G）⊆TH（G）⊆QSTAB（G）

であることが予想されるが，これが実際に成り立つことが【6］で証明されている・STAB（G）およびQSTAB（G）上で線形関数を最大化する問題はともにNP困難である［6】ことを考えると，これは興味深い結果である．また特に，Gがパーフェクトのとき
STAB（G）＝TH（G）＝QSTAB（G）

であり，TH（G）は多面体である．実は，その道も正しい．すなわちα（Gw）＝♂（Gw）であるから，β（GⅧ）を計算すればよい．ただし，単にGwを構成すると多項式時間算法にはならず，【5］では♂（GⅦ）が半正定借計画問題（SDPt〟）

目的：Ⅳ●ズ→最大化
条件：∫●ズ＝1，定理4（［6］）TH（G）：多面体⇔G：パーフェクト・■したがって，Gがパーフェクトでない場合，STAB（G）⊂TH（G）⊂QSTAB（G）

で，等号は成り立たず，しかもTH（G）は多面体では

ズ壬ブ＝0（（壷，ブ）∈句，ないことがわかる．定理4の系としてズト（フの最適値に等しいことを示し，（SDPw）を楕円体法で解いている．ここでⅣは，Ⅳ＝∨石ノ♂，∨石＝（、／市l壱∈Ⅴ）として定義される行列である・㊥（G，ぴ）＝㊥（GⅦ）と定義する・すると，㊥（G，ぴ）は（SDPt〟）のような計算式が存在する・しかし，α（G，W）のように，Wr諺を目的関数とする特徴付け系5（【6りTH（C）＝STAB（C）⇔G：パーフェクト■系6（［6】）TH（G）＝QSTAB（G）⇔G‥パーフェクト■が成り立つ．定理4，系5，6はパーフェクトグラフの興味深い特徴付けである．
なお，第3節，第4節の内容は［7】に詳しい．

が望ましいはずである．そして，その答えが［6】に与5．線形化

えられている．

【6］では，TH（G）に関する複数の表現を与えている・

それは，Gの正規直交表現（叫∈兄Ⅳl壷∈Ⅴ）および単位長ベクトルc∈RⅣについて∑（㌔叫）2諾 ≦1i∈γを正規直交表現制約とよび，2000年9月号

そして，前回紹介したLov孟szandS止蛸verの論文［11］では，TH（G）のさらに新しい表現が与えられている・
この表現は，前回解説した線形化による半正定借計画緩和問題にほかならない．これを説明するために，次の非凸2次計画問題を考えよう：© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（43）463（：￣・−・）

目的：亀㌔遠→最大化

時間で計算できるかどうかも知られていないらしい。

条件：諾古刀ゴ＝0 （（盲，メ）∈腰），￠（α）の定義式どおりに計算をすることは，おそらく、・・：、−・、・・ 〉不可能であろう。よって，⑳（α）を計算する手段はあ、‥￣、・−∴るのだろうか，とすら思えてくる。そして，それを思ここで，「尋】勘＝￠⇔認宜∈‡0，拍」であることなどうとき，阻0V血盟の卓越したアイデアにただ関心するを考慮すると，（喝P）の実行可能解集合は安定集合のばかりであり，また，その後の理論の発展にはただ驚支持ベクトル集合となる。したがって，（QP）は重みくばかりである小付き最大安定集合問題の定式化になっている。

参考文献（佃野）を線形化によって＼、卜．J

日軌 Ⅷ鮮♂→最大化

囲Åigme冨M。andZi咽鼠e訂G．M∴（（壱，ガ）∈勒

条件 一鞠＝0

P『00臨鉦om甘HE

愚00K ，Sp血ge『（1999）血．．．こ ∴ ニミ∴ ：［2］C鮎Ⅴ孟も凰且，Ⅴ∴ Om c餌も扇m po蜘opes associa七ed

恩一都㌦＝のWiも駄g訂ap払s．Jの餌γれαg材げ￠mあ五和αわγ盲αg耶あ印γyβ一郎㌦野凰瀾（1975）且38一皿弛のように再定式化すると，半正定借計画緩和問題［3］FⅧ鼠kersom，Ⅲ。択一∴Om也払epe脆cも酢乱p血地eo∬em．

目的：Ⅷ訂詔→最大化

く二．．二∴．＿， ・・‥

im M如嵐em出立ca且p『0酢乱mmimg 岬Ⅷ弧d風ob五m−（（五，メ）∈卵，

条件 一勒＝0SO肌eds。）pp。69−77，Ac風鮎m五cp訂eSS，且9悶。

こ・￣ −ト［−二・′ここ・・・・・∴、− ∴．∴・．∴∴・トl∴ニ∴・1い、■：・Lこミfて！．・ご・ミ：∴・

選一認諾鮮トのS。のP鮮脇（mews凰如七e『0甘地eM乱地em軋もicalP雷0一が得られる。すると

即amm鼠mgSoci融y），感詔（且999）2−5・卜・∴∴、一 ニト．1．1ミ∴・∴i∴卜し：−・：−∴ム ーご ‥一汐（吼可＝即（雨）ellipsoidmet・hodandi仁sconsequemcesinconlbina−が成り立つ［且拓 これを甘叫び）との関係でいうと次も0訂鼠風見opもimi盗a伍ompぴひmあ壱円α加五cα，且（且9錮）169一のようになる：

且9ア。
［6】G灯るもsc駄e且，M．，乱0V誌名，m。a訊dS地方毎ve『，Å・：Re一定理欝（E鳳凰］）

旦乱Ⅹaも五omso『verもexpack五mg．J￠視γm瓜gげぴomあ哀れα−∃g∈βy sⅦC弘也嵐aもTH（α）＝∴、・二1・￡のγ五αg珊eo叩朗γ・β魂￠（19呵330−3弧（（壱，ゴ）∈厨），∬宜ゴ＝0［7］G『る七sc駄e且，M・，mOV嘉男，m・amdSc丑l『毎ver，A∴−∴ r ：・：−い・、∴Ge−

OmetricAigorithmsandCombimatorialOptimiza−

三野一謬詔アトのも孟om ，Sp訂豆mge若（19㈹）。
鄭

ここにきて，前回紹介した線形化とmov孟s盗n岨mberの理論が結びついた。したがって，半正志値計画緩和の一般論がmov志z皿Ⅶmbe貰およびTH（G）の理論へ適用できるようになった。今後も理論のさらなる発展が［∂］Haeme訂S，W∴Omsomep『Ob且emsof鮎0V孟szcom−

eerning the Shannon capacity of a graph．IEEE
甘hⅣ柑一陣アm・耶あeO叩，霊鳥（且979）23且−232・［9］Lov義盗監∴Norm亀且駄ype呼ap亙乳Samd抽epeぎ灸cも酢aphco雨ecもⅧre・β壱ぷCγe￡e財α兢emα￡五cβ，2（且972）
253−26㌢．

期待できる。

［叫mov孟s笈m∴Om七駄eS貼nnomc乱paC軸ogagFap虹6什 ぁわりに躇風㌢紬m凱玩掛澗L耶離明，25（且979）且−7。

今回は，⑳（鴫）＝坤瑚＝〜序であることを中心と［叫監0V孟sz軋。乱md Sc払方毎ve訂A∴ Comes oぎm包もrices

した解説を行なった。しかし，一般には⑳（α）と㊥（α）

and se士・hlnぐtioms and O−loptiIlli五aもion．∫⊥4ÅfJ．

は等しくない阿ことを注意しておく。

0れのpた壱m壱zαと壱￠閃，凰（且99且）且66−1馴圭∂（α）に比べ，⑳（切には知られていないことが多［且2］弘弧mOmC。臥：甘嵐e富erO−er甘0訂CapaCi吋ogamoisy

い。例えば，7以上の奇数mについて⑳（q71）の値

c駄amme胤一服甥甘兄那∴勒卸間一孤e￠γy，3（且956）3−は知られていないようである。また，⑳（ぴ）が多項式

ユ5．

僅6穏（44）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチ