优化

数学优化是在给定可行范围内寻找目标函数最小值或最大值的问题。最小化 $f$ 与最大化 $-f$ 可以互相转换。一个优化模型必须说明决策变量、目标与约束；“最好”只有在这些选择明确后才有数学含义。

英文名称：Mathematical optimization。

English overview

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.

目标函数与可行域

一般约束优化可写为 $$\underset{x\in {ℝ}^n}{min}f(x)\text{使得}{g}_i(x)\le 0,h_j(x)=0.$$ 满足所有约束的点构成可行域。不可行的问题没有可行解；有可行解也未必能取得最小值。例如 $\underset{x>0}{min}x$ 的下确界为 0，却没有可行点达到 0。连续函数在非空紧集上一定能取得最大、最小值，这是常用的存在性保证。

一个带边界的一维例子

考虑 $$\underset{x\ge 2}{min}(x-1{)}^2.$$ 没有约束时，导数 $2(x-1)=0$ 给出 $x=1$，但该点不可行。对所有 $x\ge 2$，函数递增，所以最优点为 $x=2$，最小值为 1。

约束改变最优解；只解“导数等于零”会漏掉边界最优点。

若在可行域内部取得局部极小值，且函数可微，那么梯度为零是必要条件。但驻点不一定是极小值，例如 $f(x)=x^3$ 在 0 的导数为零却没有极值。

局部最优、全局最优与凸性

局部最优只要求在附近没有更好点；全局最优要求整个可行域都没有更好点。集合 $C$ 凸是指任意两点间的线段都在集合内。函数在凸域上凸，是指对 $0\le t\le 1$， $$f(tx+(1-t)y)\le tf(x)+(1-t)f(y).$$ 凸优化问题的局部极小点也是全局极小点。这并不自动保证最优点存在或唯一；严格凸函数若在凸域上取得最小值，才保证最优点唯一。线性规划要求线性目标与线性等式、不等式约束，是重要的凸优化类别。

拉格朗日乘子怎样使用

求 $x^2+y^2$ 在 $x+y=1$ 下的最小值。定义 $$L(x,y,\lambda )=x^2+y^2+\lambda (x+y-1).$$ 令对 $x,y$ 的偏导为零，并满足约束，得到 $2x+\lambda =0$、$2y+\lambda =0$、$x+y=1$，所以 $x=y=1/2$，目标值为 $1/2$。

这次结论还可直接验证：由 $x^2+y^2=((x+y{)}^2+(x-y{)}^2)/2\ge 1/2$，等号恰在 $x=y$ 时成立。一般问题使用乘子法需要约束正则性等条件，求出驻点后仍需判断它是极小、极大还是其他情形。

梯度下降与步长

无约束可微问题常用迭代 $x_{k+1}=x_k-\eta \mathrm{\nabla }f(x_k)$，其中 $\eta >0$ 是步长。对 $f(x)=(x-1{)}^2$，误差满足 $$x_{k+1}-1=(1-2\eta )(x_k-1).$$ 只有 $0<\eta <1$ 时，这个固定步长迭代对任意初值都收敛到 1；步长过大会振荡或发散。这个区间是本例结论，不能照搬到所有目标函数。

解得精确不等于模型正确

数学建模中的目标可能是误差、成本或耗时，不同目标会产生不同解。多目标问题需要说明权衡，数值软件报告“成功”后还应检查约束残差、最优性条件和参数敏感性。整数决策、非凸结构和噪声目标可能需要不同算法。

从一个现实要求写出数学问题

设要安排两种产品产量，机器有工作时间上限，原料有库存上限。如果目标是利润最大，应把售价与成本换成同一计量单位；如果目标改为准时交货，最佳方案可能完全不同。变量还要说明是连续量还是整数：液体体积可以近似连续，车辆数量通常不能是 2.7 辆。约束描述可接受的方案，目标用于在这些方案之间排序，不能把二者混成一句“尽量满足需求”。

一个明确的模型还应交代参数是否已知。把需求预测当作确定常数会得到确定性模型；考虑多个情景、概率或最坏情况，会得到不同的随机或鲁棒优化问题。这些处理没有脱离问题背景的统一优劣。建模者首先需要说明承担什么不确定性，以及解的含义是某个情景的最优、平均表现较好，还是对一组情景都可行。

存在、唯一与算法成功是三个问题

