単正建値計画藍その応用．・・ヰヰ室■・・

い ￣ −・ −・・・￣− ￣‥−−‥三さ＿・∴

藤江 哲也

・− −・一・、ぶ⊆風彿として問題（p）を考える。

今圃と次回の針回にわたり「緩和問題としての半正目的ニ ㌔（謬）→最小化

志値計画」を取りあげる。この話題の始まりは，最大条件：評∈鼠安定集合問題に対する監0V品s認の論文拉列である．この論文の結果は，その後彷『るもs撼e温，鮎0V孟s拓am菰Sc駄訂i叫
加配によって拡張。発展されていった申 しかし，半正造

健計画緩和が今日ほど注目されるようになったのは9

このとき，次の間題（夢）を（P）の緩和問題（re且axa七iomp∬Ob鳳em）とよぶ。
（夢（）

恥沌整数計画。組合せ最適化問題に対する一般論を展開したmov義盛乱m組Sc払『毎ve相4］の結果と∴最大カット問題に対し，半正起債計画緩和を用いた近似解法を提案した隠oem乱mS乱mdW姐臨amsom［8］の結果が始まりで

ただしヲダニ屈穐→腰，ぶ⊆児亀は（亙）ぶ⊆雷，ある。［咽では，半正造値計画緩和の適用範囲が汎用（誠）厨（記）≦済（α）（∀記∈ぶ）的であることばかりでなくタ半正志値計画緩和は連続緩和（線形計画媛和）よりも強い，など緩和が理論的を満たすものである。叶）を問題（・）の最適値とするにも優れていることが示された。削では，従来知らと，即（評）≦耶（p），すなわち緩和問題（面）は（P）に対すれていた近似比を大幅に更新するの．87＄近似解法を与る下界値を与えることが示される．半正走値計画緩和

えた膵呵は田本語で書かれた詳しい解説である）。まの場合巨酢が行列の空間に置き換わる。

た，単正志値計画問題を解く内点法およびソフトウェ

第4節では，過去に半正定借計画とは独立に提案さアの開発［ア］も半正宏値計画緩和に大きな影響を与えれたラグランジュ双対問題。固有値を用いた最適化問ている題，そして［8］に視れるベクトル計画問題が半正走値

さて，監0V恕慧am超Sc駄『毎ve『［且4ユ以来，多くの組合せ計画問題と等価であることを示す。

なお汐以下で用いられる記号や用語については，本最適化問題に対して半正定借計画緩和の研究が行なわれているが，それ以外にも非線形計画や大域的最適化で対象とされる望次計画問題にまで研究対象が広が連載第且回をご覧いただきたい。

望匂 非凸慧次計画問題っている。第2節少 第3節でその理由を明らかにする。
第3節では線形化に基づいた半正志値計画緩和の導半正走値計画緩和の場合，（P）に相当する最も一般出法を紹介サる。半正定値計画緩和の最大の特徴は，的な問題は，次の2次計画問題（Q岨a鮎aも立cp訂Og訂乱m抄

詔∈腰飽を変数とする問題を行列を変数とする問題へ

mm五mgprob且em）である。と緩和することである∴線形化による導出法は，まず∴−：）行列を変数とする問題へと再定式化しタその間題の緩目軋 題訂呼。記＋留訂認＋訂0→最小化

条件≡ が鳩糎＋留㌢認＋勘≦牒

和問題を作る，というものである。

（壱＝且，。■。，m）。

そこで，まず緩和問題を定義しよう。ダニ腰鶴→腰，ただし，（Q電，恥肝i）∈β佗×腐れ×児（壱＝0，且，…，隅）

ふじえ てつや 神戸商科大学商経学部〒65且胱2鼠￠3神戸南西区学園西町8叫2凹且である・もし，すべての吼が半正定借ならば，（Qp）

は凸計画問題であり，多項式時間で解けることが示される（この事実は定理且からも導かれる）。しかし，こ詔＄審（24）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチこでは吼の半正走値性を仮定しない．そこで，（QP）（QPム）

目的：Q。・ズ＋9訂認＋汀0→最小化
条件＝ 吼・ズ＋qr認＋Ⅳ壱≦0を非凸2次計画問題とよぶ．

