莫 莉
5.1 无约束优化问题
一、问题的数学描述
无约束非线性规划的数学描述
min f (X ) n
X E
f ( X )为非线性函数.
解析法 用到函数的一、二 阶导数，即函数的 解析性质 只用到函数值，而 不要求函数的解析 性质
莫 莉
迭代法
直接法
水电与数字化工程学院
5.1 无约束优化问题
min
f ( x)
取 p0 f ( x 0 ) (4,100)T 2 4 2 4 0 0 x p 2 100 2 100 f ( x0 p 0 ) (2 4 )2 25(2 100 )2 d 得 0 0.020037 令 f ( x0 p0 ) 0 d 1.919878 1 0 0 所以 x x 0 p 0.003070
第二章 非线性规划(Nonlinear Programming)
主讲人：莫 莉
moli@ 2015 年 5 月
水电与数字化工程学院 莫 莉
前节回顾
温
斐波那契法 黄金分割法
故
无约束优化
知
新
下降迭代算法
最速下降法 共轭方向法 共轭梯度法
水电与数字化工程学院
f ( x * ) 0
则x*是(UP)的全局最优解。
因为 f 是R n上的可微凸函数，定理 3知 f ( x* )T ( x x*) f ( x ) f ( x * ), x R n
由于f ( x * ) 0
f ( x * ) f ( x ), x R n
x*是(UP)的全局最优解。
所以 f ( x tp) f ( x )， t (0, ) 由定义知， p是 f 在点x处的下降方向。
水电与数字化工程学院 莫 莉
5.1 无约束优化问题
定理2 设 f : R n R在点x R n 处可微，若x*是(UP)的 局部最优解，则
f ( x * ) 0
使f ( x ) 0的点x称为函数 f的的驻点。
X
*
X
(k )
X
*
(k ) (k ) 成立，就称 X 收敛的阶为α ，或 X 阶收敛。
当 2 时，称为二阶收敛，也可说 X ( k ) 具有二阶敛速。
当 1 2 时，称超线性收敛。 当 1 ，且 0 1 时，称线性收敛或一阶收敛。
定理 4 设 f : R n R ， x * R n ，f 是 R n 上得可微凸函数。若有 f ( x * ) 0 则 x * 是(UMP)的整体最优解。
水电与数字化工程学院 莫 莉
5.2 最速下降法
设目标函数f(x)一阶连续可微.
基本思想：从当前点xk出发，取函数 f(x)在点 x k处 下降最快的方向为搜索方向 pk，即负梯度方向。
)，则 a1 : a0 , b1 : t1 , t2 : t1 若f ( t 1 ) f ( t 1 Fn 2 并且令 t 2 b1 (a1 b1 ) Fn1 )，则 t1 : a1 , b1 : b0 , t 2 : t1 若f ( t1 ) f ( t1 Fn 2 a1 并且令 t 2 (b1 a1 ) Fn1 水电与数字化工程学院
2 0 0 2 f ( x) 0 8 0 0 0 2 2 f ( x )正定， f ( x )是R n上的凸函数，
x * (1， 0， 0)T 是全局最优解。
水电与数字化工程学院 莫 莉
5.1 无约束优化问题
定理 1 设 f : R n R 在点 x R n 处可微。若存在 p R n ，使 f ( x )T p 0 则向量 p 是 f 在点 x 处的下降方向。
水电与数字化工程学院
莫 莉
5.2 最速下降法
算法步骤： 第1步 选取初始点x0,给定终止误差 ε>0,令k:= 0； 第2步 计算
f ( x k ) 若 || f ( x k ) || ，停止迭代，
输出x k，否则转第3步；
第 3步 第4步 进行一维搜索，求 λk使得 f ( x k k p k ) min f ( x k p k )
(k )
f ( X ( k 1 ) ) f ( X ( k ) ) f (X
(k )
)
其中 1 , 2 , 3 , 4 , 5为事先给定的足够小的 正数.
水电与数字化工程学院 莫 莉
前节回顾
斐波那契法的思路 1. 根据相对精度或绝对精度，确定试点个数； 2. 确定两个试点的位置a1、b1（对称搜索）；
水电与数字化工程学院
莫 莉
前节回顾
温
斐波那契法 黄金分割法
故
无约束优化
知
新
下降迭代算法
最速下降法 共轭梯度法 Newton法
水电与数字化工程学院
莫 莉
第二章 非线性规划
1 2 3 4 5 6
水电与数字化工程学院
基本概念 最优性条件 凸函数和凸规划 一维搜索方法 无约束最优化方法★ 约束最优化方法
水电与数字化工程学院 莫 莉
前节回顾
算法的精度判别
1 绝对误差 X
( k 1 )
0
2 0 相对误差
1) X ( k ) X
(k )
f ( X ( k 1 ) ) f ( X ( k ) ) 2
3 4
30 f ( X )的模 f ( X ） 5
莫 莉
下降迭代算法步骤
前节回顾
确定搜索方向P (k)是关键的一步，各种算法的区 别主要在于确定搜索方向P (k)的方法不同。 步长 k 的选定一般都是以使目标函数在搜索方 向上下降最多为依据的，称为最佳步长，即沿 射线
X X (k ) P(k )
求目标函数的极小值
k : min f ( X (k ) P(k ) )
定理3 设 f : R n R在点x R n 处的Hesse矩阵 2 f ( x* )存在，
若f ( x* ) 0，且 2 f ( x * )正定
则x*是(UP)的严格局部最优解。
水电与数字化工程学院 莫 莉
5.1 无约束优化问题
定理4 设 f : Rn R，x* R n , f 是R n上的可微凸函数，若
经10轮迭代得最优解。 水电与数字化工程学院
莫 莉
5.2 最速下降法
所以令 a : t1 , t1 : t 2 t 2 0.438 0.618(1.146 0.348) 0.876
1 : 2
2 (0.876) 0.0798
(4) 因 1 2 , b t1 1.146 0.708 0.438 0.5 得最优解 ： t 2 0.876
1 令 t n 1 t n
1 (a n 2 bn 2 ) 2
莫 莉
水电与数字化工程学院
前节回顾
黄金分割法
Fn 2 t1 a 0 (b0 a0 ) Fn Fn1 a0 t1 (b0 a0 ) Fn
t1 a0 0.382 (b0 a0 ) b0 0.618 (b0 a0 )
Fn-2
a a1 Fn-1

Fn-1
b1 Fn-2 b
3. 计算函数值和并比较其大小，从而缩减搜索区间； 4. 重复2、3两步，直到得到近似最小点。
水电与数字化工程学院 莫 莉
前节回顾
斐波那契法的步骤
第1步 根据缩短率δ，计算Fn ，求出最小的n。
第2步 由前面公式求前两个测试点 t1 和 t1 ) 第3步 计算 f (t1 ) 和 f (t1
(UP)
其中 x ( x1 ,..., x n )T R n ， f : R n R
无约束问题的最优性条件
最速下降法
共轭方向法 共轭梯度法
水电与数字化工程学院 莫 莉
5.1 无约束优化问题
定理1 设 f : R n R在点x R n 处可微，若存在 p R n , 使
因 ( t1 ) ( t 2 ), t 2 a 1.854 0 0.5 所以令 b : t 2 , t 2 : t1 , t1 1.854 0.618(1.854 0) 0.708 2 : 1
1 (0.708) 0.0611
水电与数字化工程学院 莫 莉
由于确定步长是通过求以 为变量的一元函数
的极小点来实现的，故称这一过程为一维搜索。
水电与数字化工程学院 莫 莉
前节回顾
算法的收敛速度。
(k ) * 设序列 X 收敛于 X，若存在与迭代次数 k无关的数 0
和 1 使K从某个 k0 0 开始，都有
X
( k 1)
定理 2 设 f : R n R 在点 x R n 处可微。若 x * 是(UMP)的局部最 优解，则 f ( x * ) 0
定理 3 设 f : R n R 在点 x R n 处的 Hesse 矩阵 2 f ( x * ) 存在。 若 f ( x * ) 0 ，并且 2 f ( x * ) 正定 则 x * 是(UMP)的局部最优解。
前节回顾
(2) 因 1 2 , t 2 a 1.146 0.5
所以令 b : t 2 , t 2 : t1
t1 1.146 0.618(1.146 0) 0.438
2 : 1
1 (0.438) 0.2082
(3) 因 1 2 , b t1 0.708 0.5
f ( x )T p 0 则 p是 f 在点x处的下降方向。