优化：修订间差异

2026年9月20日 (日) 07:16的最新版本

数学优化（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 与单纯形法。
导数 · 线性代数 · 数学建模

@@ 第1行： / 第1行： @@
-数学优化是在给定可行范围内寻找目标函数最小值或最大值的问题。最小化 <math>f</math> 与最大化 <math>-f</math> 可以互相转换。一个优化模型必须说明决策变量、目标与约束；“最好”只有在这些选择明确后才有数学含义。
+'''数学优化'''（mathematical optimization）是在允许的方案中，寻找使某个数量最小或最大的方案。需要选择的量称为'''决策变量'''，用来比较方案的式子称为'''目标函数'''，限制方案的条件称为'''约束'''。满足约束的所有方案组成'''可行域'''。
-英文名称：Mathematical optimization。
+例如设计一项配比时，变量可以是两种原料的用量，目标可以是成本最低，约束可以是总量和成分要求。优化研究目标和约束确定之后怎样求解；改变成本、误差或资源的定义，往往会得到不同的最优方案。
-== English overview ==
+== 从一个有边界的问题开始 ==
-<div lang="en" class="math-english-summary">
-Mathematical optimization asks for the best feasible decision under a stated objective. A model has variables, an objective function, and constraints; changing any of these can change what “best” means. Feasibility, attainment, uniqueness, and computability are separate questions. A problem can have feasible points but no minimizer, or it can have many equally good solutions.
-This article develops the distinction between local and global optima through one-dimensional examples and equality-constrained problems. Convexity provides a powerful bridge: every local minimum of a convex function on a convex feasible set is global, although existence and uniqueness need additional conditions. We prove this property and derive a first-order lower bound that serves as an optimality certificate. Lagrange multipliers describe how gradients balance under regular constraints, while numerical methods such as gradient descent require controlled step sizes. Examples show why boundary points, saddle points, scaling, and constraint violations matter. Historical notes distinguish calculus-based extremum methods from twentieth-century linear programming. In applications, solving an optimization problem accurately does not validate the assumptions or values encoded in the model; sensitivity analysis and independent checks remain necessary.
-</div>
-== 目标函数与可行域 ==
-一般约束优化可写为
-<math display="block">\min_{x\in\mathbb R^n}f(x)\quad\text{使得}\quad g_i(x)\le0,\ h_j(x)=0.</math>
-满足所有约束的点构成可行域。不可行的问题没有可行解；有可行解也未必能取得最小值。例如 <math>\min_{x>0}x</math> 的下确界为 0，却没有可行点达到 0。连续函数在非空紧集上一定能取得最大、最小值，这是常用的存在性保证。
-== 一个带边界的一维例子 ==
 考虑
 <math display="block">\min_{x\ge2}(x-1)^2.</math>
