优化方法

01

把优化作为统一的框架

每个优化问题都有同样的三个部分：一个目标（要最小化或最大化的东西——成本、误差、 时间）、变量（你能控制的决策），以及约束（解必须满足的规则——预算、 容量、物理极限）。用这些术语把一个问题表述出来，你就把它变成了一个优化问题，可以交给一整套方法 的工具箱。

辨认出这个框架本身就有价值：「在每个需求都被满足、且没有卡车超载的前提下，最小化总成本」与「在 权重不太大的前提下，最小化预测误差」是同一类问题。方法因地形而异，这正是我们接下来要去 的地方。

02

凸与非凸：巨大的分水岭

一个优化问题最重要的单一性质，是它是否凸。一个凸问题的地形形如一个单一、光滑的 碗：只有一个最低点，而任何局部极小值就是全局极小值。那个保证是一切—— 它意味着一个简单的下坡方法（比如梯度下降） 一定能找到真正最好的答案。凸问题，在某种真实的意义上，是「已解决的」。

一个非凸问题的地形布满了山丘和山谷——许多局部极小值。一个下坡方法会被困在 它起步处附近的那个山谷里，无法保证它是最深的。大多数真正困难的优化（包括训练深度网络）都是非凸的，这正是为什么人们投入那么多 努力，去要么把问题变凸、要么接受「足够好」的答案。凸性是「可解」与「困难」之间的那条界线。

03

线性规划与单纯形法

经典的、漂亮可解的情形是线性规划（LP）：一个线性目标，服从于线性约束。约束雕出一个可行域——一个多维的多面体——而一个关键的定理说，最优解总是位于它的某个角点（顶点）上。那就把一个无限的搜索变成了检查角点。

著名的单纯形法（Dantzig，1947）利用了这一点：从可行域的一个角点出发，沿着边走到 能改善目标的相邻角点，直到没有邻居更好为止——那个角点就是最优的。它是经典运筹学背后的主力——资源分配、配餐问题、运输、 配料——而 LP 是凸的，所以它找到的答案是真正最好的。

04

整数规划：难度的跃升

加上一个看似无害的要求——某些决策必须是整数——难度就会爆炸。整数规划涵盖了许多你不能有 2.7 辆卡车、或把半个人安排到一个班次的问题。麻烦在于，「整数」让可行域 变成一堆离散的散点、而非一个光滑的区域，这是非凸的，而且一般而言是NP 难的——没有已知的、总能快速解出它的高效算法。

实用的主力是分支定界——巧妙地把问题划分成子问题，解出每个的容易（松弛、连续）版本， 并剪掉那些不可能胜过目前最好解的分支。尽管最坏情况很难，它在实践中却出奇地好用。这个教训值得 内化：要求整数答案是难度上的一次真正的跃升，而非一个细节——许多真实的排程与分配 问题之所以难，正是这个原因。

05

处理约束

约束是让优化变得现实——也变得棘手——的东西。对于光滑的约束问题，经典的工具是拉格朗日 乘子（推广为 KKT 条件）：一种把约束折叠进目标的方法，把「在……约束下最小化」变成一个单一的 方程组去解，并揭示每个约束在最优处「推」得有多用力（它的影子价格——如果你把那个约束放松 一点点，目标会改善多少）。那种敏感性信息往往与解本身一样有价值，因为它告诉你该先松开哪个约束。

06

元启发式：当地形很丑陋时

对于精确方法无望的非凸、离散或黑箱问题，你就转向元启发式——通用的搜索策略，寻找 一个足够好的解，而不保证最好。大多数都受自然启发：

• 遗传算法——演化一群候选解：保留最适应的，通过组合各部分来「繁殖」它们，并随机 「变异」。把自然选择当作一种搜索方法。
• 模拟退火——借自冶金：一开始广泛地探索（接受一些更差的移动，以逃离局部极小值）， 然后逐渐「冷却」，安顿到一个好的山谷里。

07

它在我工作中的体现

08

60 秒回顾

凸/非凸的分水岭、LP/单纯形与整数规划/分支定界，以及元启发式 + 没有免费午餐的框架，反映了当前的 优化参考文献以及运筹学课程。