研究集会「線形行列票禦●半正定値計画法」馳

ルポ

信太正之（神奈川大学），藤江哲也（東京工業大学）
7月15日から7月17日の3日間，京都大学数理解析研究所において研究集会「線形行列不等式・半正定値いて紹介され，数理計画の研究者に対して新たな研究計画法」が開かれました．線形行列不等式（Linear

課題を提供していただきました．ただ両先生とも，制MatrixInequality：LMI）とは，変数に関して線形な御の専門家にとっては常識であるブロック線図を使わ対称行列が（半）正定値となるような解を見つけるもの

ないで説明されるのにかなり苦心されていたのがとてで，制御の安定性などで最近話題の問題のひとつとなも印象的でした．っています．それに対して，半正定借計画法（Semト●らに難しい問題（例えば，双線形行列不等式など）につ

2日目と3日目は，最近の研究の成果を講演して頂

definiteProgramming：SDP）は，線形行列不等式のきました．吉瀬章子氏（筑波大学）は「内点法と非内点制約の下で線形関数を最小化するという問題です．特法」という演題で，SDPの研究の準備としての最近の殊な凸計画問題として内点法の枠組が自然に拡張でき研究について講演されました．相補性条件を連続関数ることや，組合せ最適化問題に対する良い近似解を与で表すことによって相補性問題を無制約最適化問題にえるということから，最近の最適化の分野で大きな話変形して解くという最近話題の手法について，内点法題の1つとなっています．との類似性などと関連づけて説明されました．小原敦

このように，本研究集会は，制御や最適化の分野で美氏（大阪大学）は「SDPアルゴリズムとそのいくつかホットな話題を対象にしていることや，それにもかかの応用について」の講演をされ，障壁関数の作るベクわらず研究者同士のつながりがあまり見られないといトル場が変数の逆行列の空間においてまっすぐになるった理由から，京都大学数理解析研の室田一雄氏と岩ことをもとにした新しいアプローチを提案されました．

田覚氏が企画されたものです．その前評判が高かった

浅野孝夫氏（中央大学）は「最大充足化問題（MAXのか，普段は係わりの薄い制御，内点法，組合せ最適SAT）に対する近似アルゴリズム：半正走値計画およ化問題などといった様々な分野の研究者が（予想を裏びネットワークフローに基づくアルゴリズム」という切って？）数多く参加され非常に有意義な集会となり演題で，ネットワークフロー，LP，SDPに基づく3種ました．

類の解法を説明され，これらの解法にさらに工夫を施

初日（15日）は，小島政和氏（東工大），原辰次氏（東工すことによって，SATに対する従来の近似値差を改善大），岩崎徹也氏（東工大）が基礎的な話をされました．

した結果を示されました．池連淑子氏（東京理科大）は小島氏は「半正走値計画法の基礎理論」という演題で「SDP for themaximumstablesetproblem」とい講演されました 内容は題目のとおり，SDPの定式化

う演題で，SDPによる緩和がはじめてLov孟szによっとSDPの適用例（制御の問題と組合せ・最適化問題をて適用された安定集合問題について，緩和法と緩和問含む2次計画問題の緩和法）の解説があり，そして内点題の最適値を多項式時間で求める楕円体法の説明をさ法の簡単な説明がありました．1時間半の講演の割にれました．その結果からパーフェクトグラフに対しては内答が豊富で，SDPの全体像をつかむには最適であは多項式時間で最適解が得られることを示されました．

ったに違いありません 原氏は「行列不等式に基づく村松正和氏（上智大）は「内点法から見たSDPとLPの制御系設計：Ⅰ，LMIに基づく凸最適化」という演題で違い：簡単な例をもとにして」という題で講演されま講演されました．制御の分野で現れる多くの問題がした．LPの円点法の主問題解法のひとつとしてアフLMIで表現できることと，そのことから従来解くことィン変換法が知られていますが，この解法がSDPにが困難だった問題が解けるようになってきていること自然に拡張することができないことを単純な問題例をなどを報告されました．それに対して岩崎氏は「行列使って解説されました．Monteiro氏（ジョージア工科不等式に基づく制御系設計：ⅠⅠ，非凸最適化問題の解大）は「Primaトdualpath following algorithms for法」という演題で講演され，LMIでは表現できないさSemidefinite programming」という演題で，SDPのパ1996年10 月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（45）5丁9

ス追跡型の主双対内点法アルゴリズムについて基礎理れる講究録を参考にされるとよいでしょう．最後に，論とともに，最近提案された探索方向に基づ〈アルゴ公私共にお忙しい中，このようなすばらしい研究集会リズムについて解説されました．続いて著者の1人でを，講演の依頼から発表当日の会場設定まで取りまとある信太が「単調相補性問題と内点法」について，主めていただいた室田氏と岩田氏に，心より感謝の意をに探索方向に関して注目して説明しました．さらにこ表したいと思います．

れも著者の1人である藤江が，矢島安敏氏（東工大）との共同研究「LPおよびSDP緩和を用いた2次計画問題に対する切除平面法」について，2次計画問題に対する緩和法と緩和を強化するためのカットに関する説

会 合 記 録明を行い，数値実験結果を示しました．最後に藤沢克樹氏（東工大）は「半正定位計画法と，安定集合問題や8月1日（木） 表彰委員会

8名

最大カット問題などのSDPを解く内点法を実装した
ソフトウェアSDPAの開発に関する説明と，安定集合問題や▲最大カット問題などのSDP緩和を実際に解い会友言卜報

横山 保氏（元副会長・フェロー，前明星大学情た結果を報告されました．

以上，簡単に研究集会の概要を説明してきましたが，説明が不十分に違いありません．もしこの分野に興味がある，もしくは興味を持った方は，まもなく発行さ

報学部長）平成8年7月30日，循環不良のためご逝●去されました．享年75歳．
謹んでご冥福をお祈りいたします．

報文集価格表（会月価格）

T−76−1 オペレーションズ・リサーチのためのデータとプログラムに関する研究

4，000円T−77−2 環境アセスメントにおけるシステム分析手法に関する研究

2，000円一第一編：環境影響評価支援システムの検討−
一第二編：空間に対する影響の評価に関する調査研究−

T−77−3 環境アセスメントにおけるシステム分析手法に関する研究

2，400円

一第三編：米国における環境アセスメントマニュアル事例調査−

R−82−1「欧州におけるOR実施状況」視察団報告書

1，200円R−84−1「米国におけるORの実践」視察団報告書

1，200円

英文別刷 A New Strategy for North−South Cooperation：

1，000円

Micro−electoris as a Catalyst
R−88−1「南米諸国とのOR交流視察団」報告書

1，200円

TL94−1 NewDirectionsinSimulationforManufacturing

6，000円and Communications
R−94−2「ポルトガル・スペインとのOR交流視察団」報告書

1，000円

T−95−1「巨大プロジェクトに関するOR」

3，500円

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

オペレーションズ・リサーチ●