优化

数学优化（mathematical optimization）是在允许的方案中，寻找使某个数量最小或最大的方案。需要选择的量称为决策变量，用来比较方案的式子称为目标函数，限制方案的条件称为约束。满足约束的所有方案组成可行域。

例如设计一项配比时，变量可以是两种原料的用量，目标可以是成本最低，约束可以是总量和成分要求。优化研究目标和约束确定之后怎样求解；改变成本、误差或资源的定义，往往会得到不同的最优方案。

从一个有边界的问题开始

考虑 $min_{x \geq 2} (x - 1)^{2} .$ 这里 $x$ 是变量， $(x - 1)^{2}$ 是目标， $x \geq 2$ 是约束。若没有约束，平方项在 $x = 1$ 时为零；但这个点不在可行域中。

任意可行点都能写为 $x = 2 + t$ ，其中 $t \geq 0$ 。代入目标： $(x - 1)^{2} = (1 + t)^{2} = 1 + 2 t + t^{2} \geq 1.$ 只有 $t = 0$ 时等号成立。因此最优点为 $x = 2$ ，最小值为一。这个推导同时说明该点可行、其他点都不会更好，而且答案唯一。

抛物线的无约束最低点是一零，可行区域从x等于二开始，可行最低点为二一 — 先看允许的横坐标范围，再在这段曲线上找最低点。边界处也可能取得最小值。

图中的抛物线最低点与可行部分的最低点不同。若只解导数为零，得到 $2 (x - 1) = 0$ ，会漏掉真正答案。导数为零是在可行域内部取得可微极值的必要条件，边界需要结合可行方向判断。

最小值是否存在，是否只有一个

有可行点不一定有最优点。例如 $min_{x > 0} x$ 中，取 $x = 1, 1 / 2, 1 / 3, \dots$ 可以不断降低目标，但零不允许取到。目标的下确界是零，最小值却不存在。

相反，若目标恒为零，可行域为 $[0, 1]$ ，每一点都是最优点，答案不唯一。存在性和唯一性是不同问题。在有限维欧氏空间中，连续目标在非空、闭且有界的可行域上一定能取得最大与最小值；这是常用的存在性保证，而不是唯一可能的保证。

局部最优指在足够小的邻域内，没有可行点更好；全局最优要求整个可行域内都没有更好点。解出驻点还不能区分它们。例如 $f (x) = x^{3}$ 在零处导数为零，但零两侧一边更大、一边更小，零不是极值点。

两个变量：先利用约束消去一个

求 $x^{2} + y^{2}$ 在 $x + y = 1$ 下的最小值。约束给出 $y = 1 - x$ ，代入并配方： $x^{2} + (1 - x)^{2} = 2 x^{2} - 2 x + 1 = 2 {(x - \frac{1}{2})}^{2} + \frac{1}{2} .$ 平方项非负，因此最小值为 $1 / 2$ ，恰在 $x = y = 1 / 2$ 时取得。

几何上， $x^{2} + y^{2}$ 是点到原点的距离平方，约束是一条直线。问题是在直线上寻找离原点最近的点，答案是原点向该直线作垂线的垂足。代数配方与几何投影描述的是同一个事实，参见线性代数。

还可以不消元，直接使用 $x^{2} + y^{2} = \frac{(x + y)^{2} + (x - y)^{2}}{2} = \frac{1}{2} + \frac{(x - y)^{2}}{2} \geq \frac{1}{2} .$ 这个恒等式给出对所有可行点成立的下界，候选点又达到下界，所以构成一个完整的最优性证明。

凸性为什么能帮助寻找全局最优

集合是凸集，指集合中任意两点之间的整条线段都仍在集合内。区间、圆盘、线性不等式围成的多边形都是例子。函数 $f$ 在凸集上是凸函数，指对任意两点 $x, y$ 和 $0 \leq t \leq 1$ ，有 $f ((1 - t) x + t y) \leq (1 - t) f (x) + t f (y) .$ 右端是两个端点函数值的线性插值。这个条件说，沿线段的函数图像不高于连接端点的弦。

