対称行列空間における線形最適化問題に対する効率的な解法アルゴリズムに関する研究

对称矩阵空间线性优化问题高效求解算法研究

基本信息

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

项目摘要

対称行列空間における線形計画問題に対する内点法、特にアフィンスケーリング法の研究が主なテーマであったが、本研究ではこの方法がうまく働かないことを示すことができた。対称行列空間における線形計画問題は、凸計画問題の一種であり、さまざまな工学的応用があることと、線形計画問題に対する内点法が自然に拡張できることから、近年注目を浴びて活発に研究されている。特に主双対内点法とよばれる方法がよく研究され、一定条件下での多項式時間による収束が証明されると共に、現実の問題を解けるようになってきている。一方アフィンスケーリング法はもっとも基本的な内点法の一種であるが、対称行列空間への拡張の研究は最近に始まったばかりである。これに対し本研究では、具体的な問題を構成し、この問題に対し適当な場所からアフィンスケーリング法を始めると、最適解でない点へ収束することを証明した。すなわち、対称行列空間における線形計画問題に対するアフィンスケーリング法は、大域的収束性を持たないことを示した。当初の目的(大域的収束の証明)とは反対のネガティブな結果であるが、重要な結果である。なお、ここで提示した具体的な問題は非常にシンプルなものであり、主双対内点法を使えば簡単に解けるものである。従ってこの結果は、アフィンスケーリング法が対称空間の線形計画問題に対しては有力な方法ではないことを強く示唆するものである。

主要主题是针对对称矩阵空间中线性编程问题的内部点方法，尤其是仿射缩放方法的研究，但是这项研究表明该方法无法正常工作。对称矩阵空间中的线性编程问题是一种凸编程问题，并且近年来已经对它们进行了积极研究，因为它们具有多种工程应用，并且因为可以自然扩展线性编程问题的内部点方法。特别是，已经对一种称为主要双重内部点方法的方法进行了充分的研究，并且已经证明了由于多项式时间而引起的收敛，并且可以解决实际问题。另一方面，仿射缩放方法是内部点方法的最基本类型之一，但是对对称矩阵空间扩展的研究直到最近才开始。相比之下，这项研究构建了一个特定的问题，并证明，如果仿射缩放方法从适合此问题的位置开始，则将其收敛到不是最佳解决方案的点。也就是说，已经表明，对称矩阵空间中线性编程问题的仿射缩放方法没有全局收敛。这是一个负面结果，与原始目的相反（全球融合的证明），但结果是一个重要的结果。此处介绍的特定问题非常简单，可以使用主双重内部方法轻松解决。因此，该结果强烈表明，仿射缩放方法不是对称空间中线性编程问题的有力方法。