4 - 线性、二次与锥优化

在打开求解器之前，先把桌面腾出一小块地方，手边放一张空白纸。今天这张纸比任何软件都重要：这一篇里每一个关键模型，都要先经得起一次手算。

优化问题常常披着一层吓人的外衣：向量、锥、乘子、矩阵不等式，还有一眼看不懂的求解器日志。但它真正关心的问题其实很朴素：在所有满足规则的方案中，哪一个最符合我们的目标？ 这一篇博客会依次学习三种表达这类问题的语言：线性规划（LP）、二次规划（QP）和二阶锥规划（SOCP）。我们不从软件按钮开始，而是从“究竟要做什么决定”开始，逐步得到变量、目标、约束和验证方法。

贯穿全文的竞赛案例来自 2024 年全国大学生数学建模竞赛 C 题的农作物种植规划。公开的优秀论文需要同时处理地块、季节、作物、轮作、产量、价格、成本和需求。它很适合说明一个事实：写一句“让利润最大”并不难，真正困难的是保证求解器理解的世界与真实种植规则一致。本文会独立重建模型，而不是照抄获奖论文的公式和结果。原始材料可在国赛优秀论文展示页面查阅。

优化模型的五项契约

一个可以被审查的优化模型必须明确给出：决策变量、目标函数、约束条件、输入数据和验证方式。少掉任何一项，求解器即使给出数字，也还不能构成可信的决策。

1. 从真实决策到数学规划

假设校园餐厅中午要决定做多少盘米饭套餐和沙拉套餐。每盘米饭套餐贡献利润 36 元，使用 4 千克米和 2 分钟人工；每盘沙拉贡献利润 30 元，需要 3 分钟人工。现有 80 千克米和 72 分钟人工，市场最多能卖出 18 盘米饭套餐和 16 盘沙拉。

先不要算。我们能够控制的并不是利润、库存或需求，而是两种套餐的数量。令

$米饭套餐数量沙拉套餐数量$

于是模型是

目标和约束都是变量的加权和，所以它是线性规划。这里的“线性”并不等于问题很小，而是表达式里没有、或这类非线性项。

一般的 LP 可以写成

是我们能决定的量，是目标系数，的每一行代表一条规则，是数据。矩阵写法很紧凑，但单位不能被隐藏：把千克与分钟直接相加，不是高级，而是错误。

自然语言中，“不超过、容量、至多”通常对应；“至少、覆盖、必须达到”对应；“守恒、平衡、恰好”等词对应等式。若出现“只有启用地块才能种作物 ”，还需要二元变量和

回答“种多少”，回答“种不种”。含有整数或二元决策的线性模型称为混合整数线性规划（MILP）。

2. 可行域、顶点与线性规划的几何

餐厅模型中的每个不等式都表示一个半平面。所有半平面的交集就是可行域。线性约束的交集是凸集，因此连接任意两个可行点的线段仍然可行。

目标等值线是一组平行线。逐渐增大，直线最后一次接触可行多边形的地方就是最优解；若目标没有恰好平行于某条边，接触点会是一个顶点。

手算候选顶点。人工约束与沙拉需求边界相交时，，得到，利润 912。米饭需求边界与人工约束相交时，，得到，利润 1008。检查其他顶点后，最优。

这道手算题也是代码的单元测试。如果求解器返回，说明需求约束没有正确加入；如果目标值对但方案不同，则要判断是否存在多重最优解或输出精度问题。

凸集满足

线性目标又满足

所以内部的凸组合不可能严格优于两个端点。这解释了为什么单纯形法可以沿顶点搜索。

3. 对偶：稀缺资源值多少钱

考虑原问题

给每一项资源赋予非负价格。如果，那么任何可行解都满足

因此是利润上界。寻找最紧上界得到对偶问题

这就是弱对偶。满足常见条件时，强对偶保证原问题和对偶问题的最优值相等。最优对偶变量是影子价格：资源小幅增加时，最优目标大约增加。

餐厅最优解只用了 72 千克米，米的约束没有卡住方案，所以其影子价格为 0；人工和米饭套餐需求约束是紧的。互补松弛写为

这让我们不只说“最优利润是 1008”，还能说明究竟是哪一种资源限制了利润、放宽限制是否值得。

4. 二次规划：风险、偏差与边际代价

线性目标假设边际价值不变，但很多问题并非如此。调度会惩罚偏离目标，投资会权衡收益与方差，控制会惩罚动作突变。这些问题常写成

当对称时，，。若，问题是凸的，局部最小值就是全局最小值；若，在凸可行域内最优解唯一。

最小二乘就是典型 QP：

所以。令梯度为零得到正规方程，但数值计算更推荐 QR 或 SVD，因为显式形成会把条件数平方。

