cover.png#线性规划与对偶

线性规划 (Linear Programming, LP) 在算法中有两类作用：

1. 作为建模工具：很多优化问题可以直接写成 LP，或者写成 LP 的松弛形式
2. 作为证明工具：对偶性可以把一个优化问题的上界或下界转化成另一个自然问题

前面网络流中的最大流最小割定理，本质上就可以从 LP 对偶的角度理解：

\[\text{max flow} = \text{min cut}\]

---

线性规划

线性规划由三部分组成：

• 决策变量：\(x_1,x_2,\ldots,x_n\)
• 线性目标函数：例如最大化 \(c_1x_1+\cdots+c_nx_n\)
• 线性约束：变量之间只允许线性不等式或等式

如果目标函数或约束中出现 \(x_1x_2\)、\(x_1^2\)、\(\log x_3\) 之类的非线性项，就不再是线性规划。

标准型

本节主要使用如下标准型：

\[ \begin{aligned} \max \quad & c^T x \\ \text{s.t.}\quad & Ax \leq b \\ & x \geq 0 \end{aligned} \]

其中：

• \(x=(x_1,\ldots,x_n)^T\) 是决策变量
• \(c=(c_1,\ldots,c_n)^T\) 是目标函数系数
• \(b=(b_1,\ldots,b_m)^T\) 是约束右端项
• \(A=[a_{ij}]_{m\times n}\) 是约束矩阵

展开后就是：

\[ \begin{aligned} \max\quad & c_1x_1+c_2x_2+\cdots+c_nx_n \\ \text{s.t.}\quad & a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n \leq b_1 \\ & a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n \leq b_2 \\ & \cdots \\ & a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n \leq b_m \\ & x_j \geq 0,\quad 1\leq j\leq n \end{aligned} \]

满足所有约束的 \(x\) 称为可行解。使目标函数达到最大值的可行解称为最优解。

常见形式转换

不同教材的标准型可能略有不同，但它们之间可以互相转换：

原形式	转换方法
最小化 \(\min c^Tx\)	改写为最大化 \(\max -c^Tx\)
约束 \(a_i^Tx\geq b_i\)	两边乘 \(-1\)，得到 \(-a_i^Tx\leq -b_i\)
等式 \(a_i^Tx=b_i\)	拆成 \(a_i^Tx\leq b_i\) 和 \(a_i^Tx\geq b_i\)
自由变量 \(x_j\in\mathbb{R}\)	写成 \(x_j=x_j^+-x_j^-\)，其中 \(x_j^+,x_j^-\geq 0\)

所以只要系数是有理数，LP 可以用统一的矩阵形式处理。

---

几何直观

每一个线性不等式 \(a_i^T x \leq b_i\)

在 \(n\) 维空间中对应一个半空间。可行域 \(\{x| Ax\leq b,\ x\geq 0\}\) 就是若干个半空间的交。

凸性

LP 的可行域是凸集。若 \(p,q\) 都是可行解，那么对任意 \(\lambda\in[0,1]\)：

\[ A(\lambda p+(1-\lambda)q) =\lambda Ap+(1-\lambda)Aq \leq \lambda b+(1-\lambda)b=b \]

并且

\[ \lambda p+(1-\lambda)q\geq 0 \]

所以连接 \(p\) 和 \(q\) 的整条线段仍在可行域中。

最优解的位置

目标函数 \(c^Tx\) 的等值面是若干个互相平行的超平面，并且都垂直于向量 \(c\)。对最大化问题来说，相当于把这个超平面沿 \(c\) 的方向平移，直到最后一次接触可行域。

如果可行域非空且目标函数有界，则最优值存在；若最优解唯一，它一定在可行多面体的某个顶点上。

这也是单纯形法的直观基础：从一个顶点移动到相邻顶点，不断改进目标函数。

---

基本可行解

对单纯型法，通常会把“顶点”改写成代数语言，也就是基本可行解 (basic feasible solution, BFS)

考虑标准型：

\[ \begin{aligned} \max\quad & c^Tx\\ \text{s.t.}\quad & Ax=b\\ & x\geq 0 \end{aligned} \]

假设 \(A\) 是 \(m\times n\) 矩阵，且 \(\text{rank}(A)=m\)。选择 \(m\) 个线性无关的列组成基矩阵 \(B\)，把变量分成：