（QP）は，それ自身が非凸型連続最適化問題であり，（壱＝1，…，m），大域的最適化の分野で扱われる，線形不等式制約の2ズー都㌔㌧−0．

次計画問題等を含む．また，（QP）は0−1整数計画問題（取）は半正定借計画問題ではない．しかし，なども含んでいる．実際，変数の0−1条件，土1条件はズー別グと0⇔諾j∈（0，1）⇔ 詔書一諾ブ＝0，認ブ∈ト1，1）⇔ 諾巨1＝0（三≡）と0（2）が成り立つ（例えば［9］）ため，行列y＝（均）∈β1巾と2次等式で表現できる．すなわち，半正定借計画緩を和の通用範囲はかなり広い．もちろん，問題ごとの研諾1究も数多く存在するが，これについては［6，10，11］等a：れ∬11 ‥・ズ1†lをご覧いただきたい．

3．線形化と半正定侶：計画緩和問題

孤1 ‥・芽mとして導入すると，（取）は次の間題と等価になる．

ここで（QP）に村する半正定借計画緩和問題を導くが，すでに述べたように，（QP）は避＝（認1，…，諾れ）r（QPム2）∈月几を変数とする問題であるにもかかわらず，半正目的＝ P。・y→最小化
条件‥ β00・y＝1（⇔鴇0＝1），定借計画問題は対称行列を変数とする問題であった．

タ盲・y≦0（ま＝1，…，m），

そこでまず，（QP）の再定式化を行なう・そのために，

yト0．

2次項諾巧を新しい変数ズijに置き換える・すなわち，
方言メ＝託宣諾ブ（壱，J＝1，…，几）ただし，（1）として新しい変数を導入する．行列変数ズを用いる

障（三言），ク ＝（。；2謀）92（壱＝0，1，…，m）と（1）はである．（拓）は半正定借計画問題である．よって，∫＝正正r（奇声諒）または等価な問題何戸；）が，（QP）の半正定と書くことができる（ズの第（壱，力要素はズiブであり，那㌔の第（壱，プ）要素は諾巧である）．また，一般に借計画緩和問題とよばれるものである．
順番が逆になるが，（拓）を緩和問題にする元問題（QP上2）を紹介する．これは，（QP上）を次の事実に

TlTl

諺rQ記＝∑∑鯨明＝Q・（認諾r）

基づし

i＝1j＝1

rank （三≡）＝1・（3）と変形することができる．よって，（QP）は以下の問題と等価であることがわかる．
（QPム）

すなわち，次の間題が（QPム2）となる．

目的：Q。・ズ＋q訂正＋汀0→最小化
条件：吼・ズ＋9㌻認＋叫≦0（壱＝1，…，m），ズー那㌔＝0．

（QPェ2）

目的：Po●y→最小化
条件：鴇0＝1，
ク宣・y≦0（壱＝1，…，m），ranky＝1．

（QPム）も非凸2次計画問題である．しかし，（QP）に図1は，今までの議論のまとめである．（QP）から半おける2次目的関数，2次不等式がそれぞれ線形目的

正定借計画媛和問題何戸言）へ至る方法を2通り示し関数，線形不等式になった．よって，このような操作たが，別の方法で（拓）を導くものもある．

を線形化（1inearization）とよんでいる．

半正定借計画緩和の有効性はさまざまな角度から零行列 0 は半正定借であるので，次の問題は（QPム）の媛和問題である．
2000年8月号

論じられている．次に紹介する定理もまた，半正走値計画潰和の有効性を示すものであろう．

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

（25）389

4◎ 単正定偽計画緩和の導出法
非凸2次計画

半正志値計画緩和

本節では，線形化以外の導出方法を紹介する。
魂。鼠 ラグランジュ綴和（毒空）（眺望）閻（節義）Åニ（Å1，…，Åm）鮮≧⑬に対し，次の問題を考える。

∴∴・．∴

日蝕 ㌦鳩。お＋督訂認＋汀0†■rl

一丁−、・●∴・トー・−て・Jゝ」＝ぺ・∴召■＝ニ

条件：把∈風花巾（乱鼠Å）は緩和問題の条件を満たしており，ラグランジ

