対称錐線形計画に対する内点法に関する研究

对称圆锥线性规划内点法研究

基本信息

批准号：
12740073
负责人：
村松正和
金额：
$ 1.15万
依托单位：
The University of Electro-Communications
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
2000
资助国家：
日本
起止时间：
2000 至 2001
项目状态：
已结题

项目摘要

昨年度の終わりに,対称錐上の線形計画に対し,Commutative ClassおよびPower Classの探索方向を用いた内点法アルゴリズムに関して,計算複雑度を計算することができた.このPower Classある実数p>0でパラメタ化されており,これを使ったロングステップ内点法の計算複雑度はpに依存するものになる.既存の有力な方法であるNesterov-Toddの方向およびHRVW/KSH/M方向は,このPower Classの特殊な場合に該当することがわかった.これらの研究を受け継いで,今年度はまず,対称錐上の線形計画の一種である2次錐計画に対する内点法で,Power Classを用いるものを実装し,その効率の研究を行なった.特にNP困難な組合せ最適化問題の一種であるMax-Cut問題に対し,2次錐計画を用いた有効な緩和間題を提案し、これを実装した内点法によって解くことによりその有効性を確認した.これらの結果は,日本応用数理学会年会および統計数理研究所で行なわれた研究集会・最適化において発表された.また,論文"A New SOCP relaxation for MAX-CUT problems"となった.さらに,対称錐上の線形計画の一種である半正定値計画に関して、今回得られた知見から,強多項式で解ける問題のクラスを発見した.これは香港で行われたICOTA (International Conference on Optimization Technique and its Application) 2001において発表され,論文"A unified class of directly solvable semidefinite programming problems"となった.

去年年底，我们能够计算使用交换类和幂类搜索方向的内点算法的对称锥上线性程序的计算复杂度。使用长步内点方法的计算复杂度。这个参数取决于p。Nesterov-Todd方向和HRVW/KSH/M方向，这是现有的强大方法，是这个功率继承这些研究，今年我们首先计算Power我们使用Class实现了一个系统并研究了其效率。特别是，我们针对Max-Cut问题提出了一种使用二次锥规划的有效松弛问题，这是一种NP难组合优化问题，我们通过求解证实了其有效性。这些结果发表在日本应用数学学会和统计数学研究所的年会上，论文“A New SOCPrelaxation for MAX-CUT”。此外，关于半定规划，这是一种对称锥上的线性规划，我们发现了一类可以使用强多项式解决的问题（国际优化技术及其应用会议）2001，以及论文“。 “一类统一的可直接解决的半定规划问题”已发布。