• 基变量 \(x_B\)
• 非基变量 \(x_N\)

令所有非基变量为 0：

\[ x_N=0 \]

再解：

\[ Bx_B=b \]

如果得到的 \(x_B\geq 0\)，则 \(x\) 是一个基本可行解

几何意义

基本可行解对应可行多面体的顶点。直观上，在 \(n\) 维空间中，一个顶点由足够多的紧约束共同确定。

对标准型 \(Ax=b,x\geq 0\) 来说，\(Ax=b\) 已经提供 \(m\) 个等式约束；再把 \(n-m\) 个变量固定为 0，就得到一个候选顶点。

为什么最优解可以只看 BFS

若 LP 有最优解且目标函数有界，则存在一个最优基本可行解。

原因是：线性目标函数在凸多面体上的最优值可以在极点处取得，而极点正是基本可行解。

所以理论上可以枚举所有基：

\[ \binom{n}{m} \]

但这个数量通常是指数级的。单纯形法的思想不是枚举所有顶点，而是沿着相邻 BFS 移动，每次让目标函数变好。

退化

如果某个基本可行解中有基变量也等于 0，就称为退化 (degeneracy)。

退化会导致单纯形法可能在不同基之间移动但点本身不变，从而出现循环。实际算法会使用 Bland 规则等 pivot 规则避免循环。

---

建模示例

饮食问题

假设每天可以选择面包、酸奶、花生酱三类食物：

食物	碳水	蛋白质	脂肪	铁	价格
1 片面包	30	5	1.5	10	30
1 杯酸奶	10	9	2.5	0	80
2 茶匙花生酱	6	8	18	6	20
最低需求	300	50	70	100	-

令：

• \(x_1\) 表示面包数量
• \(x_2\) 表示酸奶数量
• \(x_3\) 表示花生酱数量

目标是用最低成本满足营养需求：

\[ \begin{aligned} \min\quad & 30x_1+80x_2+20x_3\\ \text{s.t.}\quad & 30x_1+10x_2+6x_3\geq 300\\ & 5x_1+9x_2+8x_3\geq 50\\ & 1.5x_1+2.5x_2+18x_3\geq 70\\ & 10x_1+6x_3\geq 100\\ & x_1,x_2,x_3\geq 0 \end{aligned} \]

这是一个 LP，因为目标函数和全部约束都是变量的线性函数

最大流的 LP 表述

对流网络 \(G=(V,E)\)，每条边 \((u,v)\) 有容量 \(c(u,v)\)。令 \(f_{uv}\) 表示边 \((u,v)\) 上的流量。

最大流可以写成：

\[ \begin{aligned} \max\quad & \sum_{v:(s,v)\in E} f_{sv}\\ \text{s.t.}\quad & 0\leq f_{uv}\leq c(u,v),\quad \forall (u,v)\in E\\ & \sum_{u:(u,v)\in E} f_{uv} =\sum_{w:(v,w)\in E} f_{vw}, \quad \forall v\in V\setminus\{s,t\} \end{aligned} \]

第一类约束是容量约束，第二类约束是流量守恒。

如果使用路径分解，也可以令 \(f_p\) 表示 \(s\) 到 \(t\) 的路径 \(p\) 上发送的流量。设 \(\mathcal{P}\) 是所有 \(s\)-\(t\) 路径集合，则：

\[ \begin{aligned} \max\quad & \sum_{p\in\mathcal{P}} f_p\\ \text{s.t.}\quad & \sum_{p:e\in p} f_p\leq c_e,\quad \forall e\in E\\ & f_p\geq 0,\quad \forall p\in\mathcal{P} \end{aligned} \]

这个形式的变量可能指数多，但它的对偶非常自然。

---

LP 对偶

考虑标准型原问题 (Primal)：

\[ \begin{aligned} (P)\quad \max\quad & c^Tx\\ \text{s.t.}\quad & Ax\leq b\\ & x\geq 0 \end{aligned} \]

它的对偶问题 (Dual) 是：

\[ \begin{aligned} (D)\quad \min\quad & b^Ty\\ \text{s.t.}\quad & A^Ty\geq c\\ & y\geq 0 \end{aligned} \]

这里 \(y_1,\ldots,y_m\) 是对偶变量。

对偶的构造规则