l、こ、 ・・

ュ緩和問題とよばれる。すなわち，朋（m風見）≦即（Qp）が成り立つ。そして＼形（喝P）に最も近い，すなわち

図且：半正走値計画緩和の導出法

即（m風見）を最大化する問題がラグランジュ双対問題∴∵定理鼠曙。との9吼ヒの，…，昭mとのとする（すな酎軌坤ほふ→最大化

条件：Å≧臥わち（Qp）は凸計画問題）。さらに，（蒔重信）の最適解を（謬ヰ9濫＊）とする。このとき，（圧＊，諾＊認＊釘）は（QP凪）の最適解であり，がは（Q伊）の最適解である■である8 ところが，喝。＋∑罠1Å五噂宜とのでない場合，
魁最後に，（Qp）に対する半正定借計画緩和が鮎0V孟s富叫諷Å）ニ仰∞となることが知られているので，

ト．1∴

am過Sc弘訂毎veE【且4］で提案されている方法の一般化であ

目的：即（m鼠Å）→最大化・・こ・〜 ・∴−．・′・「、：．￣・・・ ∴ることを説明する小［咽では，次の0一且整数計画問題、こ L‥、・

目的：紀伊a→最小化
・∴▲！ ‥二・∴・立 ∴−ここ

目的：或→最大化
こ．

条件 叫隠Å）一宏≧0，鞘∈｛の，且‡（ゴ＝且，…，花）。

∴∴・二＿−1・′∴∴．∴′ こ：を扱っている（ただし，瓜冨諺≦あゐ（彪＝且9…，m）を満をラグランジュ双対問題としてよい。さらにたす任意の忍は，⑬≦彗≦且（ゴ＝且，…，犯）も満たし

予・∴い′・・！；て二「・ト∴∴・ふ∴ご：・ニ ノく．・■：・ていることを仮定する）。そして（互P）を次のように再‡定式化する。

・：．∴∴′∴ご∴ ‥・∴Jミ）ト、：− ′1 ＿＿ニ・担瑚

目的：疋鮮詔→最小化を示すことができる［叫。結局，ラグランジュ双対問

1さ「■‥ ・‥−．−′・三−；・∴、・・（ガ＝且，…，犯；彪＝且，…，隅），、‥．∫；：ミ〜∴ 了・こ∴＿・、‥ こ二・目的：監→最大化

・、− ‥． ．．ニ．
・− ．・ご、：．．＝

題は−・

すをわち，（貰㌘）における妥当不等式聖≧￠とあ砲¶∴

条件：・炉0＋∑罠且Å宜厨宜¶蜜腰00≧：吼Å＞⑬となることがわかった。これは半正志値計画問題であα冨謬≧り，且皿諾ゴ≧￠とあ良一鵡訂認≧0をそれぞれ掛けり，しかも（柘）の双対問題である．（QP）に対する算して2次不等式を作る。（Ip且）は（Qp）の特殊な場合

ラグランジュ双対問題は［5，且7］等で扱われている。とをり，（QP）から（雇評忘）を作ったようにして（瓦Pl）の半正定借計画緩和ができる。これが［且4］で提案されている方法である。［29且2】は［叫の拡張であり，［咽についても言及されている。

3盟◎（26）

・・一 ハ・、・J、；・・二、・：・画（QP）において，行列吼の（ゐ，戚）要素を碗∠，ベク
トル軌の解凍要素を感と書くことにする。すなわち© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチであるから，yは何戸諒）の実行可能解である．逆に，（QP）：
Tl†もーn′目的：∑∑沖鵠撒＋∑恥＋汀0→最小化
ゐ＝1∠＝1メ＝1

TlTlyを（奇声云）の実行可能解とする．y≧＝βなので，y＝Vrγとなるような（几＋1）×（几＋1）行列γが存†1条件：∑∑沖如拙＋∑絢＋れ≦0
た＝1J＝1在する．このとき，Ⅴの列ベクトルγ0，γ1，．‥，γれが（VP）の実行可能解であることを確認することは難し

