数理科学特別講義I

行列スケーリング（Sinkhorn 1964）とは，「与えられた非負行列Aに正対角行列X,Yをかけて，XAYを２重確率行列にできるか」という問題である．その判定は2部グラフのマッチング問題に帰着し，X,Yを求める問題は，ユークリッド空間上の凸最適化問題に帰着する．行列スケーリングは作用素スケーリング（Gurvits 2004）に一般化され，最近，その多項式時間アルゴリズムが示された（Garg, Gurvits, Oliveira, Wigderson 2016, 2020）．この結果は，シンボリック行列式恒等性判定（SDIT, Edmonds問題）や Brascamp-Lieb不等式の計算など分野を横断する多くの応用をもたらしている．そして，さらなる一般化の研究が展開してきている．これらは，GITにおける半安定性の判定問題を非コンパクト対称空間上の凸最適化問題としてとらえて，アルゴリズム・計算複雑度の観点からアプローチするものである．講義では，この新しい最適化理論の展開について解説する．数理科学の問題に対するアルゴリズミックな視点を学ぶことが一つの目標である．