-没有约束时，导数 <math>2(x-1)=0</math> 给出 <math>x=1</math>，但该点不可行。对所有 <math>x\ge2</math>，函数递增，所以最优点为 <math>x=2</math>，最小值为 1。
+这里 <math>x</math> 是变量，<math>(x-1)^2</math> 是目标，<math>x\ge2</math> 是约束。若没有约束，平方项在 <math>x=1</math> 时为零；但这个点不在可行域中。
-[[File:Gezhi-optimization-boundary.svg|frame|center|alt=函数x减一的平方在x大于等于二的可行区域内，最小值位于边界二一，而无约束最低点一零不可行|约束改变最优解；只解“导数等于零”会漏掉边界最优点。]]
+任意可行点都能写为 <math>x=2+t</math>，其中 <math>t\ge0</math>。代入目标：
-若在可行域内部取得局部极小值，且函数可微，那么梯度为零是必要条件。但驻点不一定是极小值，例如 <math>f(x)=x^3</math> 在 0 的导数为零却没有极值。
+<math display="block">(x-1)^2=(1+t)^2=1+2t+t^2\ge1.</math>
+只有 <math>t=0</math> 时等号成立。因此最优点为 <math>x=2</math>，最小值为一。这个推导同时说明该点可行、其他点都不会更好，而且答案唯一。
-== 局部最优、全局最优与凸性 ==
+[[File:Gezhi-optimization-boundary-theme.svg|frame|center|alt=抛物线的无约束最低点是一零，可行区域从x等于二开始，可行最低点为二一|先看允许的横坐标范围，再在这段曲线上找最低点。边界处也可能取得最小值。]]
-局部最优只要求在附近没有更好点；全局最优要求整个可行域都没有更好点。集合 <math>C</math> 凸是指任意两点间的线段都在集合内。函数在凸域上凸，是指对 <math>0\le t\le1</math>，
-<math display="block">f(tx+(1-t)y)\le t f(x)+(1-t)f(y).</math>
-凸优化问题的局部极小点也是全局极小点。这并不自动保证最优点存在或唯一；严格凸函数若在凸域上取得最小值，才保证最优点唯一。线性规划要求线性目标与线性等式、不等式约束，是重要的凸优化类别。
-== 拉格朗日乘子怎样使用 ==
+图中的抛物线最低点与可行部分的最低点不同。若只解导数为零，得到 <math>2(x-1)=0</math>，会漏掉真正答案。导数为零是在可行域内部取得可微极值的必要条件，边界需要结合可行方向判断。
-求 <math>x^2+y^2</math> 在 <math>x+y=1</math> 下的最小值。定义
-<math display="block">L(x,y,\lambda)=x^2+y^2+\lambda(x+y-1).</math>
-令对 <math>x,y</math> 的偏导为零，并满足约束，得到 <math>2x+\lambda=0</math>、<math>2y+\lambda=0</math>、<math>x+y=1</math>，所以 <math>x=y=1/2</math>，目标值为 <math>1/2</math>。
-这次结论还可直接验证：由 <math>x^2+y^2=((x+y)^2+(x-y)^2)/2\ge1/2</math>，等号恰在 <math>x=y</math> 时成立。一般问题使用乘子法需要约束正则性等条件，求出驻点后仍需判断它是极小、极大还是其他情形。
+== 最小值是否存在，是否只有一个 ==
+有可行点不一定有最优点。例如 <math>\min_{x>0}x</math> 中，取 <math>x=1,1/2,1/3,\ldots</math> 可以不断降低目标，但零不允许取到。目标的下确界是零，最小值却不存在。
-== 梯度下降与步长 ==
+相反，若目标恒为零，可行域为 <math>[0,1]</math>，每一点都是最优点，答案不唯一。存在性和唯一性是不同问题。在有限维欧氏空间中，连续目标在非空、闭且有界的可行域上一定能取得最大与最小值；这是常用的存在性保证，而不是唯一可能的保证。
-无约束可微问题常用迭代 <math>x_{k+1}=x_k-\eta\nabla f(x_k)</math>，其中 <math>\eta>0</math> 是步长。对 <math>f(x)=(x-1)^2</math>，误差满足
-<math display="block">x_{k+1}-1=(1-2\eta)(x_k-1).</math>
-只有 <math>0<\eta<1</math> 时，这个固定步长迭代对任意初值都收敛到 1；步长过大会振荡或发散。这个区间是本例结论，不能照搬到所有目标函数。
-== 解得精确不等于模型正确 ==
+'''局部最优'''指在足够小的邻域内，没有可行点更好；'''全局最优'''要求整个可行域内都没有更好点。解出驻点还不能区分它们。例如 <math>f(x)=x^3</math> 在零处导数为零，但零两侧一边更大、一边更小，零不是极值点。
-[[数学建模]]中的目标可能是误差、成本或耗时，不同目标会产生不同解。多目标问题需要说明权衡，数值软件报告“成功”后还应检查约束残差、最优性条件和参数敏感性。整数决策、非凸结构和噪声目标可能需要不同算法。
-== 从一个现实要求写出数学问题 ==
+== 两个变量：先利用约束消去一个 ==
-设要安排两种产品产量，机器有工作时间上限，原料有库存上限。如果目标是利润最大，应把售价与成本换成同一计量单位；如果目标改为准时交货，最佳方案可能完全不同。变量还要说明是连续量还是整数：液体体积可以近似连续，车辆数量通常不能是 2.7 辆。约束描述可接受的方案，目标用于在这些方案之间排序，不能把二者混成一句“尽量满足需求”。
+求 <math>x^2+y^2</math> 在 <math>x+y=1</math> 下的最小值。约束给出 <math>y=1-x</math>，代入并配方：
+<math display="block">x^2+(1-x)^2=2x^2-2x+1=2\left(x-\frac12\right)^2+\frac12.</math>
+平方项非负，因此最小值为 <math>1/2</math>，恰在 <math>x=y=1/2</math> 时取得。
-一个明确的模型还应交代参数是否已知。把需求预测当作确定常数会得到确定性模型；考虑多个情景、概率或最坏情况，会得到不同的随机或鲁棒优化问题。这些处理没有脱离问题背景的统一优劣。建模者首先需要说明承担什么不确定性，以及解的含义是某个情景的最优、平均表现较好，还是对一组情景都可行。
+几何上，<math>x^2+y^2</math> 是点到原点的距离平方，约束是一条直线。问题是在直线上寻找离原点最近的点，答案是原点向该直线作垂线的垂足。代数配方与几何投影描述的是同一个事实，参见[[线性代数]]。
-== 存在、唯一与算法成功是三个问题 ==
+还可以不消元，直接使用
-函数 <math>f(x)=e^x</math> 在整个实数轴上大于零，下确界为零，但没有任何有限 x 使函数等于零，因此没有极小化解。函数 <math>f(x)=0</math> 在区间 [0,1] 上处处达到最小值，所以最优解不唯一。函数连续且可行域非空、闭且有界时，在有限维欧氏空间中紧性保证能取到极值；无界可行域也可能有解，只是不能直接使用这一个保证。
+<math display="block">x^2+y^2=\frac{(x+y)^2+(x-y)^2}{2}=\frac12+\frac{(x-y)^2}{2}\ge\frac12.</math>
+这个恒等式给出对所有可行点成立的下界，候选点又达到下界，所以构成一个完整的最优性证明。
-存在一个理论最优点，不代表任意算法都能找到它。算法停止可能是达到迭代上限、步长很小或数值变化很小，这些都不自动证明全局最优。相反，若能给出对所有可行点成立的下界，并找到一个点达到它，便得到一个可以独立检查的最优性证书。前面的平方和例子正是如此：恒等式给出下界二分之一，点 (1/2,1/2) 达到下界。
+== 凸性为什么能帮助寻找全局最优 ==
+集合是'''凸集'''，指集合中任意两点之间的整条线段都仍在集合内。区间、圆盘、线性不等式围成的多边形都是例子。函数 <math>f</math> 在凸集上是'''凸函数'''，指对任意两点 <math>x,y</math> 和 <math>0\le t\le1</math>，有
+<math display="block">f((1-t)x+ty)\le(1-t)f(x)+tf(y).</math>
+右端是两个端点函数值的线性插值。这个条件说，沿线段的函数图像不高于连接端点的弦。
-== 凸性为何能排除较差的局部极小点 ==
+平方函数是一个例子。把两边相减，可以得到
-设 f 在凸集 C 上凸，x 是局部极小点，却假设存在 y∈C 使 <math>f(y)<f(x)</math>。对任意很小的正数 t，线段上的 <math>z=(1-t)x+ty</math> 仍在 C 中，并可任意靠近 x。凸性给出
+<math display="block">(1-t)x^2+ty^2-((1-t)x+ty)^2=t(1-t)(x-y)^2\ge0.</math>
+因此它满足凸性。当 <math>x\ne y</math> 且 <math>0<t<1</math> 时不等号严格成立，称为'''严格凸'''。
+在凸可行域上最小化凸函数，局部最优必定也是全局最优。证明如下：假设 <math>x</math> 是局部最优，却存在可行的 <math>y</math> 使 <math>f(y)<f(x)</math>。沿线段向 <math>y</math> 走很小一步，得到 <math>z=(1-t)x+ty</math>。它仍可行，并可任意接近 <math>x</math>，但
 <math display="block">f(z)\le(1-t)f(x)+tf(y)<f(x).</math>