メ＝1（壱＝1，…，m）と書き直す．このとき，ベクトル計画渡和問題は，各変数諾ゴをベクトル竹メ∈月叫1に置き換えることで，くない・したがって，（VP）と（奇声諒）は等価な問題であることが示された．
ベクトル計画（VP）は近似解法の設計に利用されることが多い．その代表例が最大カット問題【8］である．

次のように与えられる：

ここでは，最大カット問題への適用を紹介する．その（VP）：

前に，最大カット問題では，（QP）として定式化すると

れ

Tl．Tl

目的：∑∑冴信行＋∑かれ＋和
ゐ＝1∠＝1

ブ＝1→最小化Tl作

線形項が消えることに注意しなければならない．すな

わち，後に定義する最大カット問題（MC）はれ条件：∑∑冴晶抹＋∑かれ＋れ≦0
鳥＝1∠＝1（QP）

目的：認rQ。罪＋汀0→最小化
条件：認rQ古記＋汀i≦0

ブ＝1（盲＝1，…，m），（壱＝1，…，m）

り0∈属叫1，γ訂γ0＝1，uj∈月叫1（J＝1，．．．，れ）．

単位長ベクトルγ0は定数1の役割をするものであり，の形になる・この場合（i訴㌃）は目的：￠。・ズ＋和→最小化（QPム）

条件：吼・ズ＋れ≦0

勘りをげ木に，諾メを覇王に置き換えたものがベ（壱＝1，…，m），クトル計画緩和問題（VP）である．ここで，（QP）のズー都㌔㌧−0

実行可能解諾1，…，訂れに対し，廿。を適当な単位長ベクトル，り＝諾Jγ0（ブ＝1，…，れ）として定義されとなるが，実は正を消去した問題

るγ0，γ1，…，Ⅴれは（VP）の実行可能解であり，かつ目的関数値は（QP）のそれと一敦する．したがって，目的：Q。・∫＋汀0→最小化（QPム）

条件＝ 吼・ズ＋叫≦0γ（VP）≦〃（QP）であり，（VP）の最適値は（QP）の最適（哀＝1，…，m），値の下界を与える・また，同様の議論によって，（VP）

ズと0の最適解り岩，廿；，…，現の張る空間の次元が1ならば，（QP）の最適解を構成することができる．

（VP）は（拓）と等価である．次にこの事実を示と等価になることは容易に示される．

以上を考慮しながら，まずは最大カット間違を定義

そう・まず，γ0，γト・・，γれを（VP）の実行可能解とし，する・無向グラフG＝（町方）および各枝e＝（壱，カ∈γ0，Ul，…，γれを列としてもつ（乃＋1）×（几＋1）行列を別こ非負の重みⅥ㌔＝昭プ＝l侮が与えられている．

Ⅴとする．さらにy＝VrVとする．このとき，また，頂点の部分集合g⊆Ⅴに対するカットを∂（g）＝（（壱，カ∈βll（ま，カngl＝1）と定義し，カットの重・γ君り∠＝鴇∠（鳥，ゼ＝0，1，…，几），・γ訂γ0＝1⇔坑0＝1⇔月00●y＝1，Tl．Tl

みを∑e∈∂（∫）耽とする・このとき，重み最大のカットを求める問題を最大カット問題という．最大カット問題の定式化はれ・∑∑凍読晶＋∑か訂γj＋叫
た＝1∠＝1（MC）

メ＝1

丁もTlれ ＝∑∑冴証抹＋∑か抹＋御訂廿。
た＝1∠＝1

目的：喜∑瑚1一明）→最大化（i，膏∈月条件：託宣∈ト1，1）（壱∈Ⅴ）．

j＝1＝Pi・y（五＝0，1，…，m），で与えられる・すなわち，諺＊を（MC）の最適解とすると，∫＊＝（壱∈Vl諾；＝1）に対するカットが最大カッ●y＞−0

2000年8月号

ト問題の最適解になる．（MC）は© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（27）391

l・・∴

目的：豊∑嘲一正宜認ゴ）→最大化

である。したがって，‡ま，ゴ‡∈屈g≧瑚A）⇔ z一恥（風）≧0条件：疋㌣＝風炉∈y）、．′．∴・−−くくニー．：＿．：】と変形でき，確かに線形項が存在しないので，：・∴−・：・