原问题	对偶问题
最大化	最小化
变量 \(x_j\)	对偶约束
约束 \(i\)	对偶变量 \(y_i\)
目标系数 \(c\)	对偶约束右端
约束右端 \(b\)	对偶目标系数
矩阵 \(A\)	转置为 \(A^T\)

一句话概括：对偶变量对应原约束，对偶约束对应原变量，目标函数和右端项交换，矩阵转置。

一个例子

原问题：

\[ \begin{aligned} (P)\quad \max\quad & x_1+x_2\\ \text{s.t.}\quad & 4x_1+x_2\leq 2\\ & x_1+2x_2\leq 1\\ & x_1,x_2\geq 0 \end{aligned} \]

对偶问题：

\[ \begin{aligned} (D)\quad \min\quad & 2y_1+y_2\\ \text{s.t.}\quad & 4y_1+y_2\geq 1\\ & y_1+2y_2\geq 1\\ & y_1,y_2\geq 0 \end{aligned} \]

原问题中，任何非负线性组合

\[ y_1(4x_1+x_2)+y_2(x_1+2x_2) \]

只要能逐项覆盖 \(x_1+x_2\)，就给出了原目标函数的一个上界。也就是说，只要

\[ \begin{cases} 4y_1+y_2\geq 1\\ y_1+2y_2\geq 1 \end{cases} \]

就有：

\[ x_1+x_2 \leq y_1(4x_1+x_2)+y_2(x_1+2x_2) \leq 2y_1+y_2 \]

因此对偶问题就是在所有这种上界中找最紧的

这个例子的最优解为：

\[ x^*=\left(\frac{3}{7},\frac{2}{7}\right),\quad y^*=\left(\frac{1}{7},\frac{3}{7}\right) \]

两边目标值都是：

\[ c^Tx^*=b^Ty^*=\frac{5}{7} \]

---

弱对偶

弱对偶定理：若 \(x\) 是原问题的可行解，\(y\) 是对偶问题的可行解，则：

\[ c^Tx\leq b^Ty \]

点击查看证明

因为 \(A^Ty\geq c\) 且 \(x\geq 0\)，所以：

\[ c^Tx\leq (A^Ty)^Tx \]

又因为 \((A^Ty)^Tx=y^TAx\)，并且 \(Ax\leq b\)、\(y\geq 0\)，所以：

\[ y^TAx\leq y^Tb \]

合并得到：

\[ c^Tx\leq (A^Ty)^Tx=y^TAx\leq y^Tb=b^Ty \]

弱对偶说明：

• 原问题任意可行解的目标值 \(\leq\) 对偶问题任意可行解的目标值
• 对最大化原问题来说，对偶可行解提供上界
• 如果找到一对可行解 \(x,y\)，并且 \(c^Tx=b^Ty\)，那么二者都最优

---

强对偶

强对偶定理：若原问题可行且有界，则对偶问题也可行且有界，并且二者最优值相等。

也就是说，若 \(x^*\) 和 \(y^*\) 分别是原问题和对偶问题的最优解，则：

\[ c^Tx^*=b^Ty^* \]

强对偶给出了一种证明最优性的方式：

1. 给出原问题可行解 \(x\)
2. 给出对偶问题可行解 \(y\)
3. 验证 \(c^Tx=b^Ty\)

只要三步都成立，就不需要再枚举或搜索其他解，\(x\) 和 \(y\) 都是最优解。

可行性和有界性的关系

弱对偶可以推出一些直接结论：

• 若原问题无界，则对偶问题不可行
• 若对偶问题无界，则原问题不可行
• 原问题不可行时，对偶可能无界，也可能不可行
• 对偶问题不可行时，原问题可能无界，也可能不可行

所以“不可行”和“无界”不是简单的一一对应关系。

---

Farkas 引理与证书

Farkas 引理的一种形式是：对系统

\[ Ax\leq b \]

恰好有以下两件事中的一件成立：

1. 存在 \(x\) 使得 \(Ax\leq b\)
2. 存在 \(y\geq 0\)，使得 \(y^TA=0\) 且 \(y^Tb<0\)

第二种情况中的 \(y\) 是一个不可行性证书

点击查看为什么 $y$ 可以证明不可行

如果存在 \(x\) 满足 \(Ax\leq b\)，又存在 \(y\geq 0\)，则：

