線形相補性問題に対する組合せ的なアルゴリズムの研究

线性互补问题的组合算法研究

• 批准号: 09780370
• 负责人: 並木 誠
• 金额: $ 1.54万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1997
• 资助国家: 日本
• 起止时间: 1997 至 1998
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-09780370/
• 关键词: 線形相補性問題; 組合せ最適化; 列挙アルゴリズム; マトロイド; 組み合わせ的なアルゴリズム

本研究を通して扱う線形相補性問題 (Linear Complementarity Problems.LCP)とは最適化理論の基礎である線形計画問題、ポート・フォリオ選択問題を応用例にもつ2次計画問題、ゲーム理論での均衡点を求める問題等を実例とする、数理計画の分野の基礎的な数理モデルである。本研究では、この線形相補性問題というモデルに対し、組合せ的な基本性質を探りつつ、新しい解法の提案を行い、それを計算機プログラムとして実現しようと試みる、理論と実践の両面からのアプローチを目的とする。具体的な学術的な果としては、以下の3つを挙げる。まず第1に「Tne Existence of a Short Sequence of Admissible Pivots to an Optimal Basis in LP and LCP」という題目で、International Transactions of Oprations Researchと呼ばれる論文誌に掲載されたこと。この結果は、上の記述に従えば、ある条件の下では、任意の暫定解から最適解、或いは均衡解への最短の経路が存在することの証明であり、その解を求めるアルゴリズムの存在を示唆する重要な結果であると考えられる。次に.「EP Theorem and Linear Complementarity Problems」という題目で、Discrete Applied Mathematicsと呼ばれる論文誌に掲載されたこと。この結果は、一般には解くことが非常に難しいとされるクラスのLCPに対しての新たな解法の提案している点が重要である。最後にこれらの結果をまとめて、平成9年度にスイスで行われた第16回国際数理計画シンポジウムで発表したことを記述しておく。

The purpose of this study is to study the mathematical and physical problems of Linear Complementarity Problems.LCP, such as mathematical theory, mathematical theory and mathematical theory. The purpose of this study is to study the problems of physical compatibility, such as the exploration of the basic nature of the system, the proposal of the new solution, the implementation of the computer system, the realization of the test test, the theory and practice, and the purpose of the system. The specific achievements of science and technology are very important, and the following is not a good idea. In the first chapter, "Tne Existence of a Short Sequence of Admissible Pivots to an Optimal Basis in LP and LCP" and "International Transactions of Oprations Research", please tell me that the text is in order. The results of the test, the record of the results above, the conditions under the conditions, the solution of any decision, or the shortest path of the equilibrium solution, the existence of the solution indicates that there are significant results that indicate that the results are important. In the second place, "EP Theorem and Linear Complementarity Problems" and "Discrete Applied Mathematics" were called, and the text was called, and the text was called. The results show that the general solution is very important. This is very important. This is the most important part of the solution to the LCP problem. In the end, the results showed that in the year of 1999, the number 16 of the international mathematical plans was recorded in the international mathematical plan.

项目成果

K.Fukuda,H.J.Liithi,M.Namiki: "The Existance of a Short-Sequence of Admissible Pivots to an Optimal Basis in LP and LCP" Tnt.Trans.Opl.Res.Vol.4,No.4. 273-284 (1997)

K.Fukuda、H.J.Liithi、M.Namiki：“LP 和 LCP 中最优基点的短序列可允许枢轴点的存在”Tnt.Trans.Opl.Res.Vol.4，No.4。

K.Fukuda,M.Namiki,A.Tamura: "EP theorem and Linear Complementarity Problems." Discrete Applied Mathematics. 84. 107-119 (1998)

K.Fukuda、M.Namiki、A.Tamura：“EP 定理和线性互补问题。”