第5章非线性规划（一）：一维搜索与多元无约束优化

系统分析：线性规划、非线性规划与排队模型 · 第 5 / 11 篇（展开目录）

从线性规划建模、单纯形法、对偶与灵敏度、运输与指派，到非线性规划、随机过程、马尔可夫链、排队模型和决策分析，每章都配手算例题和自测，最后一章用综合例题把方法串起来。

约 30 分钟 · 需要会求偏导数和 2×2、3×3 行列式

读完你能： 把定价、设计类问题写成非线性规划；说清单峰性与区间消去规则；手算 Fibonacci 搜索、黄金分割搜索和一维牛顿法；求梯度和 Hessian 矩阵，用顺序主子式判断正定、负定、不定，并据此分类驻点；写出多元牛顿迭代并判断它会不会走错方向。

贯穿例子： $f(x)=x^2+\dfrac{16}{x}$ （ $x>0$ ），最小点 $x^*=2$ ， $f(2)=12$ 。三种一维方法都用它，方便比较。

1. 什么是非线性规划

线性规划的目标和约束都是一次式。只要有一处不是，就是非线性规划（NLP）：

\min\ f(X)\qquad \text{s.t.}\quad h_i(X)=0\ (i=1,\dots,m),\qquad g_j(X)\le0\ (j=1,\dots,p).

最大化问题求 $\min\ -f(X)$ ，最后把最优值乘 $-1$ 。没有约束的叫无约束问题。

例1：定价。 单位成本 10 元，售价为 $p$ 时需求 $D(p)=100-2p$ 。利润 $(p-10)(100-2p)$ 最大的售价是多少？这是一元无约束问题：令导数 $(100-2p)-2(p-10)=120-4p=0$ ，得 $p=30$ ，最大利润 $20\times40=800$ 元。

例2：容器设计。 有盖的圆柱形罐至少装 20 m³，侧面和顶的材料 50 元/m²，底更厚，200 元/m²；为防止头重脚轻，高度不超过直径的 2 倍。设直径 $x_1$ 、高 $x_2$ ：

\min\ 50\Big(\pi x_1x_2+\tfrac{\pi x_1^2}{4}\Big)+200\cdot\tfrac{\pi x_1^2}{4} \qquad\text{s.t.}\quad \tfrac{\pi x_1^2}{4}x_2\ge20,\quad x_2\le2x_1,\quad x_1,x_2\ge0 .

非线性规划的难点在于：可行域不一定是多边形，最优解可以在可行域内部，也可以在边界的任意位置；而且可能有多个局部最优，只有一个是全局最优。没有通用算法能解所有非线性规划，本章和下一章介绍几类最重要的情形。

2. 局部最优、单峰性与区间消去

$f$ 在 $x_0$ 有局部极小：存在 $x_0$ 附近的一个小区间，区间内 $f(x)\ge f(x_0)$ 。若对定义域内所有 $x$ 都成立，则是全局极小。

直接搜索法只用函数值，不用导数。前提是在初始区间 $[a,b]$ 上 $f$ 单峰：区间内只有一个局部极值点。在区间内取两点 $x_1<x_2$ ，对单峰函数求极小：

比较结果	结论
$f(x_1)>f(x_2)$	极小点不在 $[a,x_1]$ ，保留 $[x_1,b]$
$f(x_1)<f(x_2)$	极小点不在 $[x_2,b]$ ，保留 $[a,x_2]$
$f(x_1)=f(x_2)$	两端都可去掉，保留 $[x_1,x_2]$

求极大时把比较方向反过来。区间消去法的区别只在于“试点放在哪里”：放得好，每次只需算一个新函数值，旧的试点可以继续用。

3. 黄金分割搜索

把两个试点放在距两端各 $0.618L$ 处（ $L$ 为当前区间长度）。消去一段后，留下的那个旧试点恰好又位于新区间的黄金分割位置，所以每轮只需新算一个点：新点放在距最新端点 $0.618L$ 处。 $0.618\approx(\sqrt5-1)/2$ ，每轮区间缩为原来的 0.618 倍。

例3： 在 $[1,6]$ 上求 $f(x)=x^2+16/x$ 的极小，精度 $\varepsilon=1$ 。

初始 $L=5$ ，试点 $1+0.618\times5=4.090$ 与 $6-3.090=2.910$ ： $f(2.910)=13.966<f(4.090)=20.640$ ，去掉 $[4.090,6]$ 。

