优化：修订间差异

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）是在允许的方案中，寻找使某个数量最小或最大的方案。需要选择的量称为'''决策变量'''，用来比较方案的式子称为'''目标函数'''，限制方案的条件称为'''约束'''。满足约束的所有方案组成'''可行域'''。
-== 目标函数与可行域 ==
+例如设计一项配比时，变量可以是两种原料的用量，目标可以是成本最低，约束可以是总量和成分要求。优化研究目标和约束确定之后怎样求解；改变成本、误差或资源的定义，往往会得到不同的最优方案。
-一般约束优化可写为
-<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> 在零处导数为零，但零两侧一边更大、一边更小，零不是极值点。
-[[数学建模]]中的目标可能是误差、成本或耗时，不同目标会产生不同解。多目标问题需要说明权衡，数值软件报告“成功”后还应检查约束残差、最优性条件和参数敏感性。整数决策、非凸结构和噪声目标可能需要不同算法。
-== 延伸阅读 ==
+== 两个变量：先利用约束消去一个 ==
-* [https://stanford.edu/~boyd/cvxbook/ Stephen Boyd、Lieven Vandenberghe，《Convex Optimization》]：凸集、凸函数、最优性条件与算法。
+求 <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 display="block">x^2+y^2=\frac{(x+y)^2+(x-y)^2}{2}=\frac12+\frac{(x-y)^2}{2}\ge\frac12.</math>
+这个恒等式给出对所有可行点成立的下界，候选点又达到下界，所以构成一个完整的最优性证明。
+== 凸性为什么能帮助寻找全局最优 ==
+集合是'''凸集'''，指集合中任意两点之间的整条线段都仍在集合内。区间、圆盘、线性不等式围成的多边形都是例子。函数 <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>
+右端是两个端点函数值的线性插值。这个条件说，沿线段的函数图像不高于连接端点的弦。
+平方函数是一个例子。把两边相减，可以得到
+<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>
+这与局部最优矛盾。因此不存在这样的 <math>y</math>。
+若函数严格凸，两个不同最优点也不可能并存：它们中点的函数值会严格更低。普通凸函数则可以有一片平坦的最优点，例如 <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>f(y)\ge f(x)</math> 对所有 <math>y</math> 成立，故 <math>x</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>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> 的梯度。
+用一个系数表示这种平行关系，就得到 <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>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> 是步长，决定每次走多远。负梯度给出局部下降方向，走得过远却可能越过低处。
+对 <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 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>：位置左右交替，但误差绝对值仍在减半。
+[[File:Gezhi-teaching-gradient-steps.svg|frame|center|alt=三个步长的迭代点在数轴上靠近一，交替靠近一，或在五和负三之间来回|每行从右侧的五出发，沿箭头读迭代顺序。绿色竖线标出最优位置一。]]
+第一行从同侧接近最优点，第二行每次越过它但越走越近，第三行则保持同样距离来回跳动。
+若 <math>\eta=1</math>，误差每次变号而不缩小，迭代在五与负三之间来回。若步长大于一，除非恰好从最优点开始，否则误差会增大。这个计算解释了步长为什么属于算法本身，而不是无关紧要的设置；其他目标函数的合适步长须根据它们的曲率重新判断。
+有约束时，普通梯度下降可能走出可行域。例如开头的可行域是 <math>[2,\infty)</math>，可以在每步之后把小于二的结果改为二，得到投影梯度步骤
+<math display="block">x_{k+1}=\max\{2,\ x_k-2\eta(x_k-1)\}.</math>
+这一步先尝试降低目标，再返回可行范围。更复杂的可行域需要求相应的投影，算法选择取决于这种操作是否容易计算。
+== 从数学答案回到模型 ==
+算法结果通常同时报告变量、目标值和约束残差。例如线性约束 <math>x+y=1</math> 的残差是 <math>x+y-1</math>，可以直接反映数值解偏离可行域多少。若有理论下界，还可比较候选目标与下界之间的差距。
+数学模型的目标也须与用途相符：体积可以是连续变量，车辆数量通常需为整数；最小平方误差与最小最大误差会给出不同拟合结果。这些选择先于求解。有关资源分配的线性目标见[[线性规划]]，有关数据拟合的目标见[[最小二乘法]]，从实际问题建立变量和假设见[[数学建模]]。
+== 历史 ==
+极值问题长期是几何与微积分的研究对象。二十世纪的线性规划把大规模资源配置放到系统的优化框架中：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 的介绍]。现代优化继续发展出凸优化、整数优化和随机优化等方向，用于处理不同的目标结构与不确定性。
+== 参考来源与延伸阅读 ==
+* [https://web.stanford.edu/~boyd/cvxbook/ Boyd 与 Vandenberghe：Convex Optimization]，作者提供的教材与讲义，见凸性、最优性条件与对偶章节。
+* [https://mathshistory.st-andrews.ac.uk/Biographies/Kantorovich/ MacTutor：Kantorovich]；[https://news.stanford.edu/stories/2005/05/george-b-dantzig-operations-research-professor-dies-90 Stanford：Dantzig 与单纯形法]。
 * [[导数]] · [[线性代数]] · [[数学建模]]
-[[分类:应用与建模]]
+[[分类:优化与运筹]]