2一丁−2
チュートリアル 1995年度日本オペレーションズ・リサーチ学会 春季研究発表会SemidefiniteProgrammingと内点法
01103520 東京工業大学 小島政和 ⅠくOJIMAMasakazu
壊近，数理計画法の分野でSemidefiniteProgrammingが注目を浴びている．特に， （a）線形計画問題の内点法の拡張（【1，4，6，7】等） （b）組み合わせ最適化への応用（【3，5】等） （c）システムと制御への応用（【2，8】等） に関連して盛んに研究されている．乃×乃の実対称行列ズが正定借，半正定借であるとき， それぞれ，ズト0，ズと0と記す・また，2つの乃×犯行列A＝【旬】，β＝【わfブ】に対し て，それらの内積をA・β＝nATβ＝∑αi舟
i，jで定義する・Ai（i＝0，1，…，m）をnxn対称行列とすると，標準形のSemidefinitePro−
gramとその双対問題は以下のように与えられる． （∫βアーク）min． Sub．to Ao●＿方 Ai・ズ＝わi（豆＝1，2，…，m） ズと0． （且DP−β）max・ Sub．to ∑わiZi ∑AiZf＋y＝Ao， yト0． 通常の線形計画問題とその双村問題 （エアーP）Inin・ Sub．to α0・〇 叫・黒＝わi（五＝1，2，…，m） 〇≧0． （エアーβ）max． ∑占iZi Sub．to ∑aLZi＋y＝ao， y≧0． と比較すると， LP（線形計画問題）SDP（SemidefiniteProgram）
αブ：れ次元ベクトル ＝⇒ Aブ‥れ×れ対称行列 ・ ＝⇒ ● ＞ ＝＝｝ ト となっていることが分る．ただし，・はベクトルの内積を表わす． 一150− © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.SemidefiniteProgramに対しては，線形計画問題に関する双対定理，相補性定理等の理論 がほほそのまま成立し，内点法が拡張されている．このチュートリアルでは以下の項目に関し て簡単に解説する． 1．SemidefiniteProgramと内点法の歴史および現状 2・線形計画問題とSemidefiniteProgram 3．SemidefiniteProgramの例 4．SemidefiniteProgramの特徴 5・SemidefiniteProgramに対する主・双対内点法【4】 Refbrences 【1】W・F・Alizadeh，J・−P・HaeberlyandM．J．0verton，“Primaトdualinterior−pOintmethods fbrsemidefiniteprogrammlng，”ComputerScienceDepartment，CourantInstituteof MathematicalSciences，NewYorkUniversity，NewYork，NY，August，1994・ 【2】S・Boyd，L・E・Ghaoui，E．FeronandV．Balakrishnan，LinearMalrixInequaliliesin SystemandConiroITheory，（SIAM，Philadelphia，1994）． 【3】M，Gr6tschel，LovaszandA．Schrijver，“Polynomialalgorithmsforperfectgraphs，” Am乃αgβげβねcreまe〟α兢emα如β21（1984）325−356． 【4】M・Kojima，S．ShindohandS．Hara，“Interior−pOintmethodsforthemonotonelinear
COmplementarityproblemsin symmetric matrices，‖ Research Reports B−282，Dept・
OfInformationSciences，TokyoInstituteofTechnology，01トOkayama，Meguro，Tbkyo 152，April1994． 【5】L・LovdszandA・Schreiver，“ConesofmatricesandsetfunctionsandO→10ptimization，” ∬A〟 J・Opf血豆zα如乃，1（1991）166−190． 【6］Y・E・NesterovandA．S．Nemirovskii，InteriorPoinlPolynomialMethodsinConvex Prv9rtLmmin9：T71eOryandApplications（SIAM，Philadelpllia，1993）．
【7］Y・E・Nesterov and M．J．Tbdd，“Selトscaled cones andinterior−1）Oint methodsin
nonlinearprogrammlng，M CatholicUniversityofLonvain，Lonvain−1a−Neuve，Belgium， 1994． 【8】L・VandenbergheandS．Boyd，“AprimaトdualpotentialredtlCtio11metllOdforproblems invoIvingmatrixinequalities，M MathematicalPro9rtlmmm9，SeriesBtoapl）Car・ −151− © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.