\[ y^TAx\leq y^Tb \]

若同时 \(y^TA=0\)，则左边为：

\[ y^TAx=0 \]

但如果 \(y^Tb<0\)，就得到：

\[ 0<0 \]

矛盾。

所以只要找到这样的 \(y\)，就能证明原不等式系统没有解。

与对偶的关系

弱对偶说明：对偶可行解给出原问题的上界。强对偶说明：如果原问题有最优解，则存在一个最紧的上界。

Farkas 引理则处理另一类问题：当原问题没有可行解时，也存在一个短证书证明不可行。

从算法复杂性的角度看，这很重要：LP 不只是“能找到最优解”，还可以给出可验证的最优性证书或不可行性证书。

证书视角总结

情况	证书
原问题可行且最优值为 \(z\)	原可行解 \(x\) 与对偶可行解 \(y\)，满足 \(c^Tx=b^Ty=z\)
原问题不可行	Farkas 证书 \(y\)，推出线性组合矛盾
原问题无界	一个可行方向 \(d\)，满足 \(Ad\leq 0\)、\(d\geq 0\) 且 \(c^Td>0\)

这也是 LP 在理论计算机科学中常被当作“证明系统”的原因。

---

互补松弛

对标准型：

\[ \begin{aligned} (P)\quad \max\quad & c^Tx\\ \text{s.t.}\quad & Ax\leq b\\ & x\geq 0 \end{aligned} \]

\[ \begin{aligned} (D)\quad \min\quad & b^Ty\\ \text{s.t.}\quad & A^Ty\geq c\\ & y\geq 0 \end{aligned} \]

定义原约束的松弛量：

\[ b_i-A_i x \]

定义对偶约束的松弛量：

\[ (A^T y)_j-c_j \]

互补松弛条件：

\[ y_i(b_i-A_i x)=0,\quad 1\leq i\leq m \]

\[ x_j((A^Ty)_j-c_j)=0,\quad 1\leq j\leq n \]

等价地说：

• 如果 \(y_i>0\)，则原问题第 \(i\) 个约束必须取等号
• 如果原问题第 \(i\) 个约束没有取等号，则 \(y_i=0\)
• 如果 \(x_j>0\)，则对偶问题第 \(j\) 个约束必须取等号
• 如果对偶问题第 \(j\) 个约束没有取等号，则 \(x_j=0\)

点击查看互补松弛为什么等价于最优

由弱对偶证明中的差值可以写成：

\[ b^Ty-c^Tx =y^T(b-Ax)+x^T(A^Ty-c) \]

其中 \(x,y,b-Ax,A^Ty-c\) 都逐项非负。

因此 \(b^Ty=c^Tx\) 当且仅当：

\[ y^T(b-Ax)=0 \]

且

\[ x^T(A^Ty-c)=0 \]

因为每一项都是非负数，所以这等价于逐项乘积为 0：

\[ y_i(b_i-A_i x)=0,\quad x_j((A^Ty)_j-c_j)=0 \]

再由弱对偶，目标值相等说明二者都是最优解。

算法设计视角

互补松弛可以看成一个通用的 primal-dual 算法设计范式：

1. \(x\) 对原问题可行
2. \(y\) 对对偶问题可行
3. \(x,y\) 满足互补松弛

如果能同时满足这三条，就得到最优解。很多算法会在过程中始终维护其中两条，然后逐步逼近第三条。

---

最大流最小割的 LP 视角

使用路径流形式：

\[ \begin{aligned} (P)\quad \max\quad & \sum_{p\in\mathcal{P}} f_p\\ \text{s.t.}\quad & \sum_{p:e\in p} f_p\leq c_e,\quad \forall e\in E\\ & f_p\geq 0,\quad \forall p\in\mathcal{P} \end{aligned} \]

将其写成矩阵形式：

\[ \max\quad \mathbf{1}^T f \quad \text{s.t.}\quad Af\leq c,\ f\geq 0 \]

其中 \(A_{ep}=1\) 当且仅当边 \(e\) 在路径 \(p\) 上。

它的对偶为：

\[ \begin{aligned} (D)\quad \min\quad & \sum_{e\in E} c_e y_e\\ \text{s.t.}\quad & \sum_{e\in p} y_e\geq 1,\quad \forall p\in\mathcal{P}\\ & y_e\geq 0,\quad \forall e\in E \end{aligned} \]

