1
15.083J/6.859J 整数优化
第 13-14 讲：代数几何和整数优化
纠正排印错误和错误。第 7.4 节 完全重写。
2
第7章
代数几何和整数优化
内 容
7.1. 代数几何知识背景
7.2. 0-1 规划的应用
7.3. 用于整数优化的 Grobner 基
7.4. 实数代数几何的应用
7.5. 多面体整数点的生成函数
7.6. 总结
7.7. 练习
7.8. 注释与参考资料
3
本章我们介绍几种源于代数几何的整数优化办法。虽然，本章讨论的方法尚未产生实际
的算法，但由于这些方法是基于数学界相当活跃领域中一些深入而巧妙的思想，将来很
可能会导出有效的算法。
为使本章内容上的完整，我们先讨论贯穿本章始终的代数几何的基础概念。应用代
数几何中经典的概念，我们得到整数优化的 Farkas 引理、0-1 规划算法和整数优化算法。
进一步，我们会介绍实数代数几何的相关概念，矩问题，并得到整数优化的半定松弛的
一个收敛序列（在 0-1 规划中，为有限序列）。最后，我们介绍锥的分解的一种有力观
点，并由此得到，在固定维的多面体上计数整数点的一个多项式时间算法。
7.1 代数几何背景知识
本章所讲的基本代数对象都是实数或复数域内的多项式。
本章我们将用
k 表示
R
或 C ，若某个结果只在 Ck
=
时适用，我们会另作说明。
维数为 1 时，单项式可自然地按其次数排序，即：
，多
维时可以定义多种排序原则。
定义 7.1 （多项式）
（
a
） 以 为变量的单项式是下述形式的积
其中 。
（
b
） 多项式是下述形式的表达式
其中 ， 有限，且对所有 ， 。
的系数为 或 的多项式集记为 。
4
单项式序的重要例子包括：
（a）字典序
对每个
n
Z
+
∈
βα
, ，若向量差
n
Z∈−
βα
的最左非零元素是正的，则
β
α
lex
>
（或
βα
xx
lex
> ）。例如： ，因为
。
（b）分级字典序
对每个
，有 ，如果
换句话说，分级字典序是总次数优先的，然后才考虑字典序。例如：
，因为 。
（c）分级字典逆序
对每个
，我们称 ，如果
，或 ，并且
的最右非零元素为负值。例如，
，因为 且
定义 7.2 单项式序
上的单项式序，是在
n
Z
+
上的任何
>
关系。或等价地，是在单项式
α
x
集
合上的任何关系，
n
Z
+
∈
α ，满足：
（
a
）
>
是
n
Z
+
上的全序关系；
（
b
）若
β
α
>
且
n
Z
+
∈
γ ，则
γ
β
γ
α
+
>
+
；
（
c
）任何
n
Z
+
的非空子集都有
>
关系下最小元素。
5
。
（d）向量引导序
我们考虑一向量
，并对每个 ，我们有 （或 ）
如果，
注意：
≥c 0 的条件是很重要的。因为如果
<
c
0，则定义 7.2 的条件（c）不满
足。
例 7.1 在不同的单项式序方法下，多项式
的写法如下：
（a）字典序
（b）分级字典序
（c）分级字典逆序
（d）
的引导向量序
注意复数域
是代数封闭的，因为非常数的多项式在 中肯定有根。而实数域
Rk = 不是代数封闭的，因为在这个域中，方程
01
2
=+x
就不存在实数根。
