CANFile无约束优化基础

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,数学与系统科学学院,第,05,章 无约束优化：基础,实用优化方法,数学基础,直线、射线,(,顶点和方向,),：,给定,直线：,射线：,线段：,1,多元函数,(,等直线、梯度、海森矩阵,),Rosenbrock“,香蕉”函数,2,多元函数沿直线的斜率和曲率,f,沿直线 的一阶导数和二阶导数,斜率,(slope),曲率,(curvature),Rosenbrock“,香蕉”函数,3,线性函数和二次函数,G,是对称矩阵,b,是常向量,c,是常数,其中,记,割线方程！,4,Taylor,展式,Peano,型余项：,Lagrange,型余项,：,积分,型余项,：,5,f,(x),的,Taylor,展式,:,的,Taylor,展式,:,6,第,05,章：无约束优化：基础,Fundamentals,of Unconstrained Optimization,7,无约束优化,在设计和分析算法时，通常假设,f,(x),是连续可微,(,二阶连续可微,),的，且导数是李普希兹连续的！,8,局部极小点的条件,算法概述,非精确线搜索,9,局部极小点的条件,10,局部极小点、全局极小点；非光滑的极小点,极小点的类型,11,局部极小点的必要条件,设,x,*,是,f,(x),的局部极小点。令,考查,则在 有零斜率和非负曲率！,故必要条件即对所有,p,，有,(,一阶条件,),，,G*,半正定,(,二阶条件,),等价地,稳定点,/,驻点,(stationary point),：,使得,g(x,*,),=0,的,x*,12,局部极小点的充分条件,例,.,考虑,Rosenbrock,函数,在,x*=(1, 1),处,严格局部极小点全局极小点,充分非必要：,定理,. x*,是严格局部极小点的充分条件是,，,G*,正定,.,13,局部极小点的充分条件,(,续,),如何判断矩阵的正定性：,G,*,的所有特征值大于零；,G*,的所有,顺序主子式,大于零；,G*,的,Cholesky,分解,LL,T,存在，其中,L,是下三角矩阵；且,l,ii,0,G*,的,LDL,T,分解存在，其中,L,是单位下三角矩阵；,D,是对角矩阵，且,d,i, 0;,14,稳定点的类型,15,凸函数的定义,定义,命题,.,若,f,i,(x),i,=1,m,是凸集,K,上的凸函数，则它们的非负线性组合仍然是,K,上的凸函数,.,相关定义,：严格凸函数、凹函数,/,严格凹函数,16,可微凸函数的判别,定理,.,设,f,是凸集,K,上的可微实值函数，,f,凸,当且仅当,对所有的 ，有,定理,.,设,f,是开凸集,K,上的二次连续可微实值函数，则,f,凸,当且仅当,对,K,中的每个,x,而言， 是半正定的,.,17,典型的凸函数,G,是对称矩阵, b,是常向量,c,是常数,既凸又凹！,凸当且仅当,G,半正定,任一范数！,18,局部极小的条件充分条件,(,续,),定理,.,可微凸函数的稳定点是全局极小点,19,二次函数的性质, G,半正定,非奇异：即,G,正定，有惟一的全局解；,奇 异：,b,在,G,的值域中有多个全局解；,b,不在,G,的值域中函数值可任意大，也可任意小；, G,不定,函数值可任意大，也可任意小；,非奇异：有惟一的稳定点；是鞍点；,奇 异：,b,在,G,的值域中有多个鞍点；,b,不在,G,的值域中没有鞍点,.,20,算法概述,21,算法概述收敛性与收敛速率,实用算法应具备的典型特征：,稳定地接近局部极小点,x*,，然后迅速地收敛于,x*,全局,收敛性结论,x,(,k,),的聚点是局部极小点或者,g,(,k,),趋于零,除个别情况外，每次迭代后目标值减小,a, 0,线性收敛、,a,= 0,超线性收敛,局部,收敛性结论,收敛,二次收敛、二阶收敛,开发优化方法还有赖于,实验,!,求解各种有代表性的,测试函数,！,22,算法概述二次模型,其中,B,(,k,),是,G,(,k,),的估计；,拟牛顿法,或者,修正牛顿,法,牛顿法,！,最速下降法,(a),最简单的具有唯一极小点的光滑函数,(,海森矩阵正定,),(b),一般函数在局部极小点,x*,附近可用二次函数近似；,(c),即使远离极小点，应用二次信息也要比简单地放弃这些信息好,(d),以二次模型为基础的方法,通常,具有,不变性,二次终止性,：当用算法极小化二次函数时，算法有限步终止,23,算法概述线搜索法与信赖域法,给定初始估计,x,(0),，设,x,(,k,),处有,g,(,k,),0,，则第,k,次迭代：,根据某种模型函数确定,x,(,k,),处的搜索方向,p,(,k,),线搜索：确定 来极小化,置,确定步长：精确线搜索、非精确线搜索,搜索方向必需是下降方向：,有许多种不同的确定方向的方法！,(,第,6,，,8,章,),24,精确线搜索,基本性质：,新迭代点处的梯度与搜索方向是,正交,的！,仅对二次函数，精确步长有解析表达式,25,算法概述实用的终止准则,最理想的终止准则：不现实！,实用准则,H,(,k,),是,G,(,k,),的逆或者近似,适合于,共轭梯度法、最速下降法,适合于,牛顿法和拟牛顿法,通常需要,联合使用,好几种终止准则！,26,非精确线搜索下降法与稳定性,尽可能地避开区间 的端点,朴素线搜索的失败,27,非精确线搜索下降法与稳定性,(,续,),实用非精确线搜索步长准则：,Goldstein(1965),准则,Goldstein,准则的缺点,：第二个条件有可能使得精确极小点位于可接受区间的左侧！,28,非精确线搜索下降法与稳定性,(,续,),实用非精确线搜索步长准则,(,续,),：,Wolfe,准则,不足：,不能退化成精确线搜索！,参数的典型值：,相当精确的线搜索共轭梯度法,弱的线搜索牛顿法或拟牛顿法,强,Wolfe,准则,29,非精确线搜索下降法与稳定性,(,续,),定义,之间的夹角,其中,夹角条件,：,定理,.,假设,g(x),是,Lipschtiz,连续的,.,对于步长满足,Goldstein,准则、且搜索方向满足夹角条件的线搜索法而言，则或者对某,k,有,g,(,k,),=0,，或者 ，或者,30,定理,.,假设,g(x),是,Lipschtiz,连续的,.,对于步长满足,Wolfe,准则或者强,Wolfe,准则、且搜索方向满足夹角条件的线搜索法而言，则或者对某,k,有,g,(,k,),=0,，或者 ，或者,非精确线搜索下降法与稳定性,(,续,),定理,假设,f,连续可微，,p,(k),是,x,(k),处的下降方向，且假定,f,沿着射线 有下界。则存在由步长组成的区间满足,Wolfe,准则和强,Wolfe,准则。,31,非精确线搜索充分减少和回溯,确定非精确线搜索步长的,实用,方法之一,Procedure 4.1 Backtracking-Armijo Linesearch,牛顿法和拟牛顿法中：,最速下降法或共轭梯度法中可取不同初始步长值！,参数的典型值：,32,非精确线搜索充分减少和回溯,(,续,),推论,在上述定理条件下,回溯,Armijo,线搜索确定的步长,定理,.,对于由回溯,Armijo,线搜索确定步长的线搜索法而言，则或者对某,k,有,g,(,k,),=0,，或者 ，或者,定理,设,g(x),是,Lipschitz,连续的,(,常数是,L,).,此外，,p,(k),是,x,(k),处,的下降方向。则区间 内的值,均,满足,Armijo,条件，其中,33,算法概述线搜索法与信赖域法,(,续,),给定初始估计,x,(0),，设,x,(,k,),处有,g,(,k,),0,，则第,k,次迭代：,信赖域：,信赖域子问题：,利用,x,(,k,),和,k,构造子问题,解信赖域子问题，得,s,(,k,),.,计算,34,