-这与 x 附近没有更小函数值矛盾，所以 x 必为全局极小点。证明只用了两件事：两点之间可以沿可行线段移动，以及函数在该线段上不高于端点值的线性插值。缺少其中任何一个条件，结论就不能照搬。
+这与局部最优矛盾。因此不存在这样的 <math>y</math>。
-若 f 严格凸，假设两个不同最优点 x、y 具有同一最小值，那么它们中点的值严格小于这个最小值，产生矛盾。因此只要最优点存在，就至多一个。普通凸性则允许平坦方向。例如 <math>f(x,y)=x^2</math> 凸，但所有 (0,y) 都是全局最优点。函数看起来“碗状”的比喻在多维中应谨慎使用，平底或平坦方向并不破坏凸性。
+若函数严格凸，两个不同最优点也不可能并存：它们中点的函数值会严格更低。普通凸函数则可以有一片平坦的最优点，例如 <math>f(x,y)=x^2</math> 的所有 <math>(0,y)</math> 都最优。凸性本身不保证最小值一定取得，仍需考虑上一节的存在性问题。
-== 一阶条件给出的全局证书 ==
+== 导数怎样给出最优性条件 ==
-可微凸函数满足一阶下界
+一元可微函数在内点 <math>x</math> 附近满足
+<math display="block">f(x+h)=f(x)+f'(x)h+o(h).</math>
+若 <math>f'(x)>0</math>，取足够小的负 <math>h</math> 就会降低函数值；若 <math>f'(x)<0</math>，取正 <math>h</math> 就会降低。因此内点局部极小必须有 <math>f'(x)=0</math>。多元情况下，所有坐标方向都必须满足这一条件，所以梯度 <math>\nabla f(x)=0</math>。
+对凸函数，一阶条件还能证明全局最优。由凸性，对 <math>0<t\le1</math> 有
+<math display="block">\frac{f(x+t(y-x))-f(x)}{t}\le f(y)-f(x).</math>
+令 <math>t\to0^+</math>，左边趋向 <math>\nabla f(x)^{\mathsf T}(y-x)</math>，得到
 <math display="block">f(y)\ge f(x)+\nabla f(x)^{\mathsf T}(y-x).</math>
