組合せ的行列理論に基づく最適化手法の設計

基于组合矩阵理论的优化方法设计

• 批准号: 07J01663
• 负责人: 垣村 尚徳
• 金额: $ 0.58万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2007
• 资助国家: 日本
• 起止时间: 2007 至 2008
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07J01663/
• 关键词: 数理計画法; 線形計画; 線形相補性問題; 組合せ的行列理論; 定性的解析

定性的行列理論とは、入力の符号情報のみから形システムの定性的挙動を解析する手法であり、経済モデルなど入力数値が不確かな場合に有用である。本研究課題は、定性的行列理論の最新の成果を利用して、最適化問題に対する効率的解法を設計することを目的としている。本研究では、最適化問題に対し符号可解性という概念を導入した。最適化問題が符号可解であるとは、入力の符号パターンから最適解の取り得る符号パターン集合が一意に定まるものをいう、昨年度までに、線形計画問題に対し、符号可解十分条件の導出と、その十分条件を満たす線形計画に対する効率的な組合せ的解法の設計に成功した。今年度は、線形相補性問題の符号可解性を議論した。まず、ある妥当な仮定を満たす線形相補性問題に対し、符号可解性に対する組合せ的な特徴付けを与えた。さらに、その特徴付けを利用して、線形相補性問題の符号可解性を判定し、符号可解ならば解を見出す効率的解法を提案した。これらの成果は、査読付き国際会議『整数計画と組合せ最適化』(IPCO)に採択され、昨年6月に発表を行なった。さらに線形計画と線形相補性問題に対する提案手法を実装し、実用的な有効性を検証した。また、二次計画に対する符号可解性条件を考察するために、係数行列が対称行列である線形方程式の組合せ的構造を調べている。対称行列の非零構造を表す二部グラフは対称性を有しており、その種々の基本的性質も対称構造を持っている。現在、その対称構造の解明を進めている。

定性矩阵理论是一种仅根据输入代码信息来分析形态系统的定性行为的方法，并且在不确定输入数字（例如经济模型中）时很有用。该研究主题旨在使用定性矩阵理论的最新结果设计有效的解决方案，以针对优化问题。在这项研究中，我们介绍了用于优化问题的代码可解决性概念。到去年，当优化问题是一个解决代码解决问题时，在这种情况下，可以将可用于最佳解决方案的代码模式集取决于输入的代码模式，我们成功地得出了线性编程问题的足够的代码解决条件，并为满足足够条件的线性编程设计了有效的组合解决方案，以满足足够的条件。今年，我们讨论了线性互补性问题的符号的迹象。首先，为满足某些合理假设的线性互补性问题提供了代码可解决性的组合表征。此外，使用此表征，我们提出了一个有效的解决方案，该解决方案确定了线性互补问题的代码解决方案，并在代码解决方案的情况下找到解决方案。这些结果由同行评审的国际会议“整数编程和组合优化”（IPCO）采用，并于去年6月提出。此外，我们实施了线性编程和线性互补问题的建议方法，以验证实际有效性。此外，为了考虑二次编程的代码可溶性条件，我们研究了系数矩阵是对称矩阵的线性方程组合结构。代表对称矩阵的非零结构的二分图具有对称性，它们的各种基本属性也具有对称结构。目前，我们正在努力澄清这种对称结构。