平方函数是一个例子。把两边相减，可以得到 $(1 - t) x^{2} + t y^{2} - ((1 - t) x + t y)^{2} = t (1 - t) (x - y)^{2} \geq 0.$ 因此它满足凸性。当 $x \neq y$ 且 $0 < t < 1$ 时不等号严格成立，称为严格凸。

在凸可行域上最小化凸函数，局部最优必定也是全局最优。证明如下：假设 $x$ 是局部最优，却存在可行的 $y$ 使 $f (y) < f (x)$ 。沿线段向 $y$ 走很小一步，得到 $z = (1 - t) x + t y$ 。它仍可行，并可任意接近 $x$ ，但 $f (z) \leq (1 - t) f (x) + t f (y) < f (x) .$ 这与局部最优矛盾。因此不存在这样的 $y$ 。

若函数严格凸，两个不同最优点也不可能并存：它们中点的函数值会严格更低。普通凸函数则可以有一片平坦的最优点，例如 $f (x, y) = x^{2}$ 的所有 $(0, y)$ 都最优。凸性本身不保证最小值一定取得，仍需考虑上一节的存在性问题。

导数怎样给出最优性条件

一元可微函数在内点 $x$ 附近满足 $f (x + h) = f (x) + f^{'} (x) h + o (h) .$ 若 $f^{'} (x) > 0$ ，取足够小的负 $h$ 就会降低函数值；若 $f^{'} (x) < 0$ ，取正 $h$ 就会降低。因此内点局部极小必须有 $f^{'} (x) = 0$ 。多元情况下，所有坐标方向都必须满足这一条件，所以梯度 $\nabla f (x) = 0$ 。

对凸函数，一阶条件还能证明全局最优。由凸性，对 $0 < t \leq 1$ 有 $\frac{f (x + t (y - x)) - f (x)}{t} \leq f (y) - f (x) .$ 令 $t \to 0^{+}$ ，左边趋向 $\nabla f (x)^{𝖳} (y - x)$ ，得到 $f (y) \geq f (x) + \nabla f (x)^{𝖳} (y - x) .$ 若梯度为零，便有 $f (y) \geq f (x)$ 对所有 $y$ 成立，故 $x$ 全局最优。

有约束时，只需对所有可行 $y$ 满足 $\nabla f (x)^{𝖳} (y - x) \geq 0$ ，也能从同一不等式证明最优。开头的例子在 $x = 2$ 处导数为二，而所有可行 $y$ 都有 $y - 2 \geq 0$ ，正好符合这个条件。梯度不必为零，因为降低目标的方向已经被约束挡住了。

拉格朗日乘子从哪里来

回到 $x + y = 1$ 。沿可行直线移动时， $x$ 增加多少， $y$ 就要减少多少，所以切向方向为 $(1, - 1)$ 。在最优点，目标沿该方向的一阶变化应为零： $\nabla f (x, y) \cdot (1, - 1) = 0.$ 因此目标梯度与法向量 $(1, 1)$ 平行。这个法向量正是约束函数 $h (x, y) = x + y - 1$ 的梯度。

用一个系数表示这种平行关系，就得到 $\nabla f + λ \nabla h = 0$ 。引入拉格朗日函数 $L (x, y, λ) = x^{2} + y^{2} + λ (x + y - 1),$ 求解 $2 x + λ = 0, 2 y + λ = 0, x + y = 1.$ 前两式相减得 $x = y$ ，再用约束得 $x = y = 1 / 2$ 。此前的平方恒等式证明它确实是全局最小点。

一般等式约束也使用这一方法，但需要约束梯度线性无关等正则性条件。若约束为 $x^{2} = 0$ ，最小化目标 $f (x) = x$ 的唯一可行点是零；然而约束梯度在那里为零，方程 $1 + λ \cdot 0 = 0$ 无法成立。这个例子说明乘子方程不是脱离条件的求解规则。