轮	新区间	长度	新试点	$f$ (新试点)	比较后去掉
1	$[1,\ 4.090]$	3.090	$4.090-0.618\times3.090=2.180$	12.092	$f(2.180)<f(2.910)$ ，去掉 $[2.910,4.090]$
2	$[1,\ 2.910]$	1.910	$2.910-0.618\times1.910=1.730$	12.242	$f(1.730)>f(2.180)$ ，去掉 $[1,1.730]$
3	$[1.730,\ 2.910]$	1.180	$1.730+0.618\times1.180=2.459$	12.554	$f(2.180)<f(2.459)$ ，去掉 $[2.459,2.910]$
4	$[1.730,\ 2.459]$	0.729	$2.459-0.618\times0.729=2.008$	12.000	区间已短于 $\varepsilon$

区间长度降到 0.729 < 1，停止。区间内最好的点 $x\approx2.008$ ， $f\approx12.000$ ，与真解 $x^*=2$ 吻合。

4. Fibonacci 搜索

Fibonacci 数 $F_0=F_1=1$ ， $F_n=F_{n-1}+F_{n-2}$ ：1, 1, 2, 3, 5, 8, 13, 21, 34, …

取满足 $F_N\varepsilon\ge b-a$ 的最小 $N$ ，令 $\varepsilon'=(b-a)/F_N$ 。
前两个试点放在距两端各 $F_{N-1}\varepsilon'$ 处。
每轮消去一段后，新试点放在距最新端点 $F_j\varepsilon'$ 处， $j=N-2,N-3,\dots,2$ 。
结束时区间内最好的点与区间中任一点的距离不超过 $\varepsilon'\le\varepsilon$ 。

例4： 同一函数， $[1,6]$ ， $\varepsilon=0.5$ 。 $b-a=5$ ，需要 $F_N\ge10$ ，取 $F_6=13$ ， $N=6$ ， $\varepsilon'=5/13\approx0.3846$ 。

前两点距两端 $F_5\varepsilon'=8\times0.3846=3.077$ ： $x=6-3.077=2.923$ （ $f=14.018$ ）与 $x=1+3.077=4.077$ （ $f=20.546$ ）。左边小，保留 $[1,\ 4.077]$ 。

$j$	$F_j\varepsilon'$	新试点	$f$	保留区间
4	$5\times0.3846=1.923$	$4.077-1.923=2.154$	12.068	$f(2.154)<f(2.923)$ → $[1,\ 2.923]$
3	$3\times0.3846=1.154$	$2.923-1.154=1.769$	12.174	$f(1.769)>f(2.154)$ → $[1.769,\ 2.923]$
2	$2\times0.3846=0.769$	$1.769+0.769=2.538$	12.747	$f(2.538)>f(2.154)$ → $[1.769,\ 2.538]$

取 $x^*\approx2.154$ ， $f\approx12.07$ 。它与最终区间两端的距离都不超过 $\varepsilon'=0.385<0.5$ 。

两种方法怎么选

Fibonacci 搜索在给定计算次数下区间缩得最多，但必须事先确定 $N$ ；黄金分割每轮固定缩 0.618 倍，次数不限，更省事。两者的比例在 $N$ 很大时趋于相同——相邻 Fibonacci 数之比的极限就是 0.618。

5. 一维牛顿法

如果能求导，就可以利用导数信息加速。把 $f'(x)$ 在 $x_n$ 处线性化： $f'(x)\approx f'(x_n)+f''(x_n)(x-x_n)$ ，令其为 0：