若两台发电机成本为，且，在容量边界未激活时，拉格朗日条件给出

也就是说，所有没有顶到容量边界的机组边际成本相等。这才是调度结果背后的经济解释。

5. KKT 条件

对，约束，定义

KKT 条件包括

$驻点条件原始可行对偶可行互补松弛$

对满足 Slater 条件等约束资格条件的凸问题，KKT 既必要又充分；在非凸问题中，它可能只描述局部驻点。

例如把点投影到半空间。若不可行，边界必须激活。由驻点条件与可得

修正方向正好是边界法向量，修正幅度正好让点回到边界。

6. 范数、不确定性与二阶锥

标准二阶锥是。SOCP 的典型约束为

它能够表达许多凸二次约束、投资风险限制和椭球不确定性下的鲁棒约束。

假设资源系数不确定：

最坏扰动是。由柯西—施瓦茨不等式，最大值为，所以无穷多条不确定约束等价于

这是一条 SOCP 约束。可见，不确定性并不必然意味着只能模拟；选对不确定集合后，可以得到可精确求解的鲁棒对应问题。

7. 求解算法与数值证据

单纯形法沿可行域顶点移动；内点法在内部沿中心路径前进；一阶法使用梯度和投影，单步便宜但高精度时迭代较多。对，对数障碍方法求解

当，障碍问题的最优点沿中心路径逼近原问题最优点。

模型结构决定算法：线性且含离散变量时用 LP/MILP；时用凸 QP；出现欧氏范数和椭球鲁棒约束时用 SOCP。不要因为遗传算法容易描述，就把一个本来能获得最优性界的凸问题交给启发式方法。

8. 获奖论文案例：2024 国赛农作物种植规划

令

$第年第季在地块种作物的面积$

表示是否种植。面积为，亩产量为，成本，价格，预计需求。总产量为

不要直接在目标中写。引入原价销量和超额销量：

若超产部分按半价出售，目标为

地块容量、启用关系、禁止重茬与三年内至少种一次豆类可分别写成

再把不适合作物、地块或季节的固定为 0，便得到 MILP。公开优秀论文采用差分进化遗传算法。我们的审查重点不是否定启发式方法，而是先利用问题的线性结构建立精确基准：即使完整实例很大，也可以抽取两年、几个地块和几种作物，用 MILP 或穷举得到可验证答案。

例如两个 10 亩地块、两年、三种作物。地块 1 只能种，地块 2 只能种；两年中至少种一次豆类，且不能连续种同一作物。单位利润为元/亩时，最优轮作为地块 1 的与地块 2 的，总利润

这个小例子可以同时检查兼容关系、轮作、豆类覆盖和利润核算。小模型没有通过，就不应相信七年大表格。

9. 实现与核验

import cvxpy as cp
import numpy as np

profit = np.array([36.0, 30.0])
x = cp.Variable(2, nonneg=True)
constraints = [4*x[0] <= 80,
               2*x[0] + 3*x[1] <= 72,
               x[0] <= 18, x[1] <= 16]
problem = cp.Problem(cp.Maximize(profit @ x), constraints)
problem.solve()
print(x.value, problem.value)
print([c.dual_value for c in constraints])

求解后要重新计算目标，逐条检查约束，核对单位与整数性。原始可行残差可以写成

$$r_p=\max{|Ex-d|\infty,\ |(Ax-b)+|_\infty}.$$

整数模型还应报告当前最好可行值、最好界和相对间隙

求解器超时不等于失败；如果已经得到 0.4% 的间隙，它可能足以支持决策。真正有问题的是完全不报告间隙。

10. 如何写出可信的优化报告

读者应当能够沿着报告还原整个链条：变量的含义和单位、目标的会计构成、约束的现实来源、模型为何属于 LP/QP/SOCP、求解器为何适合、小规模实例如何验证、残差和最优性界是多少、敏感性如何影响建议，以及模型有意忽略了什么。

LP 教会我们严谨翻译规则；QP 教会我们处理曲率、风险和折中；SOCP 告诉我们许多带范数的非线性问题仍然可以保持凸性。比算法名字更重要的是共同的习惯：忠实表达决策，诚实利用结构，把验证当作数学的一部分。

离开之前留一个小彩蛋：把餐厅模型的人工从 72 分钟改成 73 分钟，最优利润的增量恰好等于对偶给出的人工影子价格。继续一分钟一分钟增加，找到这个预测第一次失效的位置。那个拐点会让你真正看见“局部敏感性”四个字的含义。

参考资料

全国大学生数学建模竞赛官网与优秀论文展示。
Boyd 与 Vandenberghe，《Convex Optimization》。
CVXPY 文档。

Gavin0576's Blog