不等式约束还要考虑哪些边界真正起作用。写成 $g_{i} (x) \leq 0$ 时，KKT 条件在驻点条件之外加入乘子非负、可行性和互补松弛 $λ_{i} g_{i} (x) = 0$ 。在标准可微凸问题中，满足这些条件可以证明全局最优；正则性条件则用于保证最优点能够找到这样的乘子。具体的不等式证书可先从线性规划学习。

梯度下降：怎样一步步走近最小点

无法直接求出最优点时，可以沿负梯度方向迭代： $x_{k + 1} = x_{k} - η \nabla f (x_{k}),$ 其中 $η > 0$ 是步长，决定每次走多远。负梯度给出局部下降方向，走得过远却可能越过低处。

对 $f (x) = (x - 1)^{2}$ ，迭代是 $x_{k + 1} = x_{k} - 2 η (x_{k} - 1)$ 。令误差 $e_{k} = x_{k} - 1$ ，就得到 $e_{k + 1} = (1 - 2 η) e_{k}, e_{k} = (1 - 2 η)^{k} e_{0} .$ 要让任意初值的误差趋于零，必须且只需 $| 1 - 2 η | < 1$ ，即 $0 < η < 1$ 。

从 $x_{0} = 5$ 出发，取 $η = 1 / 4$ ，误差每次减半，得到 $5, 3, 2, 1.5, 1.25, \dots$ 。取 $η = 3 / 4$ ，误差每次乘 $- 1 / 2$ ，得到 $5, - 1, 2, 0.5, 1.25, \dots$ ：位置左右交替，但误差绝对值仍在减半。

三个步长的迭代点在数轴上靠近一，交替靠近一，或在五和负三之间来回 — 每行从右侧的五出发，沿箭头读迭代顺序。绿色竖线标出最优位置一。

第一行从同侧接近最优点，第二行每次越过它但越走越近，第三行则保持同样距离来回跳动。

若 $η = 1$ ，误差每次变号而不缩小，迭代在五与负三之间来回。若步长大于一，除非恰好从最优点开始，否则误差会增大。这个计算解释了步长为什么属于算法本身，而不是无关紧要的设置；其他目标函数的合适步长须根据它们的曲率重新判断。

有约束时，普通梯度下降可能走出可行域。例如开头的可行域是 $[2, \infty)$ ，可以在每步之后把小于二的结果改为二，得到投影梯度步骤 $x_{k + 1} = max {2, x_{k} - 2 η (x_{k} - 1)} .$ 这一步先尝试降低目标，再返回可行范围。更复杂的可行域需要求相应的投影，算法选择取决于这种操作是否容易计算。

从数学答案回到模型

算法结果通常同时报告变量、目标值和约束残差。例如线性约束 $x + y = 1$ 的残差是 $x + y - 1$ ，可以直接反映数值解偏离可行域多少。若有理论下界，还可比较候选目标与下界之间的差距。

数学模型的目标也须与用途相符：体积可以是连续变量，车辆数量通常需为整数；最小平方误差与最小最大误差会给出不同拟合结果。这些选择先于求解。有关资源分配的线性目标见线性规划，有关数据拟合的目标见最小二乘法，从实际问题建立变量和假设见数学建模。

历史

极值问题长期是几何与微积分的研究对象。二十世纪的线性规划把大规模资源配置放到系统的优化框架中：Kantorovich 在 1939 年发表相关工作，Dantzig 在 1947 年提出单纯形法。相关背景见 Kantorovich 传记与斯坦福大学对 Dantzig 的介绍。现代优化继续发展出凸优化、整数优化和随机优化等方向，用于处理不同的目标结构与不确定性。

参考来源与延伸阅读

Boyd 与 Vandenberghe：Convex Optimization，作者提供的教材与讲义，见凸性、最优性条件与对偶章节。
MacTutor：Kantorovich；Stanford：Dantzig 与单纯形法。
导数 · 线性代数 · 数学建模