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

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

基本信息

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

项目摘要

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

主题是研究对称矩阵空间中线性规划问题的内点方法，特别是仿射缩放方法，但在这项研究中，我们能够证明这种方法效果不佳。对称矩阵空间中的线性规划问题是凸规划问题的一种，由于其具有多种工程应用且线性规划问题的内点法可以自然扩展，因此近年来引起了人们的关注和积极研究。特别是一种称为原对偶内点法的方法得到了很好的研究，并证明了在一定条件下多项式时间内的收敛性，为解决实际问题提供了可能。另一方面，仿射缩放方法是最基本的内点方法之一，但将其扩展到对称矩阵空间的研究最近才开始。相比之下，在本研究中，我们构建了一个特定问题，并证明如果我们从该问题的适当位置开始仿射缩放方法，它会收敛到不是最优解的点。换句话说，我们证明对称矩阵空间中线性规划问题的仿射标度方法不具有全局收敛性。这是一个负面的结果，与最初的目的（证明全局收敛）背道而驰，但却是一个重要的结果。请注意，这里提出的具体问题非常简单，可以使用原对偶内点法轻松解决。因此，这个结果强烈表明仿射缩放方法不是解决对称空间中线性规划问题的有效方法。