天津大学-非线性-无约束规划.ppt

1、第 三 章,无约束非线性最优化方法,基本模型: 用符号(fs)表示非线性规划,1）方向导数 设M0位数量场u=u(M)中的一点,从点M0出发引一 条射线l,在l上点M0的附近取一动点M, 记 如果 时，下列表达式的极限存在 则称之为M0处沿着l方向的方向导数. 记为 当 时, 表示函数u沿l是增加方向, 当 时, 表示函数u沿l是减小方向。,1.方向导数与梯度,2） 直角坐标系中方向导数的计算公式 定理1. 若函数u=u(x,y,z)在点M0(x0,y0,z0)处可微; 为l的方向余弦, 则函数u在点M0处 沿l方向导数必然存在，且有下面公式计算 其中 是在M0附近的偏导数. 例题1 求函数

2、在点M(1,0,1)处沿着 方向的方向导数 解:,3)梯度：根据方向导数公式 可以知道 是其变化率最快的方向, 称为 梯度, 记为Grad u. 如果用 表示l线 上的单位矢量, 则方向导数可以写成 梯度的性质： 1) 方向导数等于梯度在该方向的投影.即 2) 数量场u=u(M)中任一点M处的梯度, 垂直于过该点 的等值面, 且指向u(M)增大的一方. 例3 设 为点M(x,y,z)的矢径 的模, 试证,2. 海瑟矩阵,海瑟矩阵是对称形式：,3 非线性规划问题的展开形式,多元函数泰勒公式的矩阵形式： 其中,线性函数：f (X) = CTX + B = ci xi + B 二次函数：f (X)

3、= (1/2) XTQX + CTX + B,f (x) = f (x*)+ f T(x)(x-x*) + (1/2)(x-x*)T 2f (x*)(x-x*) + ox-x*2,4 凸集、凸函数和凸规划,1）凸函数 定义: 设集合 S Rn 为凸集，函数 f :SR 若 x(1), x(2) S, ( 0 , 1 ) ，均有 f( x(1)(1- ) x(2) ) f(x(1)+(1- )f(x(2) ， 则称 f(x) 为凸集 S 上的凸函数。 若进一步有上面不等式以严格不等式成立，则称 f(x) 为凸集 S 上的严格凸函数。 性质: 当- f(x) 为凸函数（严格凸函数）时，则称 f(x

4、) 为凹函数（严格凹函数）。,严格凸函数,凸函数,严格凹函数,2.2 凸集、凸函数和凸规划(续),定理： f(x) 为凸集 S 上的凸函数 S 上任意有限点的凸组合的函数值不大于各点函数值的凸组合。 思考：设f1, f2是凸函数， 设1, 2 0, 1f1+2f2 , 1f1 - 2f2是否凸函数？ f(x)= max f1(x) , f2 (x) , g(x)= min f1(x) , f2 (x) 是否凸函数？,凸规划=凸可行集+凸目标函数,凸函数与凹函数(续),凸函数的判定: 如果函数f (X)的Hesse矩阵处 处半正定，则f (X)为凸函数， 若f (X)正定，则f (X) 为严格凸

5、函数。 注: 该命题的逆命题不成立 例题 检验函数 的凸性。,无约束问题的最优性条件,1. 必要条件：若X*是函数f(X)的局部最大点，则在该点必有f(X*)=0以及Hesse矩阵2f(X*)半正定 定义: 对于可微函数f(X), 称使其梯度为零向量的点为平稳点（驻点）。 2. 若X*是驻点，则其为极值点的充分条件: 1) 若H(X*)半正定，X*为局部极小点； 若H(X*)正定，X*为孤立局部极小点； 2)若H(X*)半负定，X*为局部极大点； 若H(X*)负定，X*为孤立局部极大点； 3)若H(X*)不定，X*为鞍点；(阅读课本的例题),6 最优化问题的数值解 VS 解析解,1. 解析解与

