CANFile无约束优化基础

数学基础直线、射线(顶点和方向)：给定直线：射线：线段：1多元函数(等直线、梯度、海森矩阵)Rosenbrock“香蕉”函数2多元函数沿直线的斜率和曲率f沿直线的一阶导数和二阶导数斜率(slope)曲率(curvature)Rosenbrock“香蕉”函数3线性函数和二次函数G是对称矩阵b是常向量c是常数其中记割线方程！4Taylor展式Peano型余项：Lagrange型余项：积分型余项：5f(x)的Taylor展式:的Taylor展式:6第05章：无约束优化：基础

Fundamentals

ofUnconstrainedOptimization7无约束优化在设计和分析算法时，通常假设f(x)是连续可微(二阶连续可微)的，且导数是李普希兹连续的！8局部极小点的条件算法概述非精确线搜索9局部极小点的条件10局部极小点、全局极小点；非光滑的极小点极小点的类型11局部极小点的必要条件设x*是f(x)的局部极小点。令考查则在有零斜率和非负曲率！故必要条件即对所有p，有(一阶条件)，G*半正定(二阶条件)等价地稳定点/驻点(stationarypoint)：使得g(x*)=0的x*12局部极小点的充分条件例.考虑Rosenbrock函数在x*=(1,1)处严格局部极小点－全局极小点充分非必要：定理.x*是严格局部极小点的充分条件是，G*正定.13局部极小点的充分条件(续)如何判断矩阵的正定性：G*的所有特征值大于零；G*的所有顺序主子式大于零；G*的Cholesky分解LLT存在，其中L是下三角矩阵；且lii>0G*的LDLT分解存在，其中L是单位下三角矩阵；D是对角矩阵，且di>0;14稳定点的类型15凸函数的定义定义命题.若fi(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非精确线搜索－充分减少和回溯确定非精确线搜索步长的实用方法之一

Procedure4.1Backtracking-ArmijoLinesearch牛顿法和拟牛顿法中：最速下降法或共轭梯度法中可取不同初始步长值！参数的典型值：32非精确线搜索－充分减少和回溯(续)推论在上述定理条件下,回溯Armijo线搜索确定的步长定理.

对于由回溯Armijo线搜索确定步长的线搜索法而言，则或者对某k

有g(k)=0，或者，或者定理设g(x)是Lipschitz连续的(常数是L).此外，p(k)是x(k)处