第３回目は数理第二研究室の垣村尚徳さんに「数理計画法における符号可解性（Sign-Solvability in Mathematical Programming）」という題で話していただきました．
発表では，まず，行列の定性的解析のを紹介をしていただきました．それから，それを発展させた組合せ的手法を用いた数理計画問題の定性的解析を紹介いただきました．
行列の定性的解析とは，要素に誤差を含み得る行列の，その誤差に依存しないで決まる性質を解析することです．このような定性的な解析では，行列要素の数値情報は使用できないため，符号情報（行列要素の正負）等の構造的な情報を元に組合せ的手法（グラフ理論等）を用いて解析結果を得ます．このような定性的な解析は1947年に経済学の分野から始まったそうです．
例えば，一般に経済学で価格pは需要D(p)と供給S(p)が釣り合う点D(p)=S(p)で決定される（下図左）と考えられますが，需要がもう一つの変数，嗜好tの増加関数である場合，嗜好tが増減した時に価格pがどのように変化するか，という問題を考えます(下図中央)．この時，嗜好tの変化に対する価格pの変化率は下図右のような連立方程式の解として得られますが，その符号は、D(p)やS(p)の具体的な関数形によらずD(p;t)がpに関して減少関数，tに関して増加関数であること，S(p)が増加関数であることから必ず正である（嗜好tが増えれば価格は上昇する）ということがわかります．この一次連立方程式の解の符号をその係数行列の符号のみから判定するという解析は，符号正則性という性質で特徴付けられ，有効グラフの偶閉路の解析や二部グラフの Pfaffian orientations の解析といった組合せ的な手法で解析することが出来るそうです．
上記の行列の定性的解析の考えを，行列を用いて定式化される数理計画問題に応用したものが，組合せ的手法を用いた数理計画問題の定性的解析です．数理計画問題とは，特定の条件を満たす解のうち最適なものを探し出す問題のことであり，多くの現実的な問題が数理計画問題に帰着されています．そのため，その定性的な解析が重要になってきます．例えば，機械を最適に動かすための制御にも数理計画問題が応用されています．そこでは，機械に関して測定された様々な数値データを元に数理計画問題を作り，その数理計画問題の解を元に制御器を作成します．しかしながら，現実の世界の測定結果には誤差が必ず含まれており，得られた制御器の性質はその誤差に影響されているかも知れません．そこで，そのような誤差に影響されない定性的な性質を知る手法が必要になります．垣村さんは，数理計画問題の一種である線形計画問題に対し，その最適解の符号パタンの集合が一意であるか否かという，符号可解性を高速に解析する手法を提案されました．さらに，提案された手法での解析結果を元に，最適解の符号だけでなく最適解そのものも高速に計算する手法を提案されています．組合せ的手法による解析は求解の高速化にも有効であり，応用上重要な今後の研究が非常に楽しみな研究だなと感じました．
数理第3研究室 助教 江本健斗
発表スライド：
