无约束非线性规划
第一节 最优性条件 第二节 一维搜索
第三节 最速下降法和共轭梯度法
第四节 牛顿法和拟牛顿法(变尺度法)
第五节 信赖域法
#
引言
本章讨论如下的优化模型
min f ( x) n
xR
其中
f
是
二阶连续偏导数。
x
的实值连续函数，通常假定具有
#
预备知识
#
预备知识
#
预备知识
#
最优性条件
#
#
一维搜索——黄金分割法
a
x1
x2
b
如上图所示， [a, b]为搜索区间，黄金分割法首先根据黄金比例 产生两个内点x1 , x2 x1 a 0.382(b a ) x2 a 0.618(b a ) 然后根据f ( x1 ), f ( x2 )的大小来重新选择搜索区间。
(1).若f ( x1 ) f ( x2 ), 则搜索区间变为[x1 , b]; (2).若f ( x1 ) f ( x2 ), 则搜索区间变为[a, x2 ].
例2 借助计算器或计算机用二分法求方程 2x+3x=7 的近似解(精确到0.1).
#
一维搜索——二分法
那么我们一起来总结一下二分法的解题步骤
给定精确度
，用二分法求函数f(x)零点近似解的步骤如下：
x1；
⑴确定区间[a,b],验证 f (a) f (b) 0 ,给定精确度
⑵求区间(a,b)的中点 ⑶计算f( x1)；
f ( x
来终止迭代，其中
(k )
)
0 是给定的精度要求。
#
一维搜索
#
一维搜索——二分法
对于区间[a,b]上连续不断、且f(a)f(b)<0 的函数y=f(x),通过不断地把函数f(x)的零点 所在的区间一分为二，使区间的两个端点 逐步逼近零点，进而得到零点近似值的方 法叫做二分法（bisection）
② 否则，当f (k ) f (k )时转步 ③ 当f (k ) f (k )时转步 ④
#
一维搜索——黄金分割法
ak 1 k b b ③ k 1 k k 1 k k 1 ak 1 0.618(bk 1 ak 1 )
初始点的选取依赖于方法的收敛性ቤተ መጻሕፍቲ ባይዱ。一个算法 称为收敛的，如果算法产生的序列{ x ( k ) }满足
k
lim x ( k ) x 0
其中x 是最优化问题的最优点。一个算法如果对于任意 给定的初始点都能够收敛，就说这个算法全局收敛或整体 收敛。有些算法只有当初始点接近或充分接近最优解时才 有收敛性，称这样的算法为局部收敛的方法。
#
最优性条件
迭代算法的步骤 第一步：给定最优解的一个初始估计，选择初始点x (0)，置k 0； 第二步：如果x ( k )满足最优解估计的终止条件，停止迭代； 第三步：确定下降方向d ( k ) , 使得目标函数f ( x )从x ( k )出发，沿 d ( k )方向，在射线x ( k ) d ( k ) ( 0)上选取步长k，使得 f(x ( k ) k d ( k ) )<f ( x ( k ) ) 则令x ( k 1) x ( k ) k d ( k ) . 第四步：得到最优解的一个更好的估计x ( k 1) x ( k ) k d ( k )，置 k k 1后转步2.
x ( k 1) x (k ) k d (k ) 其中k 称为步长，d ( k )称为搜索方向。通过迭代方式得到点列{x (k ) }使得 f ( x (0) ) f ( x (1) ) ... f ( x (k ) ) ...
#
迭代法
若产生的点列{ x ( k ) }逼近我们要求的极小点x , 则称 这个序列{ x ( k ) }为极小化序列。满足所对应的函数值 f ( x ( k ) )是逐次减小的算法称为下降算法。
⑤ 令k k 1, 转
；
①若f( x1)=0，则 x1 就是函数的零点； ③若 f ( x1 ) f (b) 0 ，则令a=
②若 f (a) f ( x1 ) 0，则令b= x ( 此时零点 x0 (a, x1 ) )； 1
⑷判断是否达到精确度 ：即若|a-b|< 为a(或b);否则重复⑵~⑷

x1 (此时零点 x0 ( x1, b))；
,则得到零点近似值
#
一维搜索——黄金分割法
黄金分割法也叫0.618法，它是基于一种区间 收缩的极小点搜索算法，当确定搜索区间 [a,b]后，我们只知道极小点包含于搜索区间 内，但是具体是哪个点，无法得知。 1.算法原理
黄金分割法的思想很直接，既然极小点包含 于搜索区间内，那么可以不断的缩小搜索区 间，就可以使搜索区间的端点逼近到极小点 。
#
迭代算法
在大多数的算法中，k的选取是使f ( x)下降得最多，即沿射线 x ( k ) d ( k )求f ( x )的极小值，这是单变量的函数求极小点的问题， 称为一维搜索，也称为线搜索。
迭代的终止条件在不同的最优化方法中也是不同的。 理论上，根据最优性的一阶必要条件，以及算法的设 计思想，可以用
#
一维搜索——黄金分割法
2.算法步骤
用黄金分割法求无约束问题 min f ( x )的基本算法步骤如下
xR
选定初始区间[a1 , b1 ]及精度 0，计算试探点:
① 1 a1 0.382(b1 a1 )
1 a1 0.618(b1 a1 )
令 k 1
若bk ak , 则停止计算.
最优性条件
定理的逆不成立，即梯度为零的点不一定是局部解。 #
最优性条件
#
迭代法
求解无约束优化问题的常用方法是数值解法，而数值
解法中最为常见的是迭代法。
迭代法思想：
首先给出f ( x )的极小点一个初始估计x (0) , 通过某种方式产生 一个使目标函数值减小的方向d (0) , 确定一个实数0 , 从而可以确 定新的迭代点x (1) x (0) 0d (0)，这样下去我们由x (1)、d (1)、1可以 确定x (2)，...x ( k ) ......