第五讲 非线性规划的基本概念
非线性规划问题
非线性规划数学模型
非线性规划的图解法
梯度、Hesse矩阵、Jacobi阵
凸函数和凸规划
解非线性规划方法概述
一维最优化
在科学管理和其他领域中，大量应用问题可以归结为线性规划
问题，但是，也有另外许多问题，其目标函数和（或）约束条件
很难用线性函数表达。如果目标函数和（或）约束条件中包含有
自变量的非线性函数，则这样的规划问题就属于非线性规划。
非线性规划是运筹学的重要分支之一。最近30多年来发展很
快，不断提出各种算法，而其应用范围也越来越广泛。比如在各
种预报、管理科学、最优设计、质量控制、系统控制等领域得到
广泛且不短深入的应用。
一般来说，求解非线性规划问题比线性规划问题困难得多。
而且，也不象线性规划那样有单纯形法这一通用的方法。非线性
规划的各种算法大都有自己特定的使用范围，都有一定的局限性。
到目前为止还没有适合于各种问题的一般算法，这是需要深入研
究的一个领域。我们只是对一些模型及应用作简单介绍。
1 非线性规划问题举例
例一：选址问题
设有 个市场，第 个市场位置为 ，它对某种货物的需要
量为 。现计划建立 个仓库，第 个仓库的存储
容量为 试确定仓库的位置，使各仓库对各市场的
运输量与路程乘积之和为最小。
设第 个仓库的位置为 第 个仓库到第
个市场的货物供应量为 则第 个
仓库到第 个市场的距离为
目标函数为
约束条件为
（1）每个仓库向各市场提供的货物量之和不能超过它的
存储容量。
（2）每个市场从各仓库得到的货物量之和应等于它的
需要量。
（3）运输量不能为负数
例2. 木梁设计问题
把圆形木材加工成矩形横截面的木梁，要求木梁高度
不超过 ，横截面的惯性矩（高度的平方 宽度）不小
于 ，而且高度介于宽度与4倍宽度之间。问如何确定木
梁尺寸可使木梁成本最小.
设矩形横截面的高度为 ， 宽度
为 ，则圆形木材的半径
而木梁长度无法改变，因此成本只与圆形而木梁长度无法改变，因此成本只与圆形
木材的横截面积有关。木材的横截面积有关。
目标函数为
约束条件为
（1）数学规划模型的一般形式：
其中,
简记为MP(Mathematical Programming)
2 非线性规划问题的数学模型
（2）简记形式：
引入向量函数符号：
（3）数学规划问题的分类：
若 为线性函数，即为线性规划(LP)；
若 至少一个为非线性,
即为非线性规划(NLP)；
对于非线性规划，若没有 ,即X=Rn,称为
无约束非线性规划或无约束最优化问题；
否则称为约束非线性规划或约束最优化问题。
（4）可行域和可行解：
称
为MP问题的约束集或可行域。
若x在X内，称x为MP的可行解或者可行点。
（5）最优解和极小点
对于非线性规划（MP），若 ，并且有
如果有
定义:
如果有
定义
则称 x* 是(MP)的局部最优解或局部极小解,
例1： 用图解法求解
min f(x)=(x1－2)2 +(x2－2)2
. h(x)= x1 + x2 - 6 = 0
x1
x2
0
6
62
2
3
3
最优解 x* = ( 3，3 )T
可行解 x = ( ， )T
最优级解即为最小圆的半径：
f(x)=(x1－2)2 +(x2－2)2 = 2
3 非线性规划问题的图解法
对二维最优化问题，总可以用图解法求解，而对三维或高维问题，
已不便在平面上作图，此法失效。
x1
x2
0
6
62
2
D可行域
最优解 x* = ( 2，2 )T
例2： 用图解法求解
min f(x)=(x1 - 2)2 +(x2 - 2)2
. h(x)= x1 + x2 - 6 ≤ 0
3 非线性规划问题的图解法
最优级解即为最小圆的半径：
f(x)=(x1 - 2)2 +(x2 - 2)2 = 0
• 解：①先画出等式约束曲线 的图形——抛物线，
• 例3：用图解法求解
• ②再画出不等式约束区域，
• ③最后画出目标函数等值线，
• 所以 最优解 x*=(4,1), 最优值 min f(x)=4.
4 梯度、Hesse矩阵、Jacobi阵
• (1) (1) 二次函数二次函数
一般形式:
矩阵形式:
二次型:
矩阵A的正定性: 正定、半正定、负定、不定。
其中A＝AT。
二次型的正定性: 正定、半正定、负定、不定。
（（22）） 梯度梯度
定义：f(x) 是定义在En上的可微函数。f(x) 的n个偏导数
为分量的向量称为f(x) 的梯度.
性质：设f(x) 在定义域内有连续偏导数，即有连续梯度，
则梯度有以下两个重要性质：
性质一 函数在某点的梯度不为零，则该梯度方向必与
过该点的等值面垂直;
性质二 梯度方向是函数具有最大变化率的方向（负梯
度方向也叫最速下降方向）。
解： 由于
例：试求目标函数 在点 x =[0,1]T
处的最速下降方向，并求沿这个方向移动一个单位长度后
新点的目标函数值。
则函数在 x =[0,1]T 处的最速下降方向是
这个方向上的单位向量是：
解： 由于
例：试求目标函数 在点x =[0,1]T
处的最速下降方向，并求沿这个方向移动一个单位长度后
新点的目标函数值。
新点是：
函数值：
• 几个常用的梯度公式：
（（33））HesseHesse矩阵矩阵
多元函数 f(x) 关于x的二阶导数，称为 f(x)的Hesse矩阵.
当f(x)的所有二阶偏导数连续时,即
Hesse矩阵是对称的.
时，
•几个常用Hessian公式：
（（44））JacobiJacobi矩阵矩阵
• 向量变量值函数：
向量值函数g(x)在点 x0处的Jacobi矩阵
• 向量变量值函数的导数：
(1)凸函数：
定义
5 凸函数和凸规划
例：正定二次函数
其中A是正定矩阵， f(x)是凸函数。
参见参见P104P104例。例。
性质1:
（2）凸函数的性质
性质2:
是凸集。
证明:略.
定理1：（一阶条件）
n=1时几何意义：可微函数是凸的等价于切线不在函数图像
上方。
（3） 凸函数的判定
定理2：（二阶条件）
（4）凸规划的定义及其性质：
凸规划定义：
凸规划性质：
凸规划的任一局部最优解都是它的整体最优解。
凸规划是以后重点讨论的一类非线性规划
凸函数
线性函数
（1）微分学方法的局限性：
实际的问题中，函数可能是不连续或者不可微的。
需要解复杂的方程组，而方程组到目前仍没有有效
的算法。
实际的问题可能含有不等式约束，微分学方法不易
处理。
6 非线性规划方法概述
（2）数值方法的基本思路：迭代
给定初始点x0 根据x0,依次迭代产生点列{xk}
{xk}的最后一点为最优解
{xk}有限 {xk}无限
{xk}收敛于最优解
迭代格式
xk xk+1p
k
称pk为第k轮搜索方向，tk为第k轮沿pk方向的步长。
产生tk和pk的不同方法，形成了不同的算法。
定义：特殊搜索方向——下降方向
定义：特殊搜索方向——可行可行下降方向
解非线性规划问题，关键在于
找到某个方向，使得在此方向
上，目标函数得到下降，同时
还是可行方向。
这样的方向称为可行下降方向。
定义：算法收敛、下降迭代算法
集合S上的迭代算法：
（1）初始点 ；
（2）按照某种搜索方向pk产生下一个迭代点
（i）如果点列 收敛于最优解 ，则称此算法收敛。
（ii）如果 ，则称此算法为
下降迭代算法。
.
. .
（3）下降迭代算法步骤
（1）给出初始点 ，令 ；
（2）按照某种规则确定下降搜索方向 ；
（3）按照某种规则确定搜索步长 ，使得
；
（4）令 ， ；
（5）判断 是否满足停止条件。是则停止，否则转第2步。
搜索步长确定方法：
称 为最优步长，且有对k的梯度
（4） 终止条件
②
④
①
③
（5）常用的收敛性判别准则:
（１）点收敛准则: ( 可取Rn中任一种模)。e£- - )1()( kk xx ·
（２）目标函数值准则： （绝对差）。e£-
- )()( )1()( kk ff xx
（３）目标函数值准则： （相对差）。e£
- -
)(
)()(
)(
)1()(
k
kk
f
ff
x
xx
取其中之一,也可同时取(1)与(2);(1)与(3);或(1),(2)和(3)等。
（6）算法的收敛速度
则称 的收敛阶为 。
设算法所得的点列为 ，如果
1.线性收敛（当k充分大时）：
2.超线性收敛：
3.二阶收敛： （*）式中 =2时成立。
（（**））
单变量(一维)最优化
一维最优化问题
进退法
黄金分割法
抛物线搜索法
三次插值法
下降迭代算法中最优步长的确定
.
.
一维最优化问题：
解析的方法（极值点的必要条件）
一、一维最优化问题
1. 单峰函数
定义：设 是区间 上的一元函数， 是 在
上的极小点，且对任意的 有
（a）当 时，
（b）当
. .. . .
则称 是单峰函数。
.
.
性质：通过计算区间 [a, b] 内两个不同点的函数值，就可
以确定一个包含极小点的子区间。
定理 设 是区间 上的一元函数， 是 在
上的极小点。任取点 则有
（1）如果 ，则
（2）如果 则
. ... .
2 搜索法求解：
或
基本过程：
给出[a,b],使得x*在[a,b]中。[a,b]称为搜索区间。
迭代缩短[a,b]的长度。
当[a,b]的长度小于某个预设的值，或者导数的绝
对值小于某个预设的正数，则迭代终止。
二．进退法
思想 从一点出发,按一定的步长, 试图确定出函数值呈现“高 - 低
- 高”的三点。一个方向不成功，就退回来，再沿相反方
向寻找。
进退法的计算步骤
如何确定包含极小点的一个区间？
例：
假定：已经确定了单峰区间[a,b]
x1 x2a b a bx1 2
新搜索区间为[a,x2] 新搜索区间为[x1,b]
三. 黄金分割法（法）
区间缩小比例的确定：
区间缩短比例为(x2-a)/(b-
a)
缩短比例为(b-x1)/(b-
a)
缩短比例 满足：
每次插入搜索点使得两个区间[a,x2]和[x1,b]相等；
每次迭代都以相等的比例缩小区间。
法
x1 x2a b a bx1 x2
黄金分割法的计算公式的推导：
通过确定 的取值，使上一次迭代剩余的迭代点恰与下一次
迭代的一个迭代点重合，从而减少算法的计算量。
同理可得。
3. 法的算法步骤：
确定[a,b],计算探索点
x1=a+(b-a)
x2=a+(b-a)
是 否
是
停止，输出x1
否
以[a,x2]为新的搜索区间
是
停止，输出x2
否 以[x1,b]为新的搜索区间
3. 法的算法框图：
黄金分割法的迭代效果：
第 k 次后迭代后所得区间长度为初始区间长度的
其它的试探点算法：Fibonacci算法。
例：
解：
t1 t2 30 t
1、第一轮：
t1=, t2=
t2－0>
2、第二轮：
t2=, t1=
t2－0=>
3、第三轮：
t1=, t2=
b -t1=>
tt2
t1
t
t2t1
4、第四轮：
t2==(), t1=
b-t1=<
输出：t*=t2=为最优解，最优值为
0 t
t1t2
四． Fibonacci法
此法类似于法，也是用于单峰函数。其计算过程也
与类似，第1次迭代计算两个试探点，以后每次迭代只需
新加一点，另一试探点取自上次的迭代点。此法与法的
主要差别为：区间长度的缩短比率不是常数，而是由
Fibonacci 数确定；给出精度后，迭代次数可预先确定；适合
于参数只能取整数值的情况。
定义 称满足条件
（i）F0 = F1 = 1；
（ii）
的数列{ Fn }为Fibonacci数列。
由定义推知Fibonacci数列的前10项为1,1,2,3,5,8,13,21,34,55,89。
通过求解递推关系可求得该数列的通项为
ú
ú
û
ù
ê
ê
ë
é
ø
ö
ç
ç
è
æ -
-
ø
ö
ç
ç
è
æ +
=
++ 11
2
51
2
51
5
1
nn
nF （）
由（）式可求得 。利用Fibonacci数的这一特
点，用 法中的，再梢加改进，便是
Fibonacci法。
»-
n
n
F
F
代替
n
n
F
F -
在Fibonacci法中，第n次迭代的搜索区间的长度（记为
）是上一次区间长度的 倍
所以要使在第n次迭代时搜索区间的长度不超过ε，只需
£0
1
L
Fn
ε （）
即可。因 是已知值，所以给出精度ε后利用（）式可求
得迭代次数。
Fibonacc法在迭代中计算试探点的公式为
即有即有
Fibonacci法
(1) 对初始区间 和精度ε>0，求目标函数值的计算
次数 n，使
置辨别常数δ>0。计算试探点
计算函数值和 。置k =1。
（2） 若 ，则转（3）；
若 ，则转（4）。
（3
）
（5） 置k﹕= k+1，转（2）。
（4
）
（6
）
思想 在极小点附近，用二次三项式
四. 抛物线（二次）插值
即“两头大中间小”
如何计算函数
令
x =
33
22
11
2
33
2
22
2
11
1
1
1
1
1
1
2
1
fx
fx
fx
xf
xf
xf
-
抛物线插值算法步骤：
解出
思路：
五. 三次插值法
设
令
则有
求解满足 的极小点
令
而
解方程（3），有两种情况：
由（2）可知
极小点的计算公式：
令
算法步骤：
其它插值算法：有理插值。
收敛速度：三次插值算法的收敛阶为2。
六、MATLAB
• 单变量函数求最小值的标准形式为
函数 fminbnd
格式 x = fminbnd(fun,x1,x2) %返回自变量x在区间
上函数fun取最小值时x值，fun为目标函数的表达式字符串
或MATLAB自定义函数的函数柄。
函数fminbnd的算法基于黄金分割法和二次插值法，它要求
目标函数必须是连续函数，并可能只给出局部最优解。
• x = fminbnd(fun,x1,x2,options) % options为指定优化
参数选项
• [x,fval] = fminbnd(…) % fval为目标函数的最小值
• [x,fval,exitflag] = fminbnd(…) %xitflag为终止迭
代的条件
• [x,fval,exitflag,output] = fminbnd(…) % output
为优化信息
• 说明 若参数exitflag>0，表示函数收敛于x，若
exitflag=0，表示超过函数估计值或迭代的最大数字，
exitflag<0表示函数不收敛于x；若参数
output=iterations表示迭代次数，output=funccount表
示函数赋值次数，output=algorithm表示所使用的算法。
例1 计算下面函数在区间(0，1)内的最小值。
解：[x,fval,exitflag,output]
=fminbnd('(x^3+cos(x)+x*log(x))/exp(x)',0,1)
x =
fval =
exitflag =
1
output =
iterations: 9
funcCount: 9
algorithm: 'golden section search, parabolic
interpolation'
主程序为:
f='2*exp(-x).*sin(x)';
fplot(f,[0,8]); %作图语句
[xmin,ymin]=fminbnd (f, 0,8)
f1='-2*exp(-x).*sin(x)';
[xmax,ymax]=fminbnd (f1, 0,8)
