下载文档原格式
第四章
第四章
无约束优化问题标准形式：
无约束优化问题标准形式：
§
§
§
§
§
§
图最速下降法的收敛过程
αα
2
2
例4－1 求目标函数
取初始点
[2,2]
=
x
例4－2 求目标函数解取初始点[2,2]
=x
算出一维搜索最佳步长
§
例4－3 用梯度法求下面无约束优化问题：
例4－3 用梯度法求下面无约束优化问题：
例4－3 用梯度法求下面无约束优化问题：
例4－3 用梯度法求下面无约束优化问题：
例4－3 用梯度法求下面无约束优化问题：
梯度法的特点
x
给定0,ε
一般迭代式：
§4.3
§4.3
§4.3
§4.3
α0
d 0
x
x 1
x*
1
α1d 1
1()
f −∇x d 1
4-4 共轭方向法
假设目标函数f (x ) 在极值点附近的二次近似函数为
沿某个下降方向
如果能够选定这样的搜索方向，那么对于二
α
0d0
x0x1x*
1
α
1
d1
1
()
f
−∇x d
1。
第四章 无约束优化方法第一节 概述1为什么要研究无约束优化问题?（1）有些实际问题，其数学模型本身就是一个无约束优化问题。
（2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。
（3）约束优化问题的求解可以通过一系列无约束优化方法来达到。
所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。
2各种无约束优化方法的区别在于确定其搜索方向0d 的方法不同。
根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。
一：间接法——要使用导数的无约束优化方法，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。
二：直接法——只利用目标函数值的无约束优化问题，如坐标轮换法、鲍威尔法单纯形法等。
第二节 最速下降法（梯度法） 1基本思想：函数的负梯度方向是函数值在该点下降最快的方向。
将n 维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。
2梯度法的特点：（1）理论明确，程序简单，对初始点要求不严格。
（2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。
（3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。
（4）梯度法的收敛速度与目标函数的性质密切相关。
对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。
3选用原则及条件：一般与其他算法配合，在迭代开始时使用。
第三节 牛顿型方法 1基本思想：在xk 邻域内用一个二次函数)(x ϕ来近似代替原目标函数，并将)(x ϕ的极小点作为对目标函数)(x f 求优的下一个迭代点1+k x 。
经多次迭代，使之逼近目标函数)(x f 的极小点。
2牛顿型方法的特点：（1） 初始点应选在X *附近，有一定难度；（2） 若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向； （3） 不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。
第一节，概述
无约束优化问题：求n维设计变量x=（x1，x2，…，x n）T，使目标函数f（x）→min，而对
x没有任何限制。
用数学方法求解方程▽f=0的问题/，。
该方程为非线性方程，不宜直接求解，选择搜索法。
给定初始点x0，沿着某一方向d0进行搜索，确定最佳步长α0，使得沿着d0方向下降最大；x k+1=x k+αk d k。
根据d的构成分类：一类为利用目标函数一阶和二阶导数的无约束优化方法【最速下降法】，【共轭梯度法】，【牛顿法】，【变尺度法】，另一类只利用目标函数值【坐标轮换法】，【单形替换法】，【鲍威尔法】。
第二节，最速下降法
又称梯度法，以负梯度方向作为搜索方向。
d=-▽f（x）；x k+1=x k-αk▽f（x k）
α为步长因子，取一维搜索的最佳步长：f（x k+1）=f（x k-αk▽f（x k））=minαf（x k-αk▽f（x k））=minαφ（α）→φ'（α）=-（▽f（x k-αk▽f（x k）））▽f（x k）=0→▽f（x k+1）▽f（x k）=0 相邻两次迭代方向垂直。
【重点】第三节，牛顿法
牛顿迭代公式：x k+1=x k-
多元函数f（x），设x k为f（x）极小点x*的一个近似点，在x k处将f（x）进行泰勒展开，保留二次项，得到：f（x）≈f（x k）+▽f（x k）T（x-x k）+;
整理出牛顿迭代公式：x k+1=x k-（▽2f（x k））-1▽f（x k）
阻尼牛顿法：引入阻尼因子αk，故有x k+1=x k-αk（▽2f（x k））-1▽f（x k），其中αk可由极小化求解：f（x k+1）=f（x k+αk d k）=minαf（x k+αd k），其理论意义为沿着d k方向一维搜索的最佳步长。
第四节，共轭方向法
共轭方向：d k和d k+1满足（d k）T G（d k+1）=0
原则和步骤：选定初始点x0，下降方向d0和收敛精度ε；沿着d0方向一维搜索，x1=x0+αd0；判断（），不满足则反复迭代演算，其中新方向dk+1满足（d k）T Gd k+1=0 【第五节】共轭梯度法
每一个共轭矢量都是依赖于迭代点处的负梯度构造的。
共轭方向与梯度之间的关系:
x k+1-x k=αk d k
在x k和x k+1处的梯度为g k，g k+1，设二次函数f（x）=1/2x T Gx+b T x+c,
g k=Gx k+b; g k+1=Gx k+1+b;
g k+1-g k=G(x k+1-x k)=αk Gd k
若d j和d k共轭，则有（d j）T（g k+1-g k）=0
意义：沿着d j方向一维搜索其终点x k+1与始点x k的梯度之差g k+1-g k与d k的共轭方向d j正交。
计算过程：设初值点x0，第一个搜索方向取x0的负梯度方向-g0，一维搜索后得x1，g1，要求x1为以d0为切线和某等值曲线的切点，g1和d0正交，g1T g0=0；求d0的共个方向d1，改
写d1=- g1+β0 d0其中：β0=，d1=，计算x2、g2；计算d2…直到迭代点梯度
的模小于允许值。
得到共轭方向的递推公式：d k+1=
第六节，变尺度法
放大或缩小各个坐标，通过尺度变换可以把函数的偏心程度降低到最低限度，显著地改善收敛性质。
尺度变换矩阵Q，尺度矩阵H=Q T Q；
变尺度法步骤：x0，ε→g0，H0（可取I）→d k=-H k g k→一维搜索求x1，g1→判断迭代终止条件，若不满足则取H k=I，x0=x k+1重新迭代
第七节，坐标轮换法
每次搜索只允许一个变量变化，其余变量保持不便，及沿着坐标方向轮流进行搜索的寻优方法。
当目标函数为二元二次函数其等值线为圆或长短轴平行于坐标的椭圆时此方法有效。
【重点】第八节，鲍威尔法
直接利用函数值来构造共轭方向的一种共轭方向法。
对于二次函数：
f（x）=1/2x T Gx+b T x+c；G正定，在逐次迭代中构造G的共轭方向。
构造共轭方向原理：
设x k和x k+1为从不同点出发沿着不同方向d j进行一位搜素得到的两个极小值点，x k和x k+1，梯度g k，g k+1，梯度与等值线垂直，故（d j）T g k=0，（d j）T g k+1=0；同时g k=Gx k+b，g k+1=Gx k+1+b，有g k+1- g k=G（x k+1- x k），（d j）T（g k+1- g k）=0=（d j）T G（x k+1- x k）
取d k=x k+1-x k，d j d k共轭，即沿着d j方向对函数做两次一维搜索得到的两个极小值的连线就是与d j一起对G共轭的方向。
基本算法：
x0，两个线性无关矢量e1，e2做为搜索方向→得到x10和x20→d1= x20-x10→d1代替e1，新搜索方向：e2，d1…
改进算法：考虑到原始的矢量组的好坏是否需要替换。
第九节，单形替换法
基本原理：单形替换法指在n维空间中建立≥n+1个顶点的多面体（单纯形）。
计算其各顶点函数值并加以比较，从中确定搜索方向和步长，找到一个较好的点取代单纯形中较差的顶点，组成的新单纯形更加靠近目标函数的极小点。
可通过反射、远探、近探和缩边等方式不断地更新单纯形，逐渐逼近极小点，直到足够接近为止。