撒芸監喝か鶴→最大化
畑、け〔ぶ∈＝＝ゝ ニ∬−Aトのとなるひ（E瓦G）の双対問題は（、∴・●、二・二一二・い ・・．．．、￣、：

目的：戚⑳止野→最大化

条件：∬⑳濫＝且，二町トの濫トのが半正宏値計画緩和問題，（MCV）

撒芸監勒伸輔→最大化い，ゴ）∈屈である。興味深いことに，（鼠隠）の半正定借計画緩和（東電）は（E王GD）に一致する．すなわち，半正定借計
画の弱双．対定理を用いると、・− ．一 二、しこ 二
懲戒∈戯鶴Å1（過）＝即（鼠鼠）≦ 即（夜露）＝ 即（EIGD）≦即（EIG）＝瑚過）

がベクトル計画緩和問題となる（孤＝世断詳細は［6，且5］をご覧いただきた沌㌧となって，上記の値はすべて一致することがわかった。

毯。認 固有値（ただし，（E亙α）と（EIαD）は強双対定理が成立するための条件を満たしているので，即（EIGm）＝即（濫IG）は行列威∈β犯の固有値を非増加順に上記とは独立に確認できる）．

続いて，固有値が目的関数に現れる，次のような問兵乱（過）≧…≧Å穐（過）と記す。過が半正定借であるための必要十分条件は9Å穐（過）≧①となることであった。はじめに帰趨）の計算を考える巾

まず，比較的よく知られている公式として，題を考えよう。

（EP悌慧‡崇慧、諾

＝且，…，隅）。

つまり，最大固有値を最小にするような対称行列濫を求める問題である。そしてこの場合にも記鮮過甜

ニ・ 二・∴ご−−−・＝・一丁−−．三−∴・がある（鮎3髄且g駄叫餌盟削）。つまり，恥（戚）は2次計画：・・・、・

目的：g→最小化
条件 z≧Å宜（濫）（壱＝且，…，犯），問題

慮ゐ⑳濫＝あ彪（ゐ＝且，…，m）
目的：お餅威避→最大化、ご1−；、ニ：t）と変形すれば

条件：お餅詔＝且の最適値に一致する。次に，より直接的な定式化
ぐ±…∴二：・

目的：g→最小化！：∴・）

目的：g→最小化
1こ・ド ・−‥J■− − ご・、威鬼◎濫＝あゐ（ゐ＝且，…，m）

条件 g≧Å宜（過）（義＝勘…9孤）という半正定借計画緩和問題と等価であることがわを考える。この間題自体は意味をなさないように見えかる。（EP）自身は凸計画問題であり，NP一因難な間邁るが，実は半正走億計画問題の上界値計算などに現れる。今回は，最大カット問題．ニ‥￣・∴

に対する上界値計算を紹介する。

目的：g→最小化

そのために，無向グラフα＝（折居）および非負重条件：g厨一過トのみ吼（e∈腰）が与えられたとき，e￠厨に対しと等価であることが示される（gは単位行列）。実際，
過の固有値Åに対してgnÅは岩原一過の固有値となることに注意すると，′ ．・・′二・ ′！ト㌔ノ詔9盟（28）て閑㌔＝のとする⇔ これによって任意の頂点対盲，ブ∈厨（遠≠封に重みを付加するが，このように変更しても問題は変わらなし㌧ また，雇≠Jのとき血石ブ＝】鞘ゴ，広言壱＝‰≠。昭ゴとして定義される行列風∈ぶ恥を導© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチ人する．上はLaplacian行列とよばれている．さらに，［3］DelormeC・andPotjakS・：Laplacianeigenvalues

髄＝（叫，…，≠几）rに対して，（壱，壱）要素を叫とする対and themaxim11rL CtltPrOblem．Math．Prog．，62角行列Diag（u）を定義する．このとき，（1993）55ト574・

目的：芸人1（いDiag（Ⅶ））→最小化（MCE）

fbrthepartitioningofgraphs．1BMJ．qfResearch

条件：∑た1叫＝0
は，最大カット問題に対する上界値を与えることが示されている【3］．この間題は，半正定借計画問題

目的：z→最小化（MCE）［4］DonathW・E・andHo鮎IanA・J・：Lowerbounds

