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