第5回研究会「離散凸解析と最適化」 (2019/11/2)

岸・梶谷によるグラフの基本分割から始まった基本分割の理論について、その発展の歴史をたどって分かりやすい解説を試みる。

2. 岩政 勇仁 氏（国立情報学研究所） 「2x2型分割行列のランクを求める組合せ的多項式時間アルゴリズム」

二部グラフの最大マッチング問題の代数的拡張である2x2型分割行列のランクを求める問題に対して，増加路を用いた組合せ的な多項式時間アルゴリズムを与える．

3. 平井 広志 氏（東京大学） 「離散凸解析 beyond Z^n」

整数格子Z^nを超えるより一般的な離散構造上での離散凸解析の展開について述べる．

4. 塩浦 昭義 氏（東京工業大学） 「Ｍ凸関数の最小化アルゴリズム」

本発表では，離散凸解析における最も基本的な最適化問題であるＭ凸関数の最小化を取り上げ，その制約なし問題および制約つき問題に対するアルゴリズムを紹介する．

5. 田村 明久 氏（慶應義塾大学） 「離散中点凸性とその周辺」

離散中点凸関数が満たす性質，最小化アルゴリズム，他の離散凸関数との関係等を紹介し，離散中点凸性に関連する事柄についても触れる．

6. 岩田 覚 氏（東京大学）「整数自由多品種流問題の組合せ的アルゴリズム」

ターミナル点集合が指定されたグラフにおいて，各枝に与えられた整数容量を超えない整数値多品種流で総流量が最大となるものを見出す組合せ的な強多項式時間アルゴリズムを与える．本講演は，横井優（国立情報学研究所）との共同研究に基づいている．

7. 室田 一雄 氏（首都大学東京）「離散凸関数の最大最小定理：その具体例と使い方」

離散凸解析では，種々の最大最小定理が知られている．本発表では，ネットワークフローなどの離散構造における公平な資源配分問題（離散変数の辞書式順序最適化）において，最大最小定理が有効に利用できることを説明する．最大最小定理は，通常，Ｍ凸関数やＬ凸関数の一般的な概念を用いて記述されるが，ここでは２次関数や指数関数に対してその具体形を提示して，より身近なものとすることを目指す．

[懇親会]

ワークショップ終了後に，室田 一雄 先生（首都大学東京）の京都大学の名誉教授就任をお祝いするとともに，最適化分野の未来など語らうパーティーを開催しました．

多くの方にご参加いただき，ありがとうございました．