割给出对偶可行解

给定任意 \(s\)-\(t\) 割 \((S,T)\)，令：

\[ y_e= \begin{cases} 1 & e\in \delta^+(S)\\ 0 & \text{otherwise} \end{cases} \]

任意 \(s\)-\(t\) 路径都必须至少穿过一次割边，所以：

\[ \sum_{e\in p}y_e\geq 1 \]

因此 \(y\) 是对偶可行解。对应的对偶目标值为：

\[ \sum_{e\in E}c_e y_e =\sum_{e\in \delta^+(S)}c_e =c(S,T) \]

由弱对偶可知：

\[ \text{任意流值}\leq \text{任意割容量} \]

这正是最大流最小割定理中的“上界”方向。

从对偶到最小割

强对偶说明最大路径流的 LP 值等于对偶 LP 的最优值。另一方面，对偶 LP 虽然允许 \(y_e\) 取分数，但最优解可以对应到一个割。

直观理解是：\(y_e\) 可以看成边长，约束要求每条 \(s\)-\(t\) 路径长度至少为 1。设 \(d(v)\) 是从 \(s\) 到 \(v\) 的最短距离，则 \(d(t)\geq 1\)。在阈值 \(\alpha\in[0,1)\) 处取集合

\[ S_\alpha=\{v:d(v)\leq \alpha\} \]

会得到一个 \(s\)-\(t\) 割。通过对 \(\alpha\) 做平均，可以证明存在某个割的容量不超过 \(\sum_e c_e y_e\)。

因此：

\[ \max \text{ flow} =\min \text{ dual value} =\min \text{ cut} \]

这说明最大流最小割定理也可以看作 LP 强对偶的一个特例。

---

二分图匹配的 LP 视角

设二分图 \(G=(L,R,E)\)，每条边 \(e\) 有成本 \(c_e\)。最小费用完美匹配可以写成：

\[ \begin{aligned} (P\text{-BM})\quad \min\quad & \sum_{e\in E} c_e x_e\\ \text{s.t.}\quad & \sum_{e\in \delta(v)}x_e=1,\quad \forall v\in L\cup R\\ & x_e\geq 0,\quad \forall e\in E \end{aligned} \]

如果要求 \(x_e\in\{0,1\}\)，这就是整数规划。对二分图匹配来说，去掉整数约束后 LP 仍有整数最优解，这是二分图匹配多面体的一个重要性质。

对偶

给每个顶点 \(v\) 一个对偶变量 \(p_v\)。对偶问题是：

\[ \begin{aligned} (D\text{-BM})\quad \max\quad & \sum_{v\in L\cup R}p_v\\ \text{s.t.}\quad & p_u+p_v\leq c_{uv},\quad \forall (u,v)\in E \end{aligned} \]

把约束改写为：

\[ c_{uv}-p_u-p_v\geq 0 \]

这里

\[ c_{uv}-p_u-p_v \]

称为边 \((u,v)\) 的约化费用 (reduced cost)。

互补松弛解释

若边 \((u,v)\) 在最优匹配中被选中，即 \(x_{uv}>0\)，则对应的对偶约束必须取等号：

\[ p_u+p_v=c_{uv} \]

也就是匹配边的约化费用为 0。

Hungarian 算法可以从 primal-dual 角度理解：

• 维护对偶可行性：所有边的约化费用非负
• 维护已选边的互补松弛：匹配边的约化费用为 0
• 不断改进原问题可行性：逐步构造完美匹配

当最终得到完美匹配时，由互补松弛可知它就是最小费用完美匹配。

---

整数性、全酉矩阵与 LP 松弛

很多组合优化问题本来带有 0-1 约束：

\[ x_i\in\{0,1\} \]

如果把它放宽成：

\[ 0\leq x_i\leq 1 \]

就得到一个 LP，称为原整数规划的 LP 松弛 (LP relaxation)。

LP 松弛一般可能得到分数解。但在一些特殊问题中，松弛后的 LP 仍然总能得到整数最优解，这就是整数性 (integrality)。

全酉矩阵

一个矩阵 \(A\) 称为全酉矩阵 (totally unimodular, TU)，如果它的每个方阵子式的行列式都属于：

