都有f(X0) f(X) ，则称 X 0 为（NLP）的局部最
优 解，也称为局部最小值点。
2020/6/5
例1：考虑非线性问题
minf(X)(x12)2(x22)2 s.t. x1x26
x2
6
3
如 果 约 束 改 为
x1 x2 6
呢 ？
2020/6/5
3
6
x1
2.梯度、海塞阵与泰勒公式
★梯度
若 f(X)在 X0的 邻 域 内 有 连 续 一 阶 偏 导 数 ， 则 称 f(X)在 X0点 对 n 个 变 元 的 偏 导 数 组 成 的 向 量 为 f(X)在 X0的 梯 度 ， 记 为 f(X0)， 即 f(X0)＝ [f(xX10)， L， f(xXn0)]T 几 何 意 义 ：
③在 [a1,b1]中按F Fnn12的比例取点t2(与区间中所剩的点对称)
比较f(t2)和min{f(t1),f(t1')}，去掉较大者对应点以外的 区间，得到新区间 [a2,b2]；
④ 在 [a2,b2]中 按 F Fn n 3 2的 比 例 取 点 t3再 比 较 、 再 缩 短 ， 直 到 取 完
2020/6/5
★凸规划 在非线性规划模型（NLP）中，若目标函数f（X）是凸函
数，不等式约束函数gj(X) j1,L,l为凹函数，等式约束 函数 hi(X) i1,L,m为仿射函数，则称（NLP）是一个
凸规划。
性质：★约束集是凸集； ★最优解集是凸集； ★任何局部最优解也是全局最优解； ★若目标函数是严格凸函数，且最优解存在，则 其最优解是唯一的。
2020/6/5
也不一样。
3.收敛性
衡量标准： lki mPPXXkk1XX* P*P
① 1 ,0 1 ,则 称 { X k } 是 线 性 收 敛 的 ； ② 1 , 0 ,则 称 { X k } 是 超 线 性 收 敛 的 ；
③ 2 , 0 , 则 称 { X k } 是 二 阶 收 敛 的 。
,
m ,l
其 中 X [ x1,L , xn ]T 记 D { X R n | hi( X ) 0, g j( X ) 0} 则 （ N L P） 也 可 以 表 示 为 m in f ( X )
X D
其 中 D称 为 （ NLP） 的 约 束 集 或 可 行 域 。 当 D ＝ R n时 ， （ N L P ） 称 做 无 约 束 极 值 问 题 ； 当 D R n时 ， （ N L P ） 称 做 约 束 极 值 问 题 。
2020/6/5
例4：判断下面的非线性规划是否为凸规划
m ax f ( X ) x1 x2
s.t.
x12
x
2 2
1
x1, x2 0
标准化
min( f ( X )) x1 x2
s.t
.
g1 g2
( (
X X
) )
1 x1
x12 0
x
2 2
0
g
3
(
X
)
x2
0
0 0
2 0
Hf (X)0 00,Hg1(X)0 20
(3) 从 X k 出 发 ， 确 定 搜 索 方 向 P k ；
(4) 沿 P k方 向 搜 索 ， 即 由 X ＝ X k P k确 定 搜 索 步 长 k, 得 到 下 一 个 点 X k 1 ＝ X kkP k,令 k:k 1 ,转 ( 2 )。
注：不同的搜索方向，就形成了不同的算法，不
同的算法所产生的点列收敛于最优解的速度
0 0 Hg2(X)Hg3(X)0 00
计算
说 明 f(X )是 凸 函 数 ， g 1 (X ) 、 g 2 (X ) 、 g 3 (X )是 凹 函 数 因 此 ， 本 模 型 是 凸 规 划 。
2020/6/5
第二节 无约束极值问题
★一般模型：
min f ( X )
其中X Rn
★求解（f(X)可微）：应用极值条件求解，往往得到一个非线 性的方程组，求解十分困难。因此，求 解无约束问题一般 采用迭代法，称为下降类算法。
梯 度 是 过 X0点 且 与 f(X)在 X0的 切 平 面 垂 直 的 向 量 ，
梯 度 向 量 的 方 向 是 函 数 值 在 该 点 增 加 最 快 的 方 向 。
2020/6/5
★海塞阵
若f
(
X
)在X
的
0
邻
域
内
有
连续二阶偏导数，
则
称
f
(
X
)在X
0点对n
个变元两两组合的二
阶
偏
导
数
组
成
的
矩
阵
2020/6/5
第一节 基本概念
一、非线性规划问题与模型
1. 问题
⑴生产计划问题
x:产量;P(x):价格;C(x)成本
max f (x) xP(x) xC(x)
s.t.hgji
(x) (x)
0 0
2020/6/5
⑵投资决策问题
x j : 第j种股票的购买量；Pj : 第j种股票的价格
B :总资金； j : 第j种股票的每股平均收益
第三章 非线性规划
Maxz CX
请回顾线性规划:
s
.t
.
AX X
0
b
,其目标与约束函数
均为线性的。线性规划具有相对完美的理论与方法，应用 也很广泛，但它终究不能穷尽各种优化问题，因为世界是 非线性的。
非线性规划（Nonlinear Programming）研究具有非线 性构成函数的优化问题，是运筹学中相对活跃的重要研究 分支。
2020/6/5 F F1 2， 最 后 的 小 区 间 [an-1,bn1]中 的 任 意 一 点 可 作 为 t*的 近 似 值 。
例5：用 分 数 法 求 f( t) t2 t 2 在 区 间 [ 1 ,3 ] 上 的 近 似 极 小 点 ，
要 求 缩 短 后 的 区 间 长 度 不 大 于 原 区 间 长 的 8 ％ 。
为f
(
X
)在X
的海
0
赛
阵
，
记为H
(
X
0
)，即H
(
X
0
)=[
2 f (X0 xix j
)
]nn
2
f (X x12
0
)
2 f (X0 x1xn
)
M O M
2 f (X0) xnx1
L
2 f (X0)
xn2
2020/6/5
★泰勒公式
若f (X)在X0的邻域内有连续二阶偏导数，则可写出f (X)在X0点 的（二阶）泰勒展开式：
0 .5 3 8 ,
f
(t1 )
1 .7 5 1
t1'
1
8 13
[3
( 1)]
1 .4 6 2 ,
f
( t1' )
2 .6 7 5
f (t1 )
故
[ a1 , b1 ]
[ 1,1.462],
F4 F5
5 8
t2
1
(1
5 )[1 .4 6 2 8
( 1)]
0 .0 7 7 ,
2020/6/5
f (t2 ) 2 .0 8 3 f (t1 ), 故 [a 2 , b2 ] [ 0 .0 7 7 ,1 .4 6 2 ]
解由 于 f''(t)20,所 以 （ f t） 是 严 格 的 凸 函 数 。
由 f'(t)＝ 2t－ 1 ＝ 0 ， 解 得 t*1是 极 小 点 ， （ f t* ） ＝ 1.75
由
1 Fn
0.08知 Fn
1
2 12.5,查
0 .0 8
表得
n
6,
F5 F6
8 13
8
t1
1
(1
)[3 13
( 1)]
O
a t 1 t * t 2 t 1'
怎样在区间中取点最好？
2020/6/5
bt
2020/6/5
a
t1
t 1'
b
a(1 Fn1)(ba) a Fn1 (b a)
Fn
Fn
若按
Fn1 Fn
的比例在区间中对称地取点t1和t1'，经比较后去掉[t1'
,
b],
(1- Fn1 )(b - a)
则t1在[a, t1' ]中所占的比例为
f(X kP k)f(X k) f(X k)T P k1 22P kTH (X k)P k
4.凸规划
★凸函数：f(X)是定义在凸集D上且满足对任意 X1, X2 D, [0,1] 有下式成立的函数：
f(X 1 ( 1 ) X 2 ) f( X 1 ) ( 1 ) f( X 2 )
若不等式中严格不等号成立，则称f(X)为严格凸函数
注：判断一个可导函数f(X)是否是凸函数的方法 一元函数f(x) ：二阶导大于等于零; 多元函数f(X) ：海塞阵半正定。
依
此
进
行
，
得
t
＝
5
0
.5
3 8为
近
似
极
小
点
，
f
(t5
)
1 .7
5
1
2. 0.618法
★区别：每次取点得比例是定值0.168，即每次区间内两 点得位置均在区间相对长度得0.328和0.168处。
★特点：简单，更易于应用； 效果也比较好。
2020/6/5
3.近似最佳步长公式