αれdβeγeJopme叫17（1973）420−425・［5］FujieT．andKojimaM．：Semidefiniteprogram−mlngrelaxationfornonconvexqlladraticprogram−S・J′イGgo♭αgOp士盲m壱zαわ乃，10（1997）367−380・

条件：Z∫−（エ＋Diag（髄））と0，∑た1叫＝0［6］藤江哲也： 線形化とLP緩和／SDP緩和 ，第11回RAMPシンポジウム論文集，35−48（1999）．になるが，（MCE）が（面百）の双対問題と等価である
ことが［8，16］に示されている．

［7］藤沢克樹‥ SDPA（半正定借計画問題に村するソフトウェア） ，オペレーションズ

固有値を用いた最適化問題は歴史があり，Dona紘一
Ho飢nanは1973年の論文［4］において，グラフ分割問・リサーチ，45（2000）124−131・［8］GoemansM・Ⅹ・andWi11iamsonD．P．：Improved

題（最小化問題）に対し，固有値を用いた下界値を掟案

approximationalgorithmsfor maximllmCut andしている．固有値を用いた最適化問題が半正定借計画

SatisfiabilityproblemsuslngSemide丘niteprogram−

緩和に変換できることは，［1］に詳しく述べられていming・J・扉A叩42（1995）1115−1145・る．【1］では，入1（ズ）＋…＋入た（ズ）の最小化問題など，（EP）よりも広いクラスの問題が半正定借計画問題に変換できることを示している．

【9］Horn R．A．andJolmson C．R．：
Sis

MatrixAnaly−，CambridgeUrLiversityPress（1985）・［10ト小島政和： 半正定借計画の組合せ最適化への応用に向けて ，オペレーションズ・リサーチ，42

5． ぁわりに（1997）216−221・

今回は，（QPム）に対する緩和問題として半正定借計

画媛和問題（雨）を導入した．また，これに加えて線形計画緩和問題の応用 ，離散構造とアルゴリズムⅤ（藤垂悟編），

近代科学社，203−249（199叶
目的：Q。・ズ＋9訂正＋和→最小化（6乾）［11］小島政和： 半正定借計画とその組合せ最適化へ

条件＝ 吼・ズ＋9㌻認＋れ≦0（ま＝1，・‥，m）

を導入すると，より一層広がりを持った議論ができ【12］KojimaM．andTunselL．：Conesofmatricesand
successive convex relaxations of nonconvex set，S，∫昆〟J・0れqp亡壱m盲zα如乃，10（2000）750−778・［13］Lov孟szL：OntheShannoneapacityく）fagraph．

る．しかし，（QPム）は本連載の枠からはみ出すため，

Jβββ7hれβ，坤m・7Ⅵeoγy，25（1979）1−7．

今回は取りあげなかった．興味ある方は【6】およびそ［14］Lov左sz L．and Schrijver A．：Cones ofmatricesの参考文献等をご覧いただきたい．

andsetfunctionsandO−loptimization．SIAMJ．

次回は，理論的にもそして歴史的にも重要な，最大安定集合問題の話題を取りあげる予定である．

0れOp亡盲m五zα如m，1（1991）166−190．
［15］松井知己： 半正定借計画を用いた最大カット問
題の．878近似解法 ，オペレーションズ・リサー

参考文献

チ，45（2000）140−145．
［1］Ali男adeh W．F．：Interior point methodsin

Semidefinite programInlIlg With application to［16］Poljak S．and RendlF．：NonpolyhedralrelaⅡ
ations ofgraph−bisection problems．SIAMJ．on

COmbinatorialoptimization．SLAMJ．on Opti−
Op亡壱m盲zα亡われ，5（1995）467−487・
m盲zα如m，5（1995）13−51・［2］BalasE．，CeriaS．andCorn11匂01sG．：Alift−and−projectcuttingplanealgorithmformixedO−1pro−
grams・〟α軋クγOg・，58（1993）295−324．
2000年8月号［17］ShorN．Z．：Quadraticoptimizationproblems．So一里盲e亡J肌γれαgイCo叩PU如αれd助β￡emβgC盲erlCeぶ，
25（1987）1−11・© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（29）393