函数 $f(x)=e^x$ 在整个实数轴上大于零，下确界为零，但没有任何有限 x 使函数等于零，因此没有极小化解。函数 $f(x)=0$ 在区间 [0,1] 上处处达到最小值，所以最优解不唯一。函数连续且可行域非空、闭且有界时，在有限维欧氏空间中紧性保证能取到极值；无界可行域也可能有解，只是不能直接使用这一个保证。

存在一个理论最优点，不代表任意算法都能找到它。算法停止可能是达到迭代上限、步长很小或数值变化很小，这些都不自动证明全局最优。相反，若能给出对所有可行点成立的下界，并找到一个点达到它，便得到一个可以独立检查的最优性证书。前面的平方和例子正是如此：恒等式给出下界二分之一，点 (1/2,1/2) 达到下界。

凸性为何能排除较差的局部极小点

设 f 在凸集 C 上凸，x 是局部极小点，却假设存在 y∈C 使 $f(y)<f(x)$。对任意很小的正数 t，线段上的 $z=(1-t)x+ty$ 仍在 C 中，并可任意靠近 x。凸性给出 $$f(z)\le (1-t)f(x)+tf(y)<f(x).$$ 这与 x 附近没有更小函数值矛盾，所以 x 必为全局极小点。证明只用了两件事：两点之间可以沿可行线段移动，以及函数在该线段上不高于端点值的线性插值。缺少其中任何一个条件，结论就不能照搬。

若 f 严格凸，假设两个不同最优点 x、y 具有同一最小值，那么它们中点的值严格小于这个最小值，产生矛盾。因此只要最优点存在，就至多一个。普通凸性则允许平坦方向。例如 $f(x,y)=x^2$ 凸，但所有 (0,y) 都是全局最优点。函数看起来“碗状”的比喻在多维中应谨慎使用，平底或平坦方向并不破坏凸性。

一阶条件给出的全局证书

可微凸函数满足一阶下界 $$f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^{𝖳}(y-x).$$ 可从凸性沿线段定义 $\varphi (t)=f(x+t(y-x))$，把凸性不等式移项、除以 t>0，再令 t 趋于零得到。几何上，切超平面位于函数图像下方。因此无约束时若梯度为零，就有 $f(y)\ge f(x)$ 对所有 y 成立，驻点确实是全局最优点；“凸且可微”是这里不可省略的条件。

在凸可行域 C 上，更一般的证书是 $\mathrm{\nabla }f(x{)}^{𝖳}(y-x)\ge 0$ 对所有可行 y 成立。边界最优点的梯度可以非零，因为负梯度方向可能指向不可行区域。对本条开头的 $x\ge 2$ 例子，在 x=2 处梯度为二，所有可行方向满足 y−2≥0，故这个证书成立。这样就把边界检查与一阶条件统一了起来。

二阶信息可以帮助判断局部行为：无约束二次函数若 Hessian 矩阵正定，则严格凸；在一般二次连续可微函数的驻点处，正定 Hessian 是严格局部极小的充分条件，半正定却不总是充分。例如 $x^4$ 与 $-x^4$ 在零处二阶导数同为零，局部行为相反，必须看更多信息。

乘子方法不能省略的条件

在等式约束 $h(x)=0$ 下，局部最优点处目标梯度通常要与约束梯度方向配合，因为沿可行曲面的切向移动不能一阶降低目标。多重约束时，约束梯度线性无关等正则性条件保证可以寻找乘子，使目标梯度由约束梯度线性组合表示。乘子方程给出候选点，再做可行性和最优性检查。

条件失败可能使普通乘子方程漏解。例如最小化 f(x)=x，约束 $h(x)=x^2=0$，唯一可行点 x=0 自然最优，但 $f^{\prime }(0)+\lambda h^{\prime }(0)=1+\lambda \cdot 0$ 永不为零。原因是约束在该点梯度为零，通常的正则性前提不成立。这一小例子说明：一个解方程步骤失败，并不意味着原优化问题没有解。

不等式约束的 KKT 条件还包括乘子非负、原问题可行与互补松弛。在适当正则性下它们是局部最优的必要条件；在目标函数与不等式约束函数凸、等式约束仿射且相关函数可微的标准凸问题中，满足 KKT 条件的点可提供全局最优证书。入门时可以先在线性规划里通过具体的对偶不等式理解证书，再逐步学习一般理论，避免把四组公式当作所有问题都适用的万能求解器。

