第三章 无约束最优化方法

第三章 无约束最优化的梯度方法1.最速下降法假定我们已经迭代了k 次，获得了第k 个迭代点k x 。

从k x 出发，显然应沿下降方向进行，由于负梯度方向是最速下降方向，因此沿负梯度方向应该是有利的。

因此，取搜索方向)(k k x f p -∇=。

)(1k k k k x f t x x ∇-=+此时有：0)()(1=∇∇+k T k x f x f如将该方法应用于二次函数c x b Qx x x f T T ++=21)(，则可求出k t 的显式表达式。

)()()())(()(1k k k k k k k k k k x f Q t x f x f Q t b Qx b x f t x Q b Qx x f ∇-∇=∇-+=+∇-=+=∇+0)()()()(=∇∇-∇∇k T k k k T k x f Q x f t x f x fkTk kTk k T k k T k k Qg g g g x f Q x f x f x f t =∇∇∇∇=)()()()( 2.Newton 法适用条件：如果目标函数)(x f 在n R 上具有连续的二阶偏导数，其Hesse 矩阵)(x G 正定。

基本想法：考虑从k x 到1+k x 的迭代过程。

在k x 点处用二次函数来逼近)(x f ，即：))(()(21)()()()()(k k T k k T k k x x x G x x x x x g x f x Q x f --+-+=≈0)())(()(=+-=∇k k k x g x x x G x Q)()(11k k k k x g x G x x x -+-==3.共轭方向法与共轭梯度法 1) 共轭方向法定义1:设Q 是n n ⨯对称正定矩阵。

若n 维空间中非零向量系110,...,,-m p p p 满足0=j T i Qp p ，)(1,...,2,1,j i m j i ≠-= ,则称110,...,,-m p p p 是Q 共轭的，或称110,...,,-m p p p 的方向是Q 共轭方向。

第三章⽆约束最优化⽅法3第⼋节坐标轮换法把⼀个多维问题转化为⼀系列较少维数的问题称为降维。

降维⽅法有⼏种，坐标轮换法是⽤得较多的⼀种，这是⼀种不需要求函数导数的直接探索⽬标函数最优解的⽅法。

直接法、降维法⼀、坐标轮换法的基本思想其基本思想就是通过每次仅对多元函数的⼀个变量沿其坐标轴进⾏⼀维探索，其余各变量均固定不动，并依次轮换进⾏⼀维探索的坐标轴，完成第⼀轮探索后再重新进⾏第⼆轮探索，直到找到⽬标函数在全域上的最⼩点为⽌，以达到将⼀个多维的⽆约束最优化问题，转化为⼀系列的⼀维问题来求解的⽬的。

为简明起见，现以⼆元函数来说明基本步骤： 1.从初始点(0)(0)(0)(0)12(,,)n Xx x x =出发，依次沿各坐标轴⽅向搜索最优点，保持其余n-1个变量不变。

例：如果(0)(0)(0)(0)(0)123(,,,)(3,5,23,21)n Xx x x x ==，如果沿x 1轴⽅向搜索，则搜索过后改变的仅仅是x 1的值3，其余坐标的值均保持不变。

假设搜索到的值是8，则下⼀个点的值为(1)(1)(0)(0)(0)1123(,,,)(8,5,23,21)n X x x x x ==。

迭代点的序列为：(0)(1)(0)(0)(0)(0)0123(,,,)n X X x x x x →=(1)(1)(0)(0)(0)1123(,,,)n X x x x x = (1)(1)(1)(0)(0)2123(,,,)n X x x x x =(1)(1)(1)(1)(0)3123(,,,)n X x x x x =(1)(1)(1)(1)(1)(1)(2)1230(,,,)n n X x x x x X X =→→上标表⽰搜索的轮次，下标表⽰对应的坐标，亦即该轮次的第⼏次迭代。

经过⼀轮（n 次）迭代后，得到⼀个新点，然后进⾏下⼀轮迭代。

只到满⾜精度。

⼆、步长()k i α可以有以下⼏种取法1.随机选择()k iα值的⽅法2. 加速步长法为⽅向的初始试验了加快探索过程，可以采⽤加速步长法。

第三章无约束最优化方法第三章无约束最优化方法本章内容及教学安排第一节概述第二节迭代终止原则第三节常用的一维搜索方法第四节梯度法第五节牛顿法第六节共轭方向法第七节变尺度法第八节坐标轮换法第九节鲍威尔方法第一节概述优化问题可分为无约束优化问题有约束优化问题无约束最优化问题求解基于古典极值理论的一种数值迭代方法，主要用来求解非线性规划问题迭代法的基本思想：所以迭代法要解决三个问题 1、如何选择搜索方向 2、如何确定步长3、如何确定最优点（终止迭代） 第二节 迭代终止准则 1）1K K X X ε+-≤111/221K K K Kn i i i X X X X ε++=⎡⎤-=-≤⎢⎥⎣⎦∑（）2）11()()()()()K K K K K f X f X f X f X or f X εε++-≤-≤3）(1)()K f X ε+∇≤第三节 常用的一维搜索方法本节主要解决的是如何确定最优步长的问题。

从初始点(0)X 出发,以一定的步长沿某一个方向，可以找到一个新的迭代点，其公式如下：(1)(0)00(2)(1)11(1)()K K k kX X S X X S X X S ααα+=+=+=+现在假设K S 已经确定，需要确定的是步长k α，就把求多维目标函数的极小值这个多维算过程中，当起步点和方向问题,变成求一个变量即步长的最优值的一维问题了。

即(1)()min ()min ()min ()K K K k k f X f X S f αα+=+=由此可见，最佳步长*K α由一维搜索方法来确定 求*k α，使得()()()()()()min K K K K f f X S αα=+→ 一、一维搜索区间的确定区间[,]a b 应满足()(*)()f a f f b α>< *a b α<<进退法确定搜索区间 区间的特点：两边翘。

方法的思想;1）先明确函数在某一初始点的走势,是上升还是下降,若是下降，则最小点在该点的右边，若是上升，则最小点在函数的左边。

第三章无约束优化法概述梯度法牛顿法共轭梯度法坐标轮换法鲍威尔法概述无约束优化问题的一般形式：求设计变量X 工[X i,X2，…X n]T使目标函数F（x） > min，对X没有任何约束条件。

工程实际问题中，无约束结构优化问题很少，多数是有约束条件的。

学习无约束结构优化原因：1）工程也有少量无约束结构优化问题，其数学模型就是无约束优化问题，除了在非常接近最小点的情况下，可以按无约束问题处理；2）为研究约束优化问题打下基础；3）约束优化问题可以通过一系列无约束方法达到。

无约束优化问题的求解，可以直接应用函数极值问题的求解方程：iF =0的问题，即求X，使其满足：cx1cF °cx2n个方程组，一般为非线性的，很难用解析方法求解，一般采用数值方法。

与其用数值方法求解非线性方程组，倒不如用数值方法直接求解无约束极值问题。

数值方法最常用的就是搜索法，其基本思想：从给定的初始点x0出发，按照一定原则寻找搜索方向S0，沿方向S0进行搜索，确定最佳步长：'，使得函数沿方向S0下降最快，依次形成迭代公式:X k 1=X k g k S k k =0,1,2，…根据构成搜索方向所使用的信息不同分为：（1）间接法利用目标函数的一阶或二阶导数，如梯度法（最速下降法）、牛顿法、共轭梯度法和变尺度法；梯度法最早由1847年柯西提出，是无约束优化的基本方法。

其基本思想：取目标函数的负梯度方向作为迭代的搜索方向，必使函数值下降的速度最快。

k设在第k次迭代中取得迭代点x，从该点出发，取负梯度方向：S k _ F(X k)为搜索方向，式中：*)=匡g亜心•…兰曲GX\ CX2 dx n第k 1次得到的新点：X k1=x k-宀F(X k)—般步长、丫一k= 1常采用沿负梯度方向做一维搜索：k 1 k k k、F(X ) = min F(X y S )算法特点：初始阶段改进较快，最优解附近改进较慢。

