下载文档原格式
第四章
第四章
无约束优化问题标准形式：
无约束优化问题标准形式：
§
§
§
§
§
§
图最速下降法的收敛过程
αα
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。
1优化问题概述在保证基本机械性能的基础上,借助计算机，应用一些精度较高的力学/ 数学规划方法进行分析计算，让某项机械设计在规定的各种设计限制条件下，优选设计参数，使某项或几项设计指标（外观、形状、结构、重量、成本、承载能力、动力特性等）获得最优值。
机械优化设计的过程:(l)分析设计变量，提出目标函数,确定约束条件，建立优化设计的数学模型;(2)选择适当的优化方法，编写优化程序;（3）准备必须的初始数据并上机计算，对计算机求得的结果进行必要的分析.优化方法的选择取决于数学模型的特点，如优化设计问题规模的大小、目标函数和约束函数的性态以及计算精度等，在选择各种可用的优化方法时，需要考虑的问题是优化方法本身的适应性和计算机执行该程序时所花费的时间和费用。
.一般认为,对于目标函数和约束函数均为显函数且设计变量个数不太多的问题,可选用罚函数法；对于只含有线性约束的非线性规划问题，可选用梯度投影法;对于函数易于求导的问题，可选用可行方向法；对于难以求导的问题则应选用直接法，如复合形法.1.2传统优化算法概述根据对约束条件处理的方式不同，可将传统的约束优化方法分为直接法和间接法两大类.直接法通常适用于只含不等式约束的优化问题，它是在可行域内直接搜索可行的最优点的优化方法，如复合形法、随机方向法、可行方向法和广义简约梯度法。
间接法是目前在机械优化设计中应用较为广泛的一种优化方法，其基本思路是将约束优化问题转化成一个或一系列无约束优化问题，再进行无约束优化计算，从而间接地搜索到原约束问题的最优解。
如惩罚函数法和增广拉格朗日乘子法。
1.2。
1直接法复合形法是一种求解约束优化问题的重要的直接解法，其基本思想是在n 维设计空间内构造以k 个可行点为顶点的超多面体，即复合形.对各个顶点所对应的目标函数值进行比较，将目标函数值最大的顶点,即最坏点去掉,然后按照一定的法则求出目标函数值有所下降的可行的新点，并以此点代替最坏点，构成新的复合形.如此重复，直至复合形缩小到一定的精度，即可停止迭代,获得最优解.随机方向法是一种原理很简单的直接解法,其基本思想是在可行域内任意选一初始点,然后利用随机数的概率特性产生若干个随机方向，并从中选出一个使目标函数值下降最快的随机方向作为搜索方向进行搜索.约束变尺度法是一种最先进的非线性规划计算方法，它将二次规划、线性近似、拉格朗日乘子、罚函数、变尺度以及不确定搜索这些方法有效地结合在一起，其基本思想是首先对优化问题产生拉格朗日函数，然后利用该函数在每个迭代点构造一个带有不等式约束条件的二次规划子问题，由于该子问题不易求解析解,所以只能借助于数值方法求解其极值，以每次迭代的二次规划子问题的极值解作为此次迭代的搜索方向,同时采用不精确一维搜索确定搜索步长因子，产生新的迭代点，经过一系列迭代后，最终逼近原问题的最优解。
第29卷 第6期2007年6月武汉理工大学学报 信息与管理工程版J OURNAL OF WUT (I N FORM AT I ON &MANAGE M ENT E NG I NEER I NG )V o.l 29N o .6June 2007文章编号:1007-144X (2007)06-0073-04一般约束条件下的变尺度法方建斌1,2,王展青2,王雨春2,张克新3(1.江汉大学数学与计算机科学学院,湖北武汉430056;2.武汉理工大学理学院,湖北武汉430070;3.黄冈职业技术学院基础课部,湖北黄冈438002)摘 要:从应用角度出发,首先,将约束变尺度法改进为一般约束条件,通过适当选择差商形式和对一维不精确线性搜索方法的修正,扩大了该方法的适用范围。
然后,给出了该方法完整的算法框图,并讨论了算法分析和进一步的改进方法。
最后,通过实例验证了方法改进后的实用性和高效性。
关键词:约束变尺度法;一般约束;差商;二次规划中图法分类号:O 224 文献标识码:A约束非线性问题是工程优化设计中最为普及的一类问题。
随着工程设计理论、方法和手段的不断发展,对优化设计的要求也越来越高,所考虑的因素也越来越多。
20世纪80年代,对约束非线性规划算法的研究,取得了很大成果,其中La grange 函数乘子法、投影梯度法及约束变尺度法(constrai n ed variable m etric m et h od ,C VM )已成为该领域的主导算法,尤以CVM 方法对一般约束问题最为有效。
它是由变尺度法改进而来,它把二次规划、线性近似、Lagrange 乘子、罚函数、变尺度及不精确搜索这些有特色的方法有效地结合在一起。
约束变尺度法在初始的变尺度法的基础上,对目标函数进行线性搜索,H ESSE 矩阵修正,差分求梯度和二次规划,将优化数学模型转化为二次规划子问题,再进行寻优。
从应用角度出发,对该方法作了改进,通过适当选择差商形式和对一维不精确线性搜索方法的修正,扩大了该方法的适用范围[1]。
(1)带约束的非线性优化问题解法小结考虑形式如下的非线性最优化问题(NLP):min f(x)「g j (x )“ jI st 彳 g j (x)=O j L其 中， ^(x 1,x 2...x n )^ R n， f : R n > R ， g j :R n > R(j I L) ， I 二｛1,2,…m ｝， L ={m 1,m 2...m p}。
上述问题(1)是非线性约束优化问题的最一般模型，它在军事、经济、工程、管理以 及生产工程自动化等方面都有重要的作用。
非线性规划作为一个独立的学科是在上世纪 50年 代才开始形成的。
到70年代，这门学科开始处于兴旺发展时期。
在国际上，这方面的专门性 研究机构、刊物以及书籍犹如雨后春笋般地出现，国际会议召开的次数大大增加。
在我国， 随着电子计算机日益广泛地应用，非线性规划的理论和方法也逐渐地引起很多部门的重视。
关于非线性规划理论和应用方面的学术交流活动也日益频繁，我国的科学工作者在这一领域 也取得了可喜的成绩。
到目前为止，还没有特别有效的方法直接得到最优解，人们普遍采用迭代的方法求解： 首先选择一个初始点，利用当前迭代点的或已产生的迭代点的信息，产生下一个迭代点，一 步一步逼近最优解，进而得到一个迭代点列，这样便构成求解( 1)的迭代算法。
利用间接法求解最优化问题的途径一般有：一是利用目标函数和约束条件构造增广目标 函数，借此将约束最优化问题转化为无约束最优化问题，然后利用求解无约束最优化问题的 方法间接求解新目标函数的局部最优解或稳定点，如人们所熟悉的惩罚函数法和乘子法；另 一种途径是在可行域内使目标函数下降的迭代点法，如可行点法。
此外，近些年来形成的序 列二次规划算法和信赖域法也引起了人们极大的关注。
在文献［1］中，提出了很多解决非线性 规划的算法。
下面将这些算法以及近年来在此基础上改进的算法简单介绍一下。
1. 序列二次规划法序列二次规划法，简称SQ 方法.亦称约束变尺度法。
§3.5 变尺度法DEF 变尺度法: 1. 变尺度的定义：每确定一次搜索方向，调整一次模（尺度）的大小，称为变尺度。
2. 基本思想：发扬梯度法和牛顿法各自的优点，避免两者各自的缺点，将两者结合起来，形成变尺度法。
3. 变尺度矩阵的构造：原则：使目标函数值有下降性，则变尺度矩阵应为实对称矩阵（请证明）； 使算法有二次收敛性，则 S(k) (k=1,2,…)应关于 H(k) 是共轭的；构造变尺度矩阵的递推公式：4. 修正矩阵:了牛顿法的优点。
矩阵的逆矩阵，而利用及这样避免计算二阶导数即为牛顿法。
最终迭代时，时接近当不断修正尺度，逼近，中间的迭代即为梯度法，，首次迭代时，为拟牛顿方向。
的矩阵一个为变尺度矩阵，是：其中：迭代公式Hesse x f x H S x f x H S x H H x x x H H x f S I H x f H S n n H x f H x x k K k k K k K k k k k k k k k k k k k k k k ,)()]([,,)()]([,)]([*,)]([,)(,)(][,),(][)(1)()()(1)()(1)()()(1)()()()()0()()()()()()()()()1(∇-=∇-→→-∇==∇-=⨯∇-=----+α。
即：件）变尺度条件（拟牛顿条)()]()([,)()1()()1()1()()()1(k k k k k k k k x x x f x f Hx g H -=∇-∇∆=∆⋅∙++++次迭代时的修正矩阵。
为第其中：k E E H H k k k k )()()()1(,+=+5.步骤：（略）6. 方法评价：DEF 变尺度法以逐次逼近的方法实现 H-1 的计算，当目标函数的一阶导数易求时，以一阶代替二阶导数的计算是有效的方法。
算法的第一步是梯度法，最速下降；接近 x* 时，又采用二次收敛的共轭方向，总的收敛速度较快。
约束变尺度法Newton 法最突出的优点是收敛速度快，在这一点上其它算法无法比拟的。
因此，建议凡是Hesse 矩阵比较容易求出的问题，尽可能使用Newton 法求解。
但是，Newton 法也有一个严重缺陷，就是每次迭代都要计算目标函数的Hesse 矩阵和它的逆矩阵，当问题的维数较大时，计算量迅速增加，从而就抵消了Newton 法的优点。
为此，人们开始寻找一种算法既可以保持Newton 法收敛速度快的优点，又可以摆脱关于Hesse 矩阵的计算，这就是变尺度算法。
变尺度法是一种非常好的方法，其中DFP 算法和BFGS 算法。
可以说，直到目前为止，在不用Hesse 矩阵的方法中是最好的算法。
一、拟Newton 法为了吸收Newton 法收敛速度快的优点，同时避免Newton 法每次迭代都要计算目标函数的Hesse 矩阵和它的逆矩阵，人们提出了具有超线性收敛的拟Newton 法。
（一）拟Newton 法的基本原理在Newton 法中的基本迭代公式kk k k P t X X +=+1，其中1=k t ，)()]([12kkk Xf Xf P ∇∇-=-令)()(2kkkkXf gXf G∇=∇=，于是有，，，，21011=-=-+k g G X X k k k k其中X0是初始点, gk 和 Gk 分别是目标函数f (X )在点 Xk 的梯度和Hesse 矩阵.为了消除这个迭代公式中的Hesse 逆矩阵G-1k ,可用某种近似矩阵Hk=Hk(Xk)来替换它,即构造一矩阵序列{Hk}去逼近Hesse 逆矩阵序列{G-1k}，此时kk k k g H X X -=+1事实上,式中 Pk= -Hk gk 无非是确定了第k 次迭代的搜索方向.为了取得更大的灵活性,考虑更一般的迭代公式kk k k k g H t X X -=+1其中步长tk 通过从Xk 出发沿Pk= -Hk gk 作直线搜索来确定.此式代表很广的一类迭代公式.例如,当Hk=I (单位矩阵)时,它变为最速下降法的迭代公式。
附加条件为了使Hk 确实与G-1k 近似并有容易计算的特点,必须对 Hk 附加某些条件:⑴ 为保证迭代公式具有下降性质,要求 {Hk} 中的每一个矩阵都是对称正定的.因为使搜索方向Pk= -Hk gk 是下降方向, 只要<-=k k Tk k T k g H g P g⑵ 求Hk 之间的迭代具有简单形式.可设为最简单的形式:kk k E H H +=+1其中 Ek 称为校正矩阵,此式称为校正公式.⑶ {Hk}必须满足拟Newton 条件.（二）拟Newton 法的算法构造已知目标函数f (X )及其梯度 g(X ),终止限ε。
Step 1 选定初始点X0;计算 f0=f(X0),g0=g(X0),选定初始矩阵 H0,要求H0 对称正定(例如, H0=I)，置k=0.Step 2 计算搜索方向kk k g H P -=. Step 3 作直线搜索),(1k k k P X ls X =+.计算111111(),(),,k k k k k k k k k kf f Xg g X S X X y g g ++++++===-==.Step 4 判别终止准则是否满足.若满足,则Xk+1就是所求的极小点,否则转Step 5. Step 5 计算kk k E H H +=+1.Step 6 k=k+1,转Step 2 .其中校正矩阵Ek 可由确定的公式来计算.不同的公式对应不同的拟Newton 算法.（三）拟Newton 算法的流程图二、DFP 变尺度法DFP 算法首先由Davidon 1959年提出,1963年, Fletcher 和Powell 作了改进,形成DFP 算法.D,F,P 是这三位学者名字的字头.这种算法是无约束最优化方法最有效的方法之一.（一）DFP 算法的基本原理考虑校正公式:Tk k k Tk k k k k V V U U H H βα++=+1其中Uk,Vk 是待定n 维向量,αk,βk 是待定常数.这时,校正矩阵是Tk k k Tk k k k V V U U E βα+=根据拟Newton 条件kk k k T k k k T k k k y H S y V V UU -=+)(βα或kk k k T k k k k Tk k k y H S y V V y U U -=+βα满足这个方程的Uk,Vk 有无穷多种取法, 其中的一种:T k k k k kU U y S α=，T k k k k k kV V y H y β=-注意到kTk y U 和kT k y V 都是数量,k k k k k U S V H y ==，不妨取 ， 可取 1/),1/()T Tk k k k k k k S y y H y αβ==-(得kk Tk kTk k k k T k T k k kk y H y H y y H y S S S HH-+=+1这就是DFP 校正公式（二）DFP 算法的算法构造已知目标函数f (X )及其梯度 g(X ),问题的维数n,终止限ε Step 1 选定初始点.计算 0000(),()f f Xg g X ==Step 2 置000,,0H I P g k ==-=.Step 3作直线搜索),(1k k k P X ls X =+1111()()k k k k f f X g g X ++++==，计算Step 4 判别终止准则满足否. Step 5 若k=n,则置010101k k k X X f f g g +++===，，Step 6 计算1k k k S X X +=-,1k k ky g g +=-1T T k k k k k kk k T Tk k k k kS S H y y H H H S y y H y +=+-,111k k k P H g +++=-置k=k+1,转Step 3.（三）DFP 算法的流程图三、BFGS 变尺度法另一个有效和著名的变尺度算法是Broyden, Fletcher(1970), Goldfarb(1969)和Shanno(1970)共同研究的结果,因而叫做BFGS 法.（一）BFGS 算法的基本原理考虑校正公式Tk k k k Tk k T k kk T k k T k k k k T k T k k k k W W y H y S y y H y H y y H S y S S H H ))((1β+-+=+其中,kk Tk kk k T k k k y H y y H S y S W -=校正矩阵为Tk k k k Tk k T k kk T k k Tk k k k T k T k k k W W y H y S y y H y H y y H S y S S E ))((β+-=β为实数参数, 每取一个实数就对应一种拟Newton 算法. 当取β=0时就是DFP 校正公式 令1/()T k k S y β=得著名的DFGS 校正公式⎥⎥⎦⎤⎢⎢⎣⎡--⎪⎪⎭⎫ ⎝⎛++=+k T k k T k k k T kk k Tk kk T k kTk k k H y S S y H S S y S y H y y S H H 111（二）DFGS 算法迭代步骤已知目标函数f (X )及其梯度g (X ),问题的维数n,终止限ε. Step 1 选取初始点X0,初始矩阵 H0=I,给定终止限 ε>0. Step 2 求初始梯度f (X0).若||f (X0)||≤ε,停止输出X0;否则.Step 3 构造初始BFGS 方向,取0000()(),0P H f X f X k =-∇=-∇=.Step 4 进行一维搜索,求tk,使得11(,),k k k k k k kX ls X P X X t P ++==+.Step 5 求梯度f (Xk+1).若||f (Xk+1)||≤ ε,停止输出Xk+1;否则.Step 6 检验迭代次数,若k+1=n,令X0=Xn 转(3);否则. Step 7 构造BFGS 方向,用BFGS 公式⎥⎥⎦⎤⎢⎢⎣⎡--⎪⎪⎭⎫ ⎝⎛++=+k T k k T k k k T kk k Tk kk T k kTk k k H y S S y H S S y S y H y y S H H 111计算,取,令1111,(),1k k k k H P H f X k k ++++=-∇=+转Step 4.（三）DFGS 算法的流程图计算 f (X 计算 f (X 00()H f X ∇=-∇k 使1k X =+(1+∇-k X f H || f (X 0)||N|| f (X k +1)||Nk +1=N四、变尺度法的算法分析Newton 法每次迭代都要计算目标函数的Hesse 矩阵和它的逆矩阵，当问题的维数较大时，计算量迅速增加，从而就抵消了Newton 法收敛速度快的优点。
而变尺度算法则可以保持Newton 法收敛速度快的优点，又可以摆脱关于Hesse 矩阵的计算。
变尺度法中的二个重要算法DFP 算法和BFGS 算法迭代过程相同,区别仅在于校正矩阵Ek 选取不同,对于DFP 法,由于一维搜索的不精确和计算误差的积累可能导致某一轮的Hk奇异,而BFGS法对一维搜索的精度要求不高,并且由它产生的 Hk不易变为奇异矩阵.BFGS法比DFP法更具有好的数值稳定性,它比DFP 法更具有实用性.。