6、数值解 注意获得解析解的困难性。 2、收敛性概念： 考虑(fs)设迭代算法产生点列x(k) S. 1) 算法的理想收敛：设x*S是(fs)的最优解，如果x*x(k)，或者虽然 x(k) x*， 但是k，满足 则称算法收敛到最优解 x*。,概念: 1) 局部最优: 2) 全局最优: 3) 严格全局最优 以及 4) 全局收敛： 对任意初始点x(1), 算法均收敛。 5) 局部收敛： 当x(1) 充分接近解x*时，算法才收敛。,2. 实用收敛性： 定义解集 S* = x | x 具有某种性质 例：S*=x|x-g.opt S*=x|x-l.opt S*=x| f(x)=0 S*=x|f(x) (为给

7、定实数,称为阈值 当下列情况之一成立时，称算法收敛： 1x(k) S*; 2k，X(k)任意极限点S*,8. 收敛速度,设算法产生点列x(k), 收敛到解x*, 且x(k)x*， k， 1.线性收敛： 当k充分大时成立 2.超线性收敛： 3.二阶(次)收敛： 0，当k充分大时有,定理：设算法点列x(k)超线性收敛于x*, 且x(k)x*， k，那么 证明只需注意 | |x(k+1) x* | -| x(k) x* | | |x(k+1) x(k) | |x(k+1) x* | +| x(k) x* | ，除以| x(k) x* | 并令k，利用超线性收敛定义可得结果。,8、收敛速度（续）,4.

8、1 常用的搜索算法结构,考虑（fs） 常用一种线性搜索的方式构造xk序列来求解 迭代中从一点出发沿下降可行方向找一个新的、更优的点。 下降方向 ： 设 S，d Rn,d0,若存在 ，使 ，称d 为 在 点的下降方向。,4 常用的搜索算法结构,可行方向： 设 S，dRn, d0, 若存在 使 ， 称d 为该点的可行方向。 同时满足上述两个性质的方向称 下降可行方向。,迭代算法的停止标准,1） 2） 3） 对于无约束问题可以用,10 常用的搜索算法结构,线性搜索求 ， 新点 使x(k+1)S,yes,no,11 一维搜索,一元函数求极小及线性搜索均为一维搜索。常用于求： min f(x(k)+ d

9、(k)=( ) s.t. S S有3种情况（-，+）或（0， + ）或a,b 一、缩小区间的精确一维搜索：考虑问题(P) min ( ) s.t. , 为此先介绍不确定区间及单峰函数的概念 不确定区间：, 含()的最小点， 但不知其位置,单峰的概念,一、缩小区间的精确一维搜索（续） 若对任意1 ,2, 1 ( 2); 2 若 1 * ，则( 1) ( 2). 则称( )在, 上强单峰。 若只有当( 1) ( * )， ( 2) ( * )时，上述1, 2 式才成立，则称( )在, 上单峰。,设f(X)是目标函数，如果 是在给定Xk和方向 矢量Pk下，通过f(x)=f(xk+akPk) 的极小化

10、而产生 则称 为最优步长。 根据单变量的驻点条件: 以及复合函数的求导法则可得：,1. 精确一维搜索（假定求目标函数极小值）,2 一维搜索,一、缩小区间的精确一维搜索（续） 定理： 设：RR 在， 上单峰，x1 x2 。 那么 1若(x1) (x2)，则去除 ， x2 ；如左下图 2若(x1)(x2)， 则 去除x2，；如右下图,12 一维搜索,2、黄金分割法（0.618 法） 选二点x1x2 ,比较f(x1) 与f(x2), 可去掉a, x1或者x2 ,b 考虑下面分割条件： 1对称： x1 - a = b -x2 （使“坏”的情况去掉，区间长度不小于“好”的情况） 2保持缩减比 =(保留的

11、区间长度原区间长度) 不变。 （使每次保留下来的节点， 在下一次的比较中成为一个相应比例位置的节点 )。如图所示, 推导缩减比 ,黄金分割法的步骤: 1) 确定初始区间为a,b, 初始区间的长度L=b-a, 容差 0, k=1 2) 计算初始分割点，x1=a+0.382L, f1=f(x1); x2=a+0.618L, f2=f(x2) 3) 消去大端值，计算新的分割点： 若f1f2, 置 a=x1, x1=x2, b=b, f1=f2, x2=a+b-x1, f2=f(x2) 若f1lg /log 0.618 例题 用黄金分割法求解 min f(x)=x2-6x+10,牛顿-拉夫逊法(牛顿切

12、线法) 为了找到导数函数对应的驻点，采用根近似 假设xk是当前驻点的近似解，则该点的f(x)函数线性近似可以表示为 f(x)f(xk)+f”(xk)(x-xk) 令此式为零，得出下一个近似点为 xk+1=xk-f(xk)/f”(xk) 收敛检查： 例题: 用牛顿切线法求解 min f(x)=2x2+16/x,2、二次插值法： 用设f(x)是区间a,b上的连续单峰函数，x1, x2, x3 是该区间上三个相邻点，它们的函数值分别为f1, f2, f3, 且满足两边大中间小的条件， f1 f2 f3, 求系数 ao, a1, a2, 使得二次函数 q(x)=a0+a1(x-x1)+a2(x-x1)

13、(x-x2) 在这三点上与f(x)的函数值相等, 可得到所有的系数。 由dq/dx=0 可得 例题 用二次插值法求解min f(x)=2x2+16/x， 在区间1, 1.5内的最小值。,3-3 多维梯度法,( f ) min f(x) s.t. f : RnR ( f 连续可微) 取极值的必要条件： 若x*l.opt. f(x*)=0 (驻点 ) 说明： f (x) f(x*)+ Tf(x*)(x-x*), x. 故 f (x*) f(x )， x. (由于Tf(x*) =0 ) 1. 最速下降法 方向：在迭代点 x(k) 取方向 d(k)= f(x(k) ) 步长: 精确一维搜索,最速下降法

