Mathematical programming is a branch of mathematics concerned with optimization problems, which can be applied to a variety of engineering fields. By recent progress of computer technology and algorithms, we have come to be able to utilize a large class of efficiently solvable mathematical programming models. However, it is often difficult to develop a mathematical programming model which represents a practical situation exactly. This is because the input data of a model are subject to many sources of uncertainty including errors of measurement and absence of information. On the other hand, structural properties of a model are independent of such uncertainty. This motivates us to provide a combinatorial method that exploits structural information before using numerical information.

In this thesis, we focus on the sign pattern of a mathematical programming model, that is, the combinatorial arrangement of positive and negative numbers of the input data. The use of sign patterns for matrix analysis is called qualitative matrix theory, which originated in economics. The main aim of this thesis is to present a connection between qualitative matrix theory and mathematical programming. We are concerned with the following three problems related to mathematical programming.

The first one is to compute the inertia of symmetric matrices. The inertia of a symmetric matrix indicates the number of positive/negative eigenvalues. Quadratic forms are classified by the inertia of the coefficient matrices. A symmetric matrix is said to be sign-nonsingular if every symmetric matrix with the same sign pattern as the matrix is nonsingular. Hall, Li, and Wang showed that the inertia of a sign-nonsingular symmetric matrix is determined uniquely by its sign pattern. We present an efficient algorithm for computing the inertia of such matrices. The algorithm runs in O(nγ) time for a symmetric matrix of order n with γ nonzero entries.

Secondly, we discuss solving linear programs from sign patterns. A linear program is said to be sign-solvable if the set of sign patterns of the optimal solutions is uniquely determined by the signs of the given coefficients. It turns out to be NP-hard to decide whether a linear program is sign-solvable or not. We then introduce a class of sign-solvable linear programs in terms of totally sign-nonsingular matrices, which can be recognized in polynomial time. For a linear program in this class, we devise an efficient combinatorial algorithm to obtain the sign pattern of an optimal solution from the given sign pattern. The algorithm runs in O(mγ) time, where m is the number of constraints, and γ is the number of nonzero coefficients.

Finally, we examine sign-solvability of linear complementarity problems (LCPs). An LCP is said to be sign-solvable if the set of sign patterns of the solutions is uniquely determined by the signs of the given coefficients. We provide a characterization for sign-solvable LCPs whose coefficient matrix has nonzero diagonal entries. This characterization, which can be tested in polynomial time, leads to an efficient combinatorial algorithm to find the sign pattern of a solution for these LCPs. The algorithm runs in O(γ) time, where γ is the number of nonzero coefficients.

These are the first attempts of qualitative analysis in mathematical programming which are independent of the magnitudes of the input values. In particular, the latter two results provide efficient algorithms to find the sign pattern of a solution. In both cases, the obtained sign pattern easily derives a solution itself by Gaussian elimination. Thus our results reveal new classes of mathematical programming problems which can be solved in strongly polynomial time.

数理計画法は,与えられた制約条件の下で目的関数を最大または最小にするものを見出す方法を研究する分野であり,1940年代のDantzigによる線形計画問題に対する研究が,始まりとされている.近年の計算機の高性能化と,それにも増して,アルゴリズム研究の発展の結果,現在では非常に大規模の線形計画問題も実際に解くことができるようになっている.しかし,現実の最適化問題のモデル化に際しては,係数の値が正確には判らない場合も少なくない.そのような状況下において,最適化を行うための手法として,区間線形計画,確率的最適化法,ロバスト最適化法など様々な手法が提案されている.

一方,定性的行列理論は,行列要素の数値情報を捨象し,符号情報のみから得られる行列の性質を調べる分野であり,SamuelsonやLancasterなどの数理経済学者によって,1940年代に研究が創始された.ここでは,要素の数値的な情報によらず,符号情報のみから正方行列の正則性が保証される「符号正則性」の概念が本質的である.正方行列の符号正則性を判定する問題は,Polyaが1913年に提起した2部グラフのPfaffian向き付けの問題など,様々な組合せ論的問題と等価であるが,これらの問題の計算複雑度は,1999年に Robertson, Seymour, Thomas が多項式時間アルゴリズムを示すまで,長い間未解決であった.