\[ \{-1,0,1\} \]

一个重要结论是：

若 \(A\) 是全酉矩阵，且 \(b\) 是整数向量，则多面体

\[ \{x:Ax\leq b,\ x\geq 0\} \]

的每个顶点都是整数点。

因此，对这样的 LP，只要目标函数是线性的，必然存在整数最优解。

网络流的整数性

最大流的约束矩阵可以看作有向图的点边关联矩阵，而这类矩阵是全酉的。因此如果容量都是整数，则最大流 LP 存在整数最优解。

这从 LP 角度解释了前面网络流中的整数流定理：

\[ \text{整数容量}\Rightarrow \text{存在整数最大流} \]

二分图匹配的整数性

二分图匹配的 LP：

\[ \sum_{e\in\delta(v)}x_e\leq 1,\quad x_e\geq 0 \]

在二分图中也有整数顶点。等价地说，二分图匹配多面体的极点都是 0-1 向量。

这也是为什么二分图匹配可以用 LP 精确求解，而一般图匹配需要额外的奇集约束；如果只写“每个点最多匹配一次”的约束，一般图会出现分数极点。

LP 松弛与近似算法

对 NP-hard 问题，LP 松弛通常不能直接给出整数最优解，但可以给出近似算法。

以 Vertex Cover 为例：

\[ \begin{aligned} \min\quad & \sum_{v\in V}x_v\\ \text{s.t.}\quad & x_u+x_v\geq 1,\quad \forall (u,v)\in E\\ & 0\leq x_v\leq 1,\quad \forall v\in V \end{aligned} \]

解出 LP 最优解 \(x^*\) 后，取：

\[ C=\{v:x_v^*\geq 1/2\} \]

则 \(C\) 是一个顶点覆盖。因为对每条边 \((u,v)\)，有 \(x_u^*+x_v^*\geq 1\)，所以至少有一个端点的 LP 值不小于 \(1/2\)。

并且：

\[ |C|\leq 2\sum_{v\in V}x_v^* \]

由于 LP 最优值不超过整数最优值：

\[ \sum_v x_v^*\leq OPT \]

所以：

\[ |C|\leq 2OPT \]

这就是 Vertex Cover 的一个 2-近似算法，也是公开课中常用来说明“LP 松弛 + 舍入”的例子。

整数间隙

LP 松弛的最优值记为 \(OPT_{LP}\)，整数问题的最优值记为 \(OPT_{IP}\)。对最小化问题，通常有：

\[ OPT_{LP}\leq OPT_{IP} \]

二者之间的比值称为整数间隙 (integrality gap)。

整数间隙越小，说明 LP 松弛越接近原问题；若间隙为 1，则 LP 松弛是精确的。

---

LP 算法

线性规划可以在多项式时间内求解，并且实践中也有非常成熟的求解器。

算法	特点
Simplex 单纯形法	实际效果很好，但最坏情况可能指数时间
Ellipsoid 椭球法	第一个多项式时间 LP 算法，理论意义大，实际较慢
Karmarkar 内点法	多项式时间，实践中也有竞争力
现代求解器	Gurobi、CPLEX、LINDO、SCIP 等

算法课中通常不重点实现通用 LP 求解器，而是使用 LP 的建模能力和对偶性来设计、分析更具体的问题。

---

小结

线性规划的核心内容可以概括为：

• LP 的可行域是凸多面体，线性目标函数的最优解可在顶点处取得
• 标准型原问题 \(\max\{c^Tx:Ax\leq b,x\geq 0\}\) 的对偶是 \(\min\{b^Ty:A^Ty\geq c,y\geq 0\}\)
• 弱对偶给出上界或下界，强对偶说明最优界可以达到
• 互补松弛把“目标值相等”拆成逐项条件，是 primal-dual 算法的基础
• 最大流最小割、二分图匹配等问题都可以从 LP 对偶角度重新解释
• Farkas 引理提供不可行性证书，全酉矩阵解释了网络流和二分图匹配中的整数性
• 对 NP-hard 问题，LP 松弛常用于设计近似算法，整数间隙衡量松弛质量

LP 的意义不只是“能求解一类连续优化问题”，更重要的是它提供了一种统一语言：把算法、证明、上界、下界和结构定理放在同一个框架中。