CAN-File-15-04-16-07-emp_uco_fundemeantal_2015_spr

第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础数学基础局部极小点的条件算法概述非精确线搜索第四章无约束优化：基础第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础844211/28161632321-11多元函数(等高线/等值线、梯度、Hessian阵)Rosenbrock的山谷/香蕉函数(1961),,数学基础第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础直线、射线(顶点和方向)线段：direction1x2x1212'x'xpp直线：射线：第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础多元函数沿直线的斜率和曲率Rosenbrock“香蕉”函数：斜率(slope)曲率(curvature)第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础割线方程！线性函数和二次函数记，则二次函数满足其中满足(有稳定点的)二次函数可表示为其中G是对称矩阵；b是常向量；c是常数第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础一元函数与多元函数的Taylor展式Peano型余项Lagrange型余项一阶Taylor展式：其中其中令，得多元函数的一阶Taylor展式第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础二阶Taylor展式：其中其中令，得多元函数的二阶Taylor展式向量值函数的一阶Taylor展式(习题1.6)－－写出每个分量函数的一阶Taylor展式，然后用向量来表示即可.第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础局部极小点、全局极小点；非光滑的极小点极小点的类型光滑函数的局部极小点的刻画(若函数可微，能利用Taylor展式！)xfLocalminimaGlobalminimumxfNon-smoothminimum凸(碗状)函数的局部极小点也是全局极小点第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础无约束优化：基础FundamentalsofUnconstrainedOptimization第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础无约束优化在设计和分析算法时，通常假设是连续可微(二阶连续可微)的，且导数是李普希兹连续的！常用记号：第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础稳定点/驻点(stationarypoint)：使得g(x*)=0的.局部极小点的必要条件设是的局部极小点。令它在有零斜率和非负曲率！考查故必要条件即对所有p，有():(())fx0(一阶条件)，半正定(二阶条件)等价地第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础局部极小点的充分条件严格局部极小点－全局极小点充分非必要!定理是严格局部极小点的充分条件是，正定.例考虑Rosenbrock函数在处f(x)=x2,第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础局部极小点的充分条件(续)如何判断矩阵的正定性：(i)的所有特征值大于零；(ii)的所有顺序主子式大于零；(iii)的Cholesky分解LLT存在，其中L是下三角矩阵，且lii0；(iv)的LDLT分解存在，其中L是单位下三角矩阵；D是对角矩阵，且di0;第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础稳定点的类型(*,*)fx(*,*)fx(*,*)fx1x2x*x*x1x2x第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础凸函数的定义命题若fi(x),i=1,…,m,是凸集C上的凸函数，则它们的非负线性组合仍然是C上的凸函数.相关定义：严格凸函数、凹函数/严格凹函数Jensen不等式：见习题4.6定理凸函数在凸集上的局部极小点是全局极小点.*****以下设是定义在凸集上的连续函数定义对任意应有其中1x0x1f0f()fxfx01(1)ff(应用：概率论中的Jensen不等式)第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础可微凸函数的判别推论可微凸函数的稳定点是全局极小点1x0x1f0f()fx000()ffTxx定理设f是凸集C上的可微实值函数，f凸当且仅当对所有的，有定理设f是开凸集C上的二次连续可微实值函数，则f凸当且仅当对C中的每个x而言，是半正定的.第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础典型的凸函数既凸又凹！q(x)凸当且仅当G半正定任一范数！其中G是对称矩阵；b是常向量；c是常数第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础算法概述－收敛与收敛速度实用算法应具备的典型特征：稳定地接近局部极小点x*，然后迅速地收敛于x*⊙{x(k)}的聚点是局部极小点或者g(k)趋于零⊙除个别情况外，每次迭代后目标值减小开发优化方法还有赖于实验!求解各种有代表性的测试函数！a0－线性收敛、a=0－超线性收敛收敛速度二次收敛/二阶收敛收敛性收敛()||*||kkexx，，第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础算法概述－实用的终止准则●理想的终止准则：－－不现实！●实用准则：适用于牛顿法和拟牛顿法通常需要联合使用好几种终止准则！或适合于共轭梯度法、最速下降法其中H(k)是G(k)的逆或者近似.第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础(b)一般函数在局部极小点x*附近可用二次函数近似；即使远离极小点，应用二次信息也要比简单地放弃这些信息好算法概述－二次模型其中B(k)是G(k)的估计/近似(a)最简单的具有唯一极小点的光滑函数(海森矩阵正定)使用二次模型函数的好处(c)许多算法具有二次终止性，即将算法应用于二次函数时，算法迭代有限次后终止第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础线搜索法给定初始估计x(0)，设x(k)处有g(k)≠0，则第k次迭代：(a)根据某种模型函数确定x(k)处的搜索方向p(k),(b)线搜索：求解关于的极小化问题得到步长(a)置.◆确定步长：精确线搜索、非精确线搜索有许多种不同的确定方向的方法！(第5章)最速下降法和牛顿法！共轭梯度法和拟牛顿法◆搜索方向必需是下降方向，即第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础精确线搜索基本性质：即新迭代点处的梯度与搜索方向是正交的！仅对(严格凸)二次函数有解析表达式()kp(1)kgcontouroff(1)kx()kx第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础非精确线搜索－动机朴素线搜索及其失败(1)(1)(,)xf(3)(3)(,)xf(4)(4)(,)xf(2)(2)(,)xf()yfxx0012112(5)(5)(,)xf23(1)(1)(,)xf(3)(3)(,)xf(4)(4)(,)xf(2)(2)(,)xfx0012112(5)(5)(,)xf23()yfx尽可能地避开区间两个端点附近的点令第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础非精确线搜索－Armijo法则-线：0ebc)(kf()()():()kkfxp-line(0)'(0)(0)'(0)尽可能地避开区间两个端点附近的点令，其中是参数.Armijo条件目的：保证步长不太大其中[0,c]第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础非精确线搜索－Armijo法则与Goldstein测验Armijo法则(Armijorule)，其中是参数.其中是参数.:0509..参数的典型取值：Armijo条件，其中是参数.Goldstein测验(Goldsteintest)Goldstein(1965)测验的缺点：第二个条件有可能使得精确极小点位于可接受区间的左侧！第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础非精确线搜索－回溯Armijo线搜索牛顿法和拟牛顿法中：最速下降法或共轭梯度法中初始步长可取不同的值！确定非精确线搜索步长的实用方法之一定理考虑基于Armijo法则确定步长的线搜索法，若f下方有界，且g(x)在水平集上Lipschitz连续，则初始步长第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础非精确线搜索－Wolfe条件和强Wolfe条件Wolfe条件不足：不能退化成精确线搜索！相当精确的线搜索－共轭梯度法弱的线搜索－牛顿法或拟牛顿法强Wolfe准则其中是参数.，其中是参数.，其中是参数.其中是参数.参数的典型值：第4章无约束优化：基础LHY-SMSS-BUAA数学规划基础非精确线搜索－下降法与稳定性定理假设f连续可微，p(k)是x(k)处的下降方向，且f沿着射线有下界.如果参数满足，则满足Wolfe条件和强Wolfe条件的可接受区间存在.定义与之间的夹角是其中夹角条件：存在与k无关的数，使得定理对于步长满足Wolfe条件或强Wolfe条件，且搜索方向满足夹角条件的线搜索法，如果g(x)是Lipschtiz连续的.则或对某k有g(k)=0，或，或