本論文は,定性的行列理論の最新の成果を用いて,不確実な状況下で符号情報から最適化問題を解析するための新たな方法論を展開している.特に,数値誤差の生じ得ない組合せ的な演算のみを利用して,非常に効率的なアルゴリズムを設計している点が特色である.

本論文は,8章からなる.第1章では,背景となる定性的行列理論の概要を紹介した後,本論文の主要な成果を概説している.

第2章は,組合せ的行列理論に関する準備に当てられている.行列の2部グラフ表現やDulmage-Mendelsohn分解などの基礎的な概念を紹介した後に,定性的行列理論における先行研究を紹介している.

第3章では,対称行列の表現として得られる対称2部グラフの組合せ論的な性質を調べている.特に,対称2部グラフ中の完全マッチングに関する定理は,それ自体でも非常に興味深い結果ではあるが,符号対称行列を扱う第4章の準備となっている.符号対称行列とは,対称行列の数値情報を捨象して,符号情報のみを保持することで得られる行列である.単に,符号パターンが対称になっているだけでなく,対称な位置の要素が同じ数値に由来するという条件が背後にある.符号パターンとして符号正則行列でなくとも,同じ符号パターンの対称行列がすべて正則になることがある.このような符号対称行列を符号正則対称行列という.

第4章では,符号正則な符号対称行列のSylvester指数が一意に定まるという, Hall, Li, Wangによる2004年の結果を踏まえて,その場合にSylvester指数を計算する効率的なアルゴリズムを与えている.このアルゴリズムの正当性から,Hall, Li, Wang の定理の手続き的な別証明が得られる.アルゴリズムの計算量は,行列の大きさと非零要素数の積に比例する程度である.同時に,符号対称行列が符号正則でないことを判定する問題がNP完全であることも示されている.

第5章では,完全符号正則性の概念を新たに導入している.正方行列の行列式の展開に非零項が存在するとき,この行列を項別正則という.一般の行列において,列部分集合によって定まる項別正則な部分行列がすべて符号正則であるときに,この行列を完全符号正則であるという.完全符号正則性の判定は,符号正則性の判定に帰着され,Robertson, Seymour, Thomasのアルゴリズムを用いて多項式時間で可能となる.

第6章では,線形計画問題に対して,符号可解性の概念を導入している.与えられた符号パターンの線形計画問題が符号可解でないことの判定がNP完全であることが示される.しかし,完全符号正則性を利用して,符号可解な線形計画問題の部分クラスを定義することができる.このクラスの線形計画問題に対して,最適解の符号パターンを計算する効率的なアルゴリズムを設計している.アルゴリズムの計算量は,係数行列の行数と非零要素数の積に比例する程度である.

第7章では,線形相補性問題に対する符号可解性の概念を導入している.係数行列の対角成分がすべて非零であるような線形相補性問題の符号可解性の判定を行う効率的なアルゴリズムを設計している.さらに,符号可解な場合には,解の符号パターンを同時に得ることもできる.アルゴリズムの計算量は,係数行列の非零要素数に対して線形である.係数行列の対角成分がすべて非零という仮定は,P行列(全ての主小行列式が正である行列)や正定値行列など線形相補性問題の理論で重要とされる係数行列のクラスを含んでいる点で自然なものと言える.この結果は,多項式時間で解くことのできる線形相補性問題の新たなクラスを示したと解釈することもできる.

最後に,第8章では,本論文の成果を纏めると同時に,数理計画法における符号情報の利用の観点から,今後の研究課題が提起されている.

以上のように,本論文は,定性的行列理論の数理計画法への応用という新領域を開拓した独創性の極めて高い研究であり,数理情報学の発展に大きく貢献するものである.

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる.