代数的・幾何的アプローチによる離散最適化入門
著：Jesús A. De Loera
著：Raymond Hemmecke
著：Matthias Köppe
内容紹介
本書は、代数的・幾何的の両面からのアプローチにより、離散最適化理論に関するトピックを詳しく取り上げた翻訳書である。
各部で扱われるLLL簡約（第I部）、Graver基底（第II部）、母関数（第III部）、Grobner（グレブナー）基底（第IV部）、正点定理・零点定理に基づく緩和法（第V部）といったトピックは、それぞれ独立した書籍が多数刊行されるほど広く知られる手法である。
これらの理論は、最適化理論全体に於いても重要な基盤であるが、既存の書籍では最適化に関する記述に多くのページは割かれていない。ゆえに本書の大きな特長である「最適化理論と代数学の諸分野との関係を解説する」というコンセプトの下で編纂された書籍は、本書が初めて実施したものと言えるだろう。
現在、様々な大学で理工系の数学者を巻き込んだデータサイエンスに関する組織が次々立ち上がっており、社会的にも最適化理論の知識が広く求められている。
本書は15週の講義を意識し、各章ごとに新しいアイデアやツールへの招待をすることを想定して書かれている。
[原著：Algebraic and Geometric Ideas in the Theory of Discrete Optimization, SIAM, 2013]
目次
第I部 離散最適化の確立された技法
第1章 線形および凸最適化の技法
1.1 凸集合と多面体
1.2 Farkasの補題と多面体の実行可能性
1.2.1 線形方程式系の可解性
1.2.2 線形不等式系の可解性
1.3 Weyl-Minkowskiの表現定理
1.4 錐とポリトープによる多面体の分解
1.5 面, 次元, 端点
1.6 線形最適化の双対性
1.7 計算複雑性について
1.8 楕円体法と凸実行可能性
1.9 楕円体法の応用
1.10 注釈と参考文献
1.11 演習問題
第2章 数の幾何学と整数計画法からの手法
2.1 平面における数の幾何学
2.2 格子と線形Diophantus方程式
2.3 Hermite標準形とSmith標準形
2.4 Minkowskiの定理
2.5 Gordan-Dicksonの補題
2.6 Hilbert基底
2.7 Lenstra, Lenstra, Lovászと最短ベクトル問題
2.8 Lenstraのアルゴリズム，整数実行可能性，および整数最適化
2.9 多面体の整数包と切除平面
2.10 離散最適化における線形と非線形
2.11 注釈と参考文献
2.12 演習問題
第II部 Graver基底の技法
第3章 Graver基底
3.1 はじめに
3.2 Graver基底とその表現の性質
3.3 分離可能な凸整数計画問題の最適性の証拠
3.4 必要な増加ステップの数は？
3.5 Graver最良増加ステップをどのように見つけるか？
3.6 実行可能な初期値を見つける方法
3.7 Graver基底の上限
3.8 Graver基底の計算
3.9 注釈と参考文献
3.10 演習問題
第4章 ブロック構造をもつ整数計画問題におけるGraver基底
4.1 N重ブロック整数計画法
4.1.1 Graver複雑度
4.1.2 多項式サイズのGraver基底
4.1.3 N重IPに対するGraver基底での動的計画法
4.2 二段階確率的整数計画問題
4.2.1 二段階確率的IPに対するGraver基底
4.2.2 増加ベクトルの再構成
4.3 N重4ブロック分割可能行列
4.3.1 N重4ブロック分割可能行列のGraver基底の元に対する上限
4.3.2 実行可能解の構成
4.3.3 Hochbaum-Shanthikumarの近接結果を利用する
4.3.4 制限された問題に対するGraver最良増加
4.3.5 Graver近接アルゴリズム
4.4 注釈と参考文献
4.5 演習問題
第III部 母関数の技法
第5章 母関数の導入
5.1 母関数としての等比級数
5.2 母関数と目的関数
5.3 2変数の母関数
5.4 注釈と参考文献
5.5 演習問題
第6章 多面体の特性関数の分解
6.1 指示関数と包含排除
6.2 Gram-BrianchonとBrion
6.3 錐と多面体の三角形分割
6.4 半開分割を用いた包含排除の回避
6.5 注釈と参考文献
6.6 演習問題
第7章 Barvinokの短い有理母関数
7.1 母関数とBarvinokのアルゴリズム
7.2 母関数の特殊化
7.3 格子点の明示的列挙
7.4 Barvinokのアルゴリズムを用いた整数線形最適化
7.4.1 二分探索と二分法
7.4.2 目的関数の単項式代入
7.4.3 Diggingアルゴリズム:便宜的級数展開
7.5 母関数のブール演算
7.6 整数ベクトル射影
7.7 注釈と参考文献
7.8 演習問題
第8章 総和による大域的混合整数多項式最適化
8.1 近似アルゴリズムとスキーム
8.2 総和法
8.3 ポリトープの整数点上での非負多項式最大化のためのFPTAS
8.4 離散化による混合整数最適化への拡張
8.4.1 グリッド近似による結果
8.4.2 範囲をおさえる技法
8.4.3 定理8.1.3の証明
8.5 非負でない目的関数への拡張
8.6 注釈と参考文献
8.7 演習問題
第9章 整数ベクトル射影による整数線形多目的最適化
9.1 はじめに
9.2 全てのパレート最適値を符号化した有理母関数
9.3 全パレート最適値の効率的リスト化
9.4 多面体ノルムを大域的基準に用いたパレート最適値の選択
9.5 非多面体ノルムを大域的基準に用いたパレート最適値の選択
9.6 注釈と参考文献
9.7 演習問題
第IV部 Gröbner基底の技法
第10章 多項式の計算
10.1 はじめに
10.2 1変数多項式
10.2.1 除算アルゴリズムと最大公約多項式(gcd)
10.2.2 1変数多項式の実根
10.3 多変数多項式の連立方程式
10.4 項順序と多変数多項式の除算アルゴリズム
10.5 Gröbner基底とBuchbergerアルゴリズム
10.6 注釈と参考文献
10.7 演習問題
第11章 整数計画問題でのGröbner基底
11.1 トーリックイデアルとGröbner基底
11.2 トーリックイデアルと整数計画法
11.3 生成集合と格子イデアルのトーリックイデアル
11.4 格子イデアルの生成集合の計算
11.5 注釈と参考文献
11.6 演習問題
第V部 零点定理および正点定理による緩和
第12章 離散最適化における零点定理
12.1 モチベーションと例
12.2 零点定理と組合せ方程式の解法
12.2.1 線形代数緩和
12.2.2 零点定理線形代数アルゴリズム(NulLA)
12.2.3 グラフの3-彩色不可能性を検知する
12.2.4 NulLAの限界とグラフの安定集合
12.3 零点定理の簡明な証明
12.3.1 1変数多項式の場合の証明
12.3.2 終結式と多変数多項式
12.4 注釈と参考文献
12.5 演習問題
第13章 多項式の正値性と大域最適化
13.1 制約のない多項式最適化と平方和
13.2 正点定理と半正定値計画緩和
13.3 組合せ問題の整数包の近似
13.4 注釈と参考文献
13.5 演習問題
第14章 エピローグ
14.1 線形最適化における代数的およびトポロジー的アイディア
14.2 整数計画問題における母関数を用いた別の技法
14.3 Gomoryの群緩和のバリエーション
14.4 行列解析と表現論との関連