-可从凸性沿线段定义 <math>\phi(t)=f(x+t(y-x))</math>，把凸性不等式移项、除以 t>0，再令 t 趋于零得到。几何上，切超平面位于函数图像下方。因此无约束时若梯度为零，就有 <math>f(y)\ge f(x)</math> 对所有 y 成立，驻点确实是全局最优点；“凸且可微”是这里不可省略的条件。
+若梯度为零，便有 <math>f(y)\ge f(x)</math> 对所有 <math>y</math> 成立，故 <math>x</math> 全局最优。
-在凸可行域 C 上，更一般的证书是 <math>\nabla f(x)^{\mathsf T}(y-x)\ge0</math> 对所有可行 y 成立。边界最优点的梯度可以非零，因为负梯度方向可能指向不可行区域。对本条开头的 <math>x\ge2</math> 例子，在 x=2 处梯度为二，所有可行方向满足 y−2≥0，故这个证书成立。这样就把边界检查与一阶条件统一了起来。
-二阶信息可以帮助判断局部行为：无约束二次函数若 Hessian 矩阵正定，则严格凸；在一般二次连续可微函数的驻点处，正定 Hessian 是严格局部极小的充分条件，半正定却不总是充分。例如 <math>x^4</math> 与 <math>-x^4</math> 在零处二阶导数同为零，局部行为相反，必须看更多信息。
-== 乘子方法不能省略的条件 ==
+有约束时，只需对所有可行 <math>y</math> 满足 <math>\nabla f(x)^{\mathsf T}(y-x)\ge0</math>，也能从同一不等式证明最优。开头的例子在 <math>x=2</math> 处导数为二，而所有可行 <math>y</math> 都有 <math>y-2\ge0</math>，正好符合这个条件。梯度不必为零，因为降低目标的方向已经被约束挡住了。
-在等式约束 <math>h(x)=0</math> 下，局部最优点处目标梯度通常要与约束梯度方向配合，因为沿可行曲面的切向移动不能一阶降低目标。多重约束时，约束梯度线性无关等正则性条件保证可以寻找乘子，使目标梯度由约束梯度线性组合表示。乘子方程给出候选点，再做可行性和最优性检查。
-条件失败可能使普通乘子方程漏解。例如最小化 f(x)=x，约束 <math>h(x)=x^2=0</math>，唯一可行点 x=0 自然最优，但 <math>f'(0)+\lambda h'(0)=1+\lambda\cdot0</math> 永不为零。原因是约束在该点梯度为零，通常的正则性前提不成立。这一小例子说明：一个解方程步骤失败，并不意味着原优化问题没有解。
+== 拉格朗日乘子从哪里来 ==
+回到 <math>x+y=1</math>。沿可行直线移动时，<math>x</math> 增加多少，<math>y</math> 就要减少多少，所以切向方向为 <math>(1,-1)</math>。在最优点，目标沿该方向的一阶变化应为零：
+<math display="block">\nabla f(x,y)\cdot(1,-1)=0.</math>
+因此目标梯度与法向量 <math>(1,1)</math> 平行。这个法向量正是约束函数 <math>h(x,y)=x+y-1</math> 的梯度。
-不等式约束的 KKT 条件还包括乘子非负、原问题可行与互补松弛。在适当正则性下它们是局部最优的必要条件；在目标函数与不等式约束函数凸、等式约束仿射且相关函数可微的标准凸问题中，满足 KKT 条件的点可提供全局最优证书。入门时可以先在[[线性规划]]里通过具体的对偶不等式理解证书，再逐步学习一般理论，避免把四组公式当作所有问题都适用的万能求解器。
+用一个系数表示这种平行关系，就得到 <math>\nabla f+\lambda\nabla h=0</math>。引入拉格朗日函数
+<math display="block">L(x,y,\lambda)=x^2+y^2+\lambda(x+y-1),</math>
+求解
+<math display="block">2x+\lambda=0,\qquad2y+\lambda=0,\qquad x+y=1.</math>
+前两式相减得 <math>x=y</math>，再用约束得 <math>x=y=1/2</math>。此前的平方恒等式证明它确实是全局最小点。
-== 完整算例：梯度下降为何会振荡 ==
+一般等式约束也使用这一方法，但需要约束梯度线性无关等正则性条件。若约束为 <math>x^2=0</math>，最小化目标 <math>f(x)=x</math> 的唯一可行点是零；然而约束梯度在那里为零，方程 <math>1+\lambda\cdot0=0</math> 无法成立。这个例子说明乘子方程不是脱离条件的求解规则。
-仍取 <math>f(x)=(x-1)^2</math>，初值 x₀=5。步长 η=1/4 时，误差每次减半，迭代值为 5、3、2、1.5、1.25，逐渐靠近一。步长 η=3/4 时，误差每次乘以 −1/2，得到 5、−1、2、0.5、1.25，虽然左右交替，误差绝对值仍减半。振荡本身不等于发散。
-若 η=1，误差每次乘以 −1，迭代在 5 与 −3 之间来回，目标值一直是十六，不收敛到最优点；若 η>1，误差绝对值通常增大。只有初值恰为一时，任何步长都停在最优点，因此先前给出的区间描述的是“对任意初值都收敛”的条件。此处明确量词，可以避免用一个特殊初值错误地反驳或证明算法结论。
+不等式约束还要考虑哪些边界真正起作用。写成 <math>g_i(x)\le0</math> 时，KKT 条件在驻点条件之外加入乘子非负、可行性和互补松弛 <math>\lambda_i g_i(x)=0</math>。在标准可微凸问题中，满足这些条件可以证明全局最优；正则性条件则用于保证最优点能够找到这样的乘子。具体的不等式证书可先从[[线性规划]]学习。
-多维二次问题中，不同方向可能具有很不一样的曲率，步长必须兼顾最陡方向，较平坦方向便收敛很慢。这与[[矩阵]]的条件数有关。变量单位相差很多也可能造成数值尺度失衡；重新缩放可以改善计算，但不能随意改变目标中的相对权重，否则是在求另一个问题。实现后应输出目标值、约束残差和停止原因，而不只给一个“成功”标签。
+== 梯度下降：怎样一步步走近最小点 ==
+无法直接求出最优点时，可以沿负梯度方向迭代：
+<math display="block">x_{k+1}=x_k-\eta\nabla f(x_k),</math>
+其中 <math>\eta>0</math> 是步长，决定每次走多远。负梯度给出局部下降方向，走得过远却可能越过低处。
-== 一个边界问题的完整 KKT 证书 ==
+对 <math>f(x)=(x-1)^2</math>，迭代是 <math>x_{k+1}=x_k-2\eta(x_k-1)</math>。令误差 <math>e_k=x_k-1</math>，就得到
-把开头的约束写为 <math>g(x)=2-x\le0</math>，拉格朗日函数为 <math>L(x,\lambda)=(x-1)^2+\lambda(2-x)</math>。候选点 <math>x_*=2</math> 配上乘子 <math>\lambda_*=2</math>，分别满足可行性、乘子非负、互补松弛 <math>\lambda_*g(x_*)=0</math>，以及驻点关系 <math>2(x_*-1)-\lambda_*=0</math>。四项条件在一个具体问题中各有可检查的数值含义。
+<math display="block">e_{k+1}=(1-2\eta)e_k,\qquad e_k=(1-2\eta)^k e_0.</math>
+要让任意初值的误差趋于零，必须且只需 <math>|1-2\eta|<1</math>，即 <math>0<\eta<1</math>。
-更直接的证书来自固定这个乘子后的恒等式：
+从 <math>x_0=5</math> 出发，取 <math>\eta=1/4</math>，误差每次减半，得到 <math>5,3,2,1.5,1.25,\ldots</math>。取 <math>\eta=3/4</math>，误差每次乘 <math>-1/2</math>，得到 <math>5,-1,2,0.5,1.25,\ldots</math>：位置左右交替，但误差绝对值仍在减半。
-<math display="block">L(x,2)=(x-2)^2+1\ge1.</math>
-对任何可行点 <math>x\ge2</math>，约束项 <math>2(2-x)\le0</math>，所以 <math>f(x)\ge L(x,2)\ge1</math>；候选点恰好达到一。这个证明同时给出全域下界与达到下界的可行解，不依赖某个求解器的成功标志。
-乘子非负不能省略。它使“加上约束项”在可行点处只会降低目标，从而产生有效下界；若把符号任意反转，这条不等式链就可能失效。互补松弛说明在最优候选点处，这个下界没有因为约束项而留下额外空隙。对不活跃约束，乘子可以为零；活跃约束也不一定要求乘子严格为正。
+[[File:Gezhi-teaching-gradient-steps.svg|frame|center|alt=三个步长的迭代点在数轴上靠近一，交替靠近一，或在五和负三之间来回|每行从右侧的五出发，沿箭头读迭代顺序。绿色竖线标出最优位置一。]]
-在标准可微凸模型中，KKT 条件的充分性不要求另外先假定 Slater 条件；Slater 一类正则性常用于保证最优解存在相应乘子以及强对偶。把“一个 KKT 点足够证明最优”与“每个最优点必有 KKT 乘子”分开，才能避免把必要性和充分性混为一谈。[https://web.stanford.edu/~boyd/cvxbook/bv_cvxslides.pdf Boyd 与 Vandenberghe，第 5 章讲义]
+第一行从同侧接近最优点，第二行每次越过它但越走越近，第三行则保持同样距离来回跳动。
-数值证书也需要区分精确与近似：若约束残差只是很小，而没有被严格控制，得到的只是近似可行性；若上下界仍留有差距，则应报告这个最优性差距。容差应与变量尺度相匹配，不能把任意一组默认小数阈值当作所有问题都适用的证明。
+若 <math>\eta=1</math>，误差每次变号而不缩小，迭代在五与负三之间来回。若步长大于一，除非恰好从最优点开始，否则误差会增大。这个计算解释了步长为什么属于算法本身，而不是无关紧要的设置；其他目标函数的合适步长须根据它们的曲率重新判断。
-局部最优也应相对可行域解释：存在一个邻域，使其中的可行点都不比候选点更好；邻域里的不可行点不参与比较。可行域若离散，一个孤立可行点天然局部最优，却可能远逊于另一个可行点。因此凸性定理中的可行线段条件确实不可少，不能把连续凸问题的结论搬到任意整数决策问题中。
+有约束时，普通梯度下降可能走出可行域。例如开头的可行域是 <math>[2,\infty)</math>，可以在每步之后把小于二的结果改为二，得到投影梯度步骤
+<math display="block">x_{k+1}=\max\{2,\ x_k-2\eta(x_k-1)\}.</math>
+这一步先尝试降低目标，再返回可行范围。更复杂的可行域需要求相应的投影，算法选择取决于这种操作是否容易计算。
-== 历史与方法谱系 ==
+== 从数学答案回到模型 ==
-极值研究与几何、微积分长期相连，现代优化不能归结为一个人的一次发现。二十世纪线性规划的发展与资源分配问题密切相关。Kantorovich 在 1939 年发表相关工作，Dantzig 在 1947 年提出单纯形法；[https://mathshistory.st-andrews.ac.uk/Biographies/Kantorovich/ MacTutor 传记]与[https://news.stanford.edu/stories/2005/05/george-b-dantzig-operations-research-professor-dies-90 斯坦福大学的 Dantzig 纪念文章]分别介绍了这些背景。模型的提出、对偶理论的形成与算法的实现是不同贡献，不宜压缩成简单的“谁发明优化”。
+算法结果通常同时报告变量、目标值和约束残差。例如线性约束 <math>x+y=1</math> 的残差是 <math>x+y-1</math>，可以直接反映数值解偏离可行域多少。若有理论下界，还可比较候选目标与下界之间的差距。
-今天优化还包括离散、非凸、多目标、随机等方向。凸优化提供了一组结构清楚、理论与算法联系紧密的问题，但不覆盖所有实际决策。尤其当目标涉及多个不可直接通约的标准时，数学能揭示权衡和可行边界，不能自行替决策者选择价值排序。
+数学模型的目标也须与用途相符：体积可以是连续变量，车辆数量通常需为整数；最小平方误差与最小最大误差会给出不同拟合结果。这些选择先于求解。有关资源分配的线性目标见[[线性规划]]，有关数据拟合的目标见[[最小二乘法]]，从实际问题建立变量和假设见[[数学建模]]。
-== 编者评注（AI 辅助） ==
+== 历史 ==
-<div class="math-editorial-note">本条建议用“候选解—可行性—证书”三步阅读每个算例。先得到一个数值只是开始，检查它是否满足约束，再说明为什么没有更好方案，才完成了数学任务。把模型假设与求解误差分别记录也很重要：一个被精确求解但目标选错的模型，可能不如一个较粗糙却正确回答实际问题的模型。学习时宜先把小问题手算清楚，再借助软件处理大规模情形。</div>
+极值问题长期是几何与微积分的研究对象。二十世纪的线性规划把大规模资源配置放到系统的优化框架中：Kantorovich 在 1939 年发表相关工作，Dantzig 在 1947 年提出单纯形法。相关背景见 [https://mathshistory.st-andrews.ac.uk/Biographies/Kantorovich/ Kantorovich 传记]与[https://news.stanford.edu/stories/2005/05/george-b-dantzig-operations-research-professor-dies-90 斯坦福大学对 Dantzig 的介绍]。现代优化继续发展出凸优化、整数优化和随机优化等方向，用于处理不同的目标结构与不确定性。
 == 参考来源与延伸阅读 ==