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

点击翻译按钮获取中文摘要

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