具体迭代步骤：1. 选择初始点X0及迭代精度；・0,令迭代次数k=0；2. 计算点X k的梯度、F(X k)及梯度的模、F(X k)，并令s k U'F(X k)3. 判断是否满足收敛精度|p F(X k)卜S—般情况下，若p F(X k)|"，则X k为近似最优点，F(X k)为近似最优值，可以输出最优解X” = X k，kF(X ) =F(X )，否则进行4.4. 从点X k出发，沿负梯度方向求最优步长:-k，及沿S k进行一维搜索，求得使函数下降最多的步长因子:-kmin F(X k：k S k) =min ()x k1 =x k-:.k s k令^k 1，转入2步。

【复习笔记】最优化⽅法-3.⽆约束优化⽅法第三章⽆约束优化⽅法本⽂是本⼈研究⽣课程《最优化⽅法》的复习笔记，主要是总结课件和相关博客的主要内容⽤作复习。

3.1 算法理论基础1. ⽆约束优化问题的最优性条件先是⼀元函数取得极值的条件，⾼中就学过的然后是拓展到多元函数后的理论这三条和前⾯⼀元函数的三条是⼀⼀对应的，半正定对应⼤于等于，正定对应严格⼤于。

这⾥的最优性⼀直在说的都是局部最优性。