完整算例：梯度下降为何会振荡

仍取 $f(x)=(x-1{)}^2$，初值 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，误差绝对值通常增大。只有初值恰为一时，任何步长都停在最优点，因此先前给出的区间描述的是“对任意初值都收敛”的条件。此处明确量词，可以避免用一个特殊初值错误地反驳或证明算法结论。

多维二次问题中，不同方向可能具有很不一样的曲率，步长必须兼顾最陡方向，较平坦方向便收敛很慢。这与矩阵的条件数有关。变量单位相差很多也可能造成数值尺度失衡；重新缩放可以改善计算，但不能随意改变目标中的相对权重，否则是在求另一个问题。实现后应输出目标值、约束残差和停止原因，而不只给一个“成功”标签。

一个边界问题的完整 KKT 证书

把开头的约束写为 $g(x)=2-x\le 0$，拉格朗日函数为 $L(x,\lambda )=(x-1{)}^2+\lambda (2-x)$。候选点 $x_{\ast }=2$ 配上乘子 ${\lambda }_{\ast }=2$，分别满足可行性、乘子非负、互补松弛 ${\lambda }_{\ast }g(x_{\ast })=0$，以及驻点关系 $2(x_{\ast }-1)-{\lambda }_{\ast }=0$。四项条件在一个具体问题中各有可检查的数值含义。

更直接的证书来自固定这个乘子后的恒等式： $$L(x,2)=(x-2{)}^2+1\ge 1.$$ 对任何可行点 $x\ge 2$，约束项 $2(2-x)\le 0$，所以 $f(x)\ge L(x,2)\ge 1$；候选点恰好达到一。这个证明同时给出全域下界与达到下界的可行解，不依赖某个求解器的成功标志。

乘子非负不能省略。它使“加上约束项”在可行点处只会降低目标，从而产生有效下界；若把符号任意反转，这条不等式链就可能失效。互补松弛说明在最优候选点处，这个下界没有因为约束项而留下额外空隙。对不活跃约束，乘子可以为零；活跃约束也不一定要求乘子严格为正。

在标准可微凸模型中，KKT 条件的充分性不要求另外先假定 Slater 条件；Slater 一类正则性常用于保证最优解存在相应乘子以及强对偶。把“一个 KKT 点足够证明最优”与“每个最优点必有 KKT 乘子”分开，才能避免把必要性和充分性混为一谈。Boyd 与 Vandenberghe，第 5 章讲义

数值证书也需要区分精确与近似：若约束残差只是很小，而没有被严格控制，得到的只是近似可行性；若上下界仍留有差距，则应报告这个最优性差距。容差应与变量尺度相匹配，不能把任意一组默认小数阈值当作所有问题都适用的证明。

局部最优也应相对可行域解释：存在一个邻域，使其中的可行点都不比候选点更好；邻域里的不可行点不参与比较。可行域若离散，一个孤立可行点天然局部最优，却可能远逊于另一个可行点。因此凸性定理中的可行线段条件确实不可少，不能把连续凸问题的结论搬到任意整数决策问题中。

历史与方法谱系

极值研究与几何、微积分长期相连，现代优化不能归结为一个人的一次发现。二十世纪线性规划的发展与资源分配问题密切相关。Kantorovich 在 1939 年发表相关工作，Dantzig 在 1947 年提出单纯形法；MacTutor 传记与斯坦福大学的 Dantzig 纪念文章分别介绍了这些背景。模型的提出、对偶理论的形成与算法的实现是不同贡献，不宜压缩成简单的“谁发明优化”。

今天优化还包括离散、非凸、多目标、随机等方向。凸优化提供了一组结构清楚、理论与算法联系紧密的问题，但不覆盖所有实际决策。尤其当目标涉及多个不可直接通约的标准时，数学能揭示权衡和可行边界，不能自行替决策者选择价值排序。

编者评注（AI 辅助）

本条建议用“候选解—可行性—证书”三步阅读每个算例。先得到一个数值只是开始，检查它是否满足约束，再说明为什么没有更好方案，才完成了数学任务。把模型假设与求解误差分别记录也很重要：一个被精确求解但目标选错的模型，可能不如一个较粗糙却正确回答实际问题的模型。学习时宜先把小问题手算清楚，再借助软件处理大规模情形。

参考来源与延伸阅读

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