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