x_{n+1}=x_n-\frac{f'(x_n)}{f''(x_n)} .

当 $|x_{n+1}-x_n|<\varepsilon$ 或 $|f'(x_{n+1})|<\varepsilon$ 时停止。

例5： $f(x)=x^2+16/x$ ， $f'(x)=2x-16/x^2$ ， $f''(x)=2+32/x^3$ ， $x_0=1$ ， $\varepsilon=10^{-5}$ 。

$n$	$x_n$	$x_{n+1}$	$\lvert x_{n+1}-x_n\rvert$
0	1	1.411765	0.411765
1	1.411765	1.800935	0.389170
2	1.800935	1.978950	0.178016
3	1.978950	1.999777	0.020827
4	1.999777	2.000000	0.000223
5	2.000000	2.000000	< $10^{-5}$

第一步： $f'(1)=2-16=-14$ ， $f''(1)=2+32=34$ ， $x_1=1+14/34=1.411765$ 。越接近解收敛越快（误差大致按平方缩小）。

牛顿法找的是 $f'(x)=0$ 的点，它不区分极小和极大。在极小点附近且 $f''>0$ 时，适当初值通常能快速收敛；但初值选得不好，仍可能越界或发散，不能只靠出发点处的正曲率保证收敛。

6. 梯度、Hessian 与正定性

$n$ 元函数的梯度和 Hessian 矩阵：

\nabla f=\Big(\frac{\partial f}{\partial x_1},\dots,\frac{\partial f}{\partial x_n}\Big)^{T},\qquad [\nabla^2 f]_{ij}=\frac{\partial^2 f}{\partial x_i\,\partial x_j}.

正定性的顺序主子式判别法。 对称矩阵 $A$ 的顺序主子式 $A_1=|a_{11}|$ ， $A_2=\begin{vmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{vmatrix}$ ，…， $A_n=|A|$ ：

结论	条件
正定	$A_1>0,\ A_2>0,\ \dots,\ A_n>0$
负定	符号交替： $A_1<0,\ A_2>0,\ A_3<0,\ \dots$
半正定	所有主子式 $\ge0$ （严格判断要看全部主子式，不只是顺序主子式）
不定	既不半正定也不半负定，例如 $A_2<0$ （2×2 时一定不定）

例6：

H=\begin{pmatrix}2&2&0\\2&4&-2\\0&-2&6\end{pmatrix}:\quad A_1=2,\quad A_2=2\cdot4-2\cdot2=4,\quad A_3=2(24-4)-2(12-0)+0=16 .

三个都为正， $H$ 正定。

7. 驻点的分类

梯度为零的点叫驻点。在驻点 $X^*$ 处：

$\nabla^2 f(X^*)$ 正定 → 严格局部极小；
$\nabla^2 f(X^*)$ 负定 → 严格局部极大；
$\nabla^2 f(X^*)$ 不定 → 鞍点，既不是极小也不是极大；
半定 → 本判别法无法确定，需要进一步分析。

例7： $f(x_1,x_2)=x_1^3-3x_1+x_2^2-4x_2$ 。

\nabla f=\begin{pmatrix}3x_1^2-3\\2x_2-4\end{pmatrix}=0\ \Rightarrow\ x_1=\pm1,\ x_2=2;\qquad \nabla^2 f=\begin{pmatrix}6x_1&0\\0&2\end{pmatrix}.

$(1,2)$ ： $H=\mathrm{diag}(6,2)$ ， $A_1=6>0,\ A_2=12>0$ ，正定，局部极小， $f=1-3+4-8=-6$ 。
$(-1,2)$ ： $H=\mathrm{diag}(-6,2)$ ， $A_2=-12<0$ ，不定，鞍点。

这个函数没有全局极小： $x_1\to-\infty$ 时 $x_1^3\to-\infty$ 。“局部极小”不保证是全局最优，这正是非线性规划和线性规划的根本区别之一。

例8： 二次函数 $f=x_1^2+2x_2^2+3x_3^2+2x_1x_2-2x_2x_3-4x_1+6x_3$ 。它的 Hessian 就是例6的常数矩阵 $H$ （处处正定），所以唯一的驻点就是全局极小。解 $\nabla f=0$ ：

2x_1+2x_2-4=0,\qquad 2x_1+4x_2-2x_3=0,\qquad -2x_2+6x_3+6=0

得 $X^*=(13/2,\ -9/2,\ -5/2)$ 。

Hessian 处处正定 = 凸函数

如果定义域是凸集，且函数在其上二阶可微、Hessian 处处半正定，函数就是凸函数，任何局部极小都是全局极小。第6章的 KKT 充分条件就建立在这个性质上。

8. 多元牛顿法

一维牛顿法推广到多元：

X_{n+1}=X_n-\big[\nabla^2 f(X_n)\big]^{-1}\nabla f(X_n),

当 $|f(X_{n+1})-f(X_n)|<\varepsilon$ 时停止。对正定二次函数，牛顿法一步就到达极小点（因为二阶泰勒展开就是函数本身）。

例9： $f=(x_1-2)^4+(x_1-2x_2)^2$ ， $X_0=(0,3)$ ，真极小点 $(2,1)$ ， $f=0$ 。

\nabla f=\begin{pmatrix}4(x_1-2)^3+2(x_1-2x_2)\\-4(x_1-2x_2)\end{pmatrix},\qquad \nabla^2 f=\begin{pmatrix}12(x_1-2)^2+2&-4\\-4&8\end{pmatrix}.

$n$	$X_n$	$f(X_n)$	$\nabla f(X_n)$	$\nabla^2 f(X_n)$
0	$(0,\ 3)$	52	$(-44,\ 24)$	$\begin{pmatrix}50&-4\\-4&8\end{pmatrix}$
1	$(2/3,\ 1/3)$	3.16	$(-9.48,\ 0)$	$\begin{pmatrix}70/3&-4\\-4&8\end{pmatrix}$
2	$(10/9,\ 5/9)$	0.62	$(-2.81,\ 0)$	$\begin{pmatrix}310/27&-4\\-4&8\end{pmatrix}$
3	$(38/27,\ 19/27)$	0.12

第一步： $\det H=400-16=384$ ， $H^{-1}=\frac{1}{384}\begin{pmatrix}8&4\\4&50\end{pmatrix}$ ， $H^{-1}\nabla f=\frac{1}{384}(-352+96,\ -176+1200)=(-2/3,\ 8/3)$ ，于是 $X_1=(0,3)-(-2/3,8/3)=(2/3,1/3)$ 。

从第一步起每个点都满足 $x_1=2x_2$ ，之后 $x_1-2$ 每步缩为原来的 $2/3$ 。四次函数不是二次的，所以要迭代多次；而且越接近解 Hessian 越接近奇异，收敛变慢。

牛顿法可能走向极大点

牛顿法只是在找 $\nabla f=0$ 的点。如果当前 Hessian 不正定（求极小时），迭代方向就可能是“上坡”，最后收敛到极大点或鞍点。求极大值时道理相同：需要 Hessian 在附近负定。迭代后发现目标没有朝希望的方向改进，就应该换一个初值。

9. 小结

NLP：目标或约束有非线性项；最大化转为最小化 $-f$ ；局部最优不一定全局最优。
区间消去：单峰前提下比较两个试点，去掉较差一侧之外的那段。
黄金分割：试点在 $0.618L$ 处，每轮新算一个点；Fibonacci： $F_N\varepsilon\ge b-a$ ，试点在 $F_j\varepsilon'$ 处。
一维牛顿： $x_{n+1}=x_n-f'/f''$ ；多元牛顿： $X_{n+1}=X_n-H^{-1}\nabla f$ 。
驻点分类：Hessian 正定 → 极小，负定 → 极大，不定 → 鞍点；用顺序主子式判断。

自测

1. 判断 $f=2x_1x_2-x_1^2-x_2^2$ 和 $g=x_1^2+4x_1x_2+x_2^2$ 的 Hessian 是正定、负定还是不定。

$\nabla^2 f=\begin{pmatrix}-2&2\\2&-2\end{pmatrix}$ ： $A_1=-2<0$ ， $A_2=4-4=0$ ，是半负定（ $f=-(x_1-x_2)^2\le0$ ），所以 $f$ 是凹函数，但不是严格凹。

$\nabla^2 g=\begin{pmatrix}2&4\\4&2\end{pmatrix}$ ： $A_2=4-16=-12<0$ ，不定，原点是鞍点。

2. 用一维牛顿法从 $x_0=4$ 出发求 $f(x)=x^2+16/x$ 的极小，写出第一步。

$f'(4)=8-1=7$ ， $f''(4)=2+32/64=2.5$ ， $x_1=4-7/2.5=1.2$ 。之后继续迭代会收敛到 2。初值离解远时第一步可能“冲过头”（从 4 跳到 1.2，越过了 2），本例继续迭代会收敛；一般问题中即使出发点曲率为正，也应检查后续迭代是否越界，并配合步长控制。

3. 两家工厂合谋：总产量 $x=x_1+x_2$，售价 $200-x$，成本分别为 $x_1$ 和 $0.5x_2^2$。总利润最大时各生产多少？

$f=(200-x_1-x_2)(x_1+x_2)-x_1-0.5x_2^2=199x_1+200x_2-x_1^2-2x_1x_2-1.5x_2^2$ 。

$\partial f/\partial x_1=199-2x_1-2x_2=0$ ， $\partial f/\partial x_2=200-2x_1-3x_2=0$ ，解得 $x_2=1$ ， $x_1=98.5$ 。Hessian $\begin{pmatrix}-2&-2\\-2&-3\end{pmatrix}$ ： $A_1=-2<0$ ， $A_2=6-4=2>0$ ，负定，是极大点。