2. ⽆约束凸规划问题的最优性条件凸规划就有⼀个很好的特点，就是只要是局部最优解，那他就是全局最优解，也就是不存在鞍点了，再把前⾯的思路拓展就可以得到很好的结果了。

3. 线搜索下降算法及其收敛性算法收敛性收敛速度后⾯的⼏种⽅法总览参考：【1】最速下降法利⽤⽬标函数⼀阶梯度进⾏下降求解，易产⽣锯齿现象，在快接近最⼩值时收敛速度慢。

Newton法利⽤了⼆阶梯度，收敛速度快，但是⽬标函数的Hesse矩阵不⼀定正定。

于是出现了修正的Newton法，主要是对不同情况进⾏了分情况讨论。

Newton法的优缺点都很突出。

优点：⾼收敛速度（⼆阶收敛）；缺点：对初始点、⽬标函数要求⾼，计算量、存储量⼤（需要计算、存储Hesse矩阵及其逆）。

共轭梯度法是介于最速下降法和⽜顿法之间的⼀个⽅法，相⽐最速下降法收敛速度快，并且不需要像⽜顿法⼀样计算Hesse矩阵，只需计算⼀阶导数(共轭梯度法是共轭⽅向法的⼀种，意思是搜索⽅向都互相共轭)。

拟Newton法是模拟Newton法给出的⼀个保优去劣的算法。

3.2 最速下降法最速下降⽅向：梯度的定义是：变化最快的⽅向，其实指向的就是上升最快的⽅向。

下降最快的⽅向是梯度的反⽅向，即−g k。

1. 算法框架2. 优缺点3. 精确⼀维线搜索 + 最速下降法：4. 例题3.3 ⽜顿法这⾥参考博客：1. ⽜顿法与阻尼⽜顿法2. 优缺点Processing math: 100%3. 例题3.4 共轭梯度法共轭⽅向法是介于最速下降法和Newton法之间的⼀种⽅法。

第七节 变尺度法（拟牛顿法）变尺度法是无约束最优化方法发展过程中非常有影响的重要研究成果，它的基本思想是基于有很好收敛速度的牛顿法。

但又避免了计算二阶导数矩阵及其求逆计算，又比共轭梯度法有更好的收敛速度，被认为是求最优化问题的最有效的算法之一。

牛顿法的缺点：计算复杂（一阶、二阶偏导数）、对函数的性态要求高（对海赛矩阵要求、对初始点的选择要求） 一、变尺度法的基本原理 一）范数和尺度函数图象联系了函数和几何，表达两个数之间的变化关系，映射推广了函数的概念，使得自变量不再仅仅局限于一个数，也不再局限于一维，任何事物都可以拿来作映射，维数可以是任意维，传统的函数图象已无法直观地表达高维对象之间的映射关系，这就要求我们在观念中，把三维的几何空间推广到抽象的n 维空间。

由于映射的对象可以是任何事物，为了便于研究映射的性质以及数学表达，我们首先需要对映射的对象进行“量化”，取定一组“基”，确定事物在这组基下的坐标，事物同构于我们所熟悉的抽象几何空间中的点，事物的映射可以理解为从一个空间中的点到另一个空间的点的映射，而映射本身也是事物，自然也可以抽象为映射空间中的一个点。

范数是把一个事物映射到非负实数，且满足非负性、齐次性、三角不等式，符合以上定义的都可以称之为范数，所以，范数的具体形式有很多种（由内积定义可以导出范数，范数还也可以有其他定义，或其他方式导出）。

从一个线性空间到另一个线性空间的线性映射，可以用一个矩阵来表达，矩阵被看线性作映射，线性映射的性质可以通过研究矩阵的性质来获得。

平面解析几何中一个向量1,2()TX x x =的长度的定义：1/22212X x x =+它具有非负性、齐次性和三角不等式三个基本性质。

向量范数定义 一个从到的非负函数叫做上的向量范数，如果满足：（1） 正定性：对所有的有，而且当且仅当；（2） 齐次性：对所有的和有； （3） 三角不等式：对所有的有.向量x 与y 之间的距离可定义为的x-y 范数，即(,)d X Y X Y =-常用范数最常用的范数就是p-范数。