查看“︁优化”︁的源代码

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

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

== 从一个有边界的问题开始 ==
考虑
<math display="block">\min_{x\ge2}(x-1)^2.</math>
这里 <math>x</math> 是变量，<math>(x-1)^2</math> 是目标，<math>x\ge2</math> 是约束。若没有约束，平方项在 <math>x=1</math> 时为零；但这个点不在可行域中。

任意可行点都能写为 <math>x=2+t</math>，其中 <math>t\ge0</math>。代入目标：
<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>2(x-1)=0</math>，会漏掉真正答案。导数为零是在可行域内部取得可微极值的必要条件，边界需要结合可行方向判断。

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

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

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

== 两个变量：先利用约束消去一个 ==
求 <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 与单纯形法]。
* [[导数]] · [[线性代数]] · [[数学建模]]
[[分类:优化与运筹]]