遂次凸緩和アルゴリズムの並列実行とその組合せ最適化問題への応用

顺序凸松弛算法的并行执行及其在组合优化问题中的应用

• 批准号: 13224037
• 负责人: 小島 政和
• 金额: --
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13224037/
• 关键词: 逐次凸緩和; 組合せ最適化問題; 半正定値計画; 線形計画; 並列計算

本年度は以下の研究を行った(1)半正定値計画問題に対するソフトウェアSDPAのさらなる高速化に関する研究.通常SDPAの1反復の中で,最も計算パワーを要する部分は探索方向の計算である.この部分を高速化するために2つのことなった技術について研究した.1つは半正定値行列補完であり,この技術が変数の個数が非常に大きい問題に対して有効であることを計算機実験を通して検証した.もう1つは線形等式条件が多い問題に有効なLagrange双対内点法である.これらの結果については,九州で行われた応用数理学会,および,京都で行われた国際会議NTOC2001で発表した.(2)逐次線形計画緩和の実装とその並列実行実験.この研究課題を始める以前に行っていた逐次半正定値計画緩和は有効な緩和値を計算出来るのであるが,計算時間が多くかかった.これに対して今回の逐次線形計画緩和は緩和値に関しては若干劣るが,計算時間は短いことを検証した.この際,逐次線形計画緩和に特有の問題である"線形計画子問題を解く時間の大きなばらつき"を発見した.このため並列実行する際に線形計画子問題をどのような粒度でサーバー機に受け渡せば良いかが今後の課題として残った.また,逐次線形計画緩和,および,逐次半正定値計画緩和の2つの逐次凸緩和をどのように使い分けるかを詳しく調べる必要もある.(3)分枝限定法と組み合わせた場合に,逐次半正定値計画緩和がどのように有効に働くかについての基礎実験に向けての準備を開始した.

This year, the following studies were carried out: (1) Semi-definite planning problems related to the optimization of SDPA and the acceleration of SDPA. Usually SDPA's 1 iteration, the most important part of the calculation is to explore the direction of calculation. This part of the speed of development, 2, technology, research, 1, semi-definite value column complement, this technology, the number of very large problems, there are problems, this computer implementation, through the detection of evidence. 1 The results of this research were presented at the Kyushu International Conference on Mathematics, Kyoto International Conference NTOC2001. (2)Successive linear plan mitigation and parallel implementation. This research topic starts from the beginning, and the calculation time is very long. This is the case with the successive linear plan mitigation. The calculation time is short. At this time, successive linear planning mitigates the unique problem of "linear planning sub-problem solution time". The problem of parallel linear planning is that the problem of parallel linear planning is difficult to solve. 2. Successive convex mitigation of successive linear plan mitigation. (3)The branch limit method and the combination method are used for the case, and the semi-definite value plan is gradually relaxed.

项目成果

Kim-Chuan Toh, M.Kojima: "Solving some large scale semidenite programs via the conjugate residual method"SIAM Journal on Optimization. (掲載予定).

Kim-Chuan Toh，M.Kojima：“通过共轭残差法求解一些大规模半定程序”SIAM 优化杂志（即将出版）。

Shao-Liang Zhang, K.Nakata, M.Kojima: "Incomplete Orthogonalization Preconditioners for Solving large and Dense Linear Systems Which Arise from Semidefinite Programming"Applied Numerical Mathematics. (掲載予定).

张绍良、K.Nakata、M.Kojima：“用于解决半定规划产生的大型密集线性系统的不完全正交化预条件子”应用数值数学（即将出版）。

M.Kojima, L.Tuncel: "Some Fundamental Properties of Successive Convex Relaxation Methods on LCP and Related Problems"Journal of Global Optimization. (掲載予定).

M.Kojima、L.Tuncel：“LCP 上连续凸松弛方法的一些基本性质及相关问题”全局优化杂志（待出版）。