代数的・幾何的アプローチによる離散最適化入門

本書は、代数的・幾何的の両面からのアプローチにより、離散最適化理論に関するトピックを詳しく取り上げた翻訳書である。
各部で扱われる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基底での動的計画法
　ほか

本の帯に関して

帯つきでの出荷はお約束しておりません。
商品ページに、帯のみに付与される特典物等の表記がある場合でも、確実に帯つきでの出荷はお約束しておりません。
また、帯は商品の一部ではなく「広告扱い」のため、帯の有無・破損による交換や返品は承っておりません。

版・表紙について

版・表紙（カバー）のご指定は承っておりません。ご注文いただくタイミングによっては、お届けする商品の版や表紙が商品ページ上のものとは異なる場合がございます。
また、初版にのみにお付けしている特典（初回特典、初回仕様特典）がある商品は、商品ページに特典の表記がされている場合でも、無くなり次第終了となります。