14、（续） 特点： 1) 全局收敛, 线性收敛; 2) 缺点: 易产生扭摆现象而造成早停 (当x(k)距最优点较远时,速度快, 而接近最优点时,速度下降) 原因 1： f(x)=f(x(k)+Tf(x(k)(x-x(k) + o|x-x(k)| 当 x(k)接近 l.opt.时 f(x(k) )0，于是高阶项 o|x-x(k)|的影响可能超过Tf(x(k)(x-x(k) 。 原因 2：,最速下降法的流程,例题3-9 用最速下降法求解:,3 Newton法及其修正 一、 Newton法： 设f(x)二阶可微，取f(x)在x(k)点附近的二阶Taylor近似函数： qk(x)=f(x(k)+Tf(x(

15、k)(x-x(k) + (x-x(k)T2f(x(k)(x-x(k) 求驻点： qk(x)=f(x(k)+2f(x(k)(x-x(k)=0 当2f(x(k)正定时，令上述方程解为x(k+1), 有极小点： Newton迭代公式: x(k+1)=x(k)-2f(x(k) -1f(x(k) 停止条件: |f(x(k)|,Newton法的计算流程,例题 3-11 用Newton法计算,Pk+1=-2f(x(k) -1f(x(k),特点： 1) 二阶收敛，局部收敛。 （当x(k)充分接近x*时, 局部函数可用正定二次函数很好地近似，故收敛很快） 2) 当f(x)为正定二次函数时，从任意初始点可一步迭代

16、达到最优解 说明: 设f(x)= xTQx+PTx+r , Qnn对称正定, P Rn, r R. x(1), f(x(1)=Q x(1) +P 2f(x(1)=Q 迭代： x(2) = x(1) - Q 1(Qx(1) +P) = - Q 1 P (驻点即opt.) 主要缺点： (1)局部收敛 (2)用到二阶Hesse阵，且要求正定 (3)需计算Hesse阵逆或解n阶线性方程组，计算量大,Newton法：（续）,6、 Newton法的改进（续）-自己阅读和体会 (1)为减小工作量，取m（正整数），使每m次迭代使用同一个Hesse阵，迭代公式变为： x(km+j+1)=x(km+j)-2f(x

17、(km)-1 f(x(km+j) j=0,1,2, ,m-1 , k=0,1,2, 特点：收敛速度随m的增大而下降 m=1时即Newton法， m 即线性收敛。 (2)带线性搜索的Newton法： 在Newton迭代中，取d(k)= -2f(x(k) -1 f(x(k) , 加入线性搜索：min f(x(k)+k d(k) 求得k , x(k+1)=x(k)+kd(k) 特点：可改善局部收敛性，当d(k)为函数上升方向时，可向负方向搜索，但可能出现 d(k)均非下降方向的情况。,二、算法流程图,6 共轭梯度法,共轭的概念: 对于方向pi, pj相对于nn对称正定矩阵Q共轭，则 基本公式: 停止

18、条件:,共轭梯度法算法特点,1、全局收敛（下降算法）；线性收敛； 2、每步迭代只需存储若干向量(适用于大规模问题)； 3、有二次终结性（对于正定二次函数，至多n次迭代 可达opt.） 例题 3-10 用共轭梯度法求解,目标函数 (f)min f(x), f: R n R 1、基本思想： 用对称正定矩阵H(k)近似2f(x(k)的逆 , 而H(k)的产生从给定H(1)开始逐步修整得到。 2、算法框图：,5 变尺度法,5、变尺度法的主要特点： 只需用到函数一阶梯度 (Newton法用到二阶Hesse阵） 下降算法，故全局收敛； 不需求矩阵逆；（计算量小） 一般可达到超线性收敛；（速度快） 有二次终

19、结性。 二 DFP (Davidon(1959),Fletcher and Powell (1963) ) 法: 1、DFP法：以下省去各量上标，x, s, y, H 表示第k 步的量， 等表示第k+1步的量。,二、1、DFP法： （续） Ex. 用DFP法求解 min f(X)= 10 x12+x22 解：取初始点x(1)=(110,1)T, H(1)=I (单位矩阵) 得到如下结果： （计算过程见下页）,2、BFGS法 BFGS ( Broyden(1970), Fletcher (1970), Goldfarb (1970), Schanno(1970) ) 法 主要公式：,BFGS法有变尺度法的全部优点，并且在一定条件下可以证明在BFGS法中使用前文中介绍的不精确一维搜索有全局收敛性。,3.4. 多维直接算法