当前位置：文档之家 › 8无约束最优化的直接法

8无约束最优化的直接法

  • 格式：doc
  • 大小：443.00 KB
  • 文档页数：8

第八章 无约束最优化的直接法本章主要内容：坐标轮换法及其收敛性 模式搜索法及其收敛性 旋转方向法、Powell 法。

教学目的及要求：掌握坐标轮换法并理解其收敛性，掌握模式搜索法并理解其收敛性；了解旋转方向法、Powell 法。

教学重点：Powell 法． 教学难点：Powell 法． 教学方法：启发式．教学手段：多媒体演示、演讲与板书相结合． 教学时间：6学时． 教学内容：§8.1 坐标轮换法考虑无约束最优化问题min ()f x ， （8.1.1） 其中,:n n x R f R R ∈→．算法8-1（坐标轮换法）Step1 选取初始数据．选取初始点0x ，给定允许误差0ε>，令1k =．Step2 进行一维搜索．从1k x -出发，沿坐标轴方向010k e ⎛⎫⎪ ⎪⎪= ⎪ ⎪ ⎪⎝⎭进行一维搜索，求1k λ-和k x ，使得111()min ()k k k k k f x e f x e λλλ---+=+，11k k k k x x e λ--=+．Step3 检查迭代次数．若k n =，转Step4；否则，令:1k k =+，返回Step2． Step4 检查是否满足终止准则．若0n x x ε-<，迭代终止，得n x 为问题（8.1.1）的近似最优解；否则，令0:,:1n x x k ==，返回Step2．定理8.1.2 设:n f R R →具有一阶连续偏导数，0n x R ∈，记0()f x α=，且水平集(,)S f α有界．若{}k x 是用坐标轮换法求解问题（8.1.1）产生的点列，且在每次一维搜索中所得到的最优解都是唯一的，则（1）当{}k x 为有穷点列时，其最后一个点是f 的平稳点；（2）当{}k x 为无穷点列时，它必有极限点，并且其任一极限点都是f 的平稳点．例1 用坐标轮换法求解问题2212112min ()3f x x x x x x =+--， （8.1.3） 其中12(,)T x x x =．取初始点(0)(0,0)T x =，允许误差0.1ε=．解 从点(0)x 出发沿1e 进行一维搜索：(0)101000x e λλλ⎛⎫⎛⎫⎛⎫+=+= ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭，将12,0x x λ==代入2212112()3f x x x x x x =+--中，易得(1)(0)00133,(,0)22T x x e λλ==+=；从点(1)x 出发沿2e 进行一维搜索，得(2)(1)112333,(,)424T x x e λλ==+=；(2)(0)x x ε->．再从点(2)x 出发沿1e 进行一维搜索，得(3)(2)2213153,(,)884Tx x e λλ==+=； 从点(3)x 出发沿2e 进行一维搜索，得(4)(3)33231515,(,)4816Tx x e λλ==+=； (4)(2)x x ε->．再从点(4)x 出发沿1e 进行一维搜索，得(5)(4)44136315,(,)323216T x x e λλ==+=；从点(5)x 出发沿2e 进行一维搜索，得(6)(5)55236363,(,)643264T x x e λλ==+=； (6)(4)x x ε->．再从点(6)x 出发沿1e 进行一维搜索，得(7)(6)661325563,(,)12812864Tx x e λλ==+=； 从点(7)x 出发沿2e 进行一维搜索，得(8)(7)7723255255,(,)256128256Tx x e λλ==+=； (8)(6)x x ε-<．迭代终止，得问题（8.1.3）的近似最优解为(8)255255(,)128256Tx =． 其实问题（8.1.3）的最优解为(2,1)T ．§8.2 模式搜索法算法8-2（模式搜索法）Step1 选取初始数据．选取初始点0x ，初始步长00δ>，给定收缩因子(0,1)α∈，给定允许误差0ε>，令0k =．Step2 确定参考点．令,1k y x j ==．Step3 进行正轴向探测．从点y 出发，沿j e 作正轴向探测：若()()k j f y e f y δ+<，令:k j y y e δ=+，转Step5；否则，转Step4．Step4 进行负轴向探测．从点y 出发，沿j e 作负轴向探测：若()()k j f y e f y δ-<，令:k j y y e δ=-，转Step5；否则，转Step5．Step5 检验探测次数．若j n <，令:1j j =+，返回Step3；否则，令1k x y +=，转Step6．Step6 进行模式移动．若1()()k k f x f x +<，从点1k x +出发沿加速方向1k kx x +-作模式移动，令112,,:1,1k k k k y x x k k j δδ++=-==+=，返回Step3；否则，转Step7．Step7 检查是否满足终止准则．若k δε<，迭代终止，得问题（8.1.1）的近似最优解为k x ；否则，转Step8．Step8 缩短步长．若1k k x x +=，令1,:1k k k k δαδ+==+，返回Step2；否则，令11,,:1k k k k x x k k δδ++===+，返回Step2．定理8.2.1 设:n f R R →是具有一阶连续偏导数的凸函数，0n x R ∈，记0()f x α=，并且水平集(,)S f α有界．若{}k x 为由模式搜索法求解问题（8.1.1）产生的点列，则{}k x 必存在极限，且其任一极限点都是问题（8.1.1）的最优解．§8.3 旋转方向法算法8-3（旋转方向法）Step1 选取初始数据．选取初始点0x ，初始单位正交方向组12,,,n d d d （可取12,,,n d d d 为坐标轴方向12,,,n e e e ）．给定初始步长(0)(0)(0)(0)12(,,,)Tn δδδδ= ，收缩因子(0,1)α∈，放大因子1β>，允许误差0ε>，令0k =．Step2 确定参考点．取参考点k y x =，并令,1k z x j ==．Step3 进行轴向探测．若()()()k j j f y d f y δ+<，令()()(:,:k k k jj jj y y d δδβδ=+=，转Step4；否则，令()():k k j j δαδ=-，转Step4．Step4 检验探测次数．若j n <，令:1j j =+，返回Step3；否则，转Step5．Step5 判断探测是否结束．若()()f y f z <，令,1z y j ==，返回Step3；若()(),()()k f y f z f y f x =<，令1k x y +=，转Step6；若()()()k f y f z f x ==，转Step7． Step6 检查是否满足终止准则．若1k k x x ε+-<，迭代终止，1k x +为问题（8.1.1）的近似最优解；否则，转Step8．Step7 检验步长大小．若对一切()1,2,,,k j j n δε=< ，迭代终止，k x 为问题（8.1.1）的近似最优解；否则，令,1z y j ==，返回Step3．Step8 进行轴向旋转．计算各轴向移动的步长的代数和：12,,,n λλλ ，利用,0,,0.j j n j i i j i jd p d λλλ==⎧⎪=⎨≠⎪⎩∑ （8.3.1）11,1,, 2.j T j j i j j j jT i i i p j q q p p d j q p λ-==⎧⎪=⎨-≥⎪⎩∑ （8.3.2） ,1,2,,j j jq d j n q == ． （8.3.1）构造新的单位正交方向12,,,n d d d ，并令(1)(),,1,2,,,:1k k j j j j d d j n k k δδ+====+ ，返回Step2．§8.4 Powell 法算法8-4（Powell 法）Step1 选取初始数据．选取初始点0x ，n 个线性无关的初始搜索方向011,,,n d d d - ，给定允许误差0ε>，令0k =．Step2 进行基本搜索．令0k y x =，依次沿011,,,n d d d - 进行一维搜索．对一切1,2,,j n = ，记11111()min ()j j j j j f y d f y d λλλ-----+=+，111j j j j y y d λ---=+．Step3 检查是否满足终止准则．取加速方向0n n d y y =-，若n d ε<，迭代终止，得n y 为问题的近似最优解；否则，转Step4．Step4 确定搜索方向．按1101()()max {()()}m m j j j n f y f y f y f y ++≤≤--=- （8.4.17）确定m ，若001()2()(2)2[()()]n n m m f y f y f y y f y f y +-+-<- （8.4.18）成立，转Step5；否则，转Step6．Step5 调整搜索方向．从点n y 出发沿方向n d 作一维搜索．求出n λ，使得()min ()n n n n n f y d f y d λλλ+=+．令1k n n n x y d λ+=+，再令1:,,1,,1j j d d j m m n +==+- ，:1k k =+，返回Step2． Step6 不调整搜索方向．令1k n x y +=，:1k k =+，返回Step2．例2 用Powell 法求解问题（8.1.3）：2212112min ()3f x x x x x x =+--，仍取初始点(0)(0,0)T x =，初始搜索方向组01(0,1),(1,0)T T d d ==，给定允许误差0.1ε=．解 第一次迭代：令(0)(0)(0,0)T y x ==，从点(0)y 出发沿0d 进行一维搜索，易得(1)(0)0000,(0,0)T y y d λλ==+=；接着从点(1)y 出发沿1d 进行一维搜索，得(2)(1)11133,(,0)22T y y d λλ==+=由此有加速方向(2)(0)23(,0)2T d y y =-=．因为23/2d ε=>，所以要确定调整方向．由于 (0)(1)(2)9()0,()0,()4f y f y f y ===-，按（8.4.17）式有(1)(2)()(1)()()max{()()|0,1}j j f y f y f y f y j +-=-=，因此1m =，并且()(1)(1)(2)9()()()()4m m f y f y f y f y +-=-=．又因(2)(0)(2)0f y y -=，故（8.4.18）式不成立．于是，不调整搜索方向组，并令(1)(2)3(,0)2T x y ==．第二次迭代：取(0)(1)3(,0)2T y x ==，从点(0)y 出发沿0d 作一维搜索，得(1)(0)000333,(,)424T y y d λλ==+=．接着从点(1)y 出发沿方向1d 作一维搜索，得(2)(1)1113153,(,)884Ty y d λλ==+=． 由此有加速方向(2)(0)233(,)84T d y y =-=．因为2d ε=>，所以要确定调整方向．因(0)(1)(2)945189(),(),()41664f y f y f y =-=-=-，故按（8.4.17）式易知0m =，并且()(1)(0)(1)9()()()()16m m f y f y f y f y +-=-=． 由于(2)(0)45(2)16f y y -=-， 因此（8.4.18）式成立。

合集下载

无约束最优化方法直接搜索法课件

无约束最优化方法直接搜索法课件


x2
S(1)
S2(1
)
(1)
X3 X2 (1)
X* X2 (2) X1 (2)
S(2)
X0 (1)
X 1 (1)
S1(1) x1
• 鲍威尔基本算法的缺点
鲍威尔基本算法仅具有理论意义，不要说对于一般的 函数，就是对于二次函数，它也可能失效。因为在迭代过程 中的n个搜索方向有时会变成线性相关，而不能形成共轭方向， 从而张不成n维空间，导致随后的迭代搜索在降维(“退化”) 的空间中进行，可能求不到极小点，故需进行改进。
x 2 XL X2
Xn+3 Xn+2
Xn+1
Xห้องสมุดไป่ตู้ XH
X1 XG x1
6)扩张：当 fn+2 < f L 时，取扩张点Xn+3 ，即
Xn+3 = Xn+1 + (Xn+2 – Xn+1)
( =1.2~2.0 )
并计算 fn+3 = f (Xn+3 ) 。 若 fn+3 < fn+2 ，则以Xn+3 代替 X H ， fn+3 代替 fH ，构造一个新的单纯形；否则，以 X n+2 代 替XH ， fn+2 代替fH ，构造新的单纯形；然后返回到 3)。
鲍威尔条件：
若 f 3 < f 1, ( f1 - 且2f2 + f3) (f1 - f2 - △m(k))2 < 0.5 △m(k) (f1 - f3 )2 同时成立，则用 S ( k ) 替代 S m ( k ) ；否则，仍用 就是鲍威尔修正算法，通常所说的鲍威尔算法就是指这一修正算法。
• 鲍威尔算法的计算步骤及算法框图
工程优化设计-无约束直接法

工程优化设计-无约束直接法

性质 4) 设 , 沿n个共轭方向依次进行一维搜索, 在第n次搜索时达到整体最优解. n为X维数. Si
X1
X2 S
无约束直接搜索方法
四.共轭方向法及其改进后的Powell法 (2) 共轭方向法 第一轮: S1(1), S2(1) 不一定 共轭, 产生S(1). 第二轮: 取S1(2)= S2(1) S2(2) =S(1), 产生S(2). 第三轮: 取S1(3)= S(1) S2(3) =S(2), 所以,由性质(3)知, 对于 二次函数, S(1), S(2)共轭. 第二轮 第一轮
Powell算法
2.依次一维搜索: X(k)i= X(k)i-1+aS(k)i : min f(X(k)i-1+aS(k)i), i=1,2,…,n
转步6. 转步7.
转步7.
7.如果 否则. k=k+1, 转步2. 结束.
无约束直接搜索方法
Powell法另一形式(保证线性无关) 引理: 设k =det(S1/|S1|, S2/|S2|,…, Sn/|Sn|), k+1=det(S1/|S1|, S2/|S2|,…, Sm-1/|Sm-1|, Sn+1/|Sn+1|, Sm+1/|Sm+1|,…,Sn/|Sn|), 则 k+1= k *am/|Xn(k)-X0(k)|, 这里 Xm(k)=Xm-1(k)+amSm
工程优化设计
黄正东
二0一0年九月
内容提要
• • • • • • • • • • 工程优化问题建模 优化数学理论 一维搜索方法 无约束问题直接搜索方法 无约束问题间接接搜索方法 约束问题直接搜索方法 线性规划与二次规划问题求解 约束问题间接搜索方法 启发式算法 优化软件系统
无约束优化方法

无约束优化方法

第四章无拘束优化方法——最速降落法，牛顿型方法概括在求解目标函数的极小值的过程中，若对设计变量的取值范围不加限制，则称这种最优化问题为无拘束优化问题。

只管对于机械的优化设计问题，多半是有拘束的，无拘束最优化方法仍然是最优化设计的基本构成部分。

因为拘束最优化问题能够经过对拘束条件的办理，转变为无拘束最优化问题来求解。

为何要研究无拘束优化问题（1）有些实质问题，其数学模型自己就是一个无拘束优化问题。

（2）经过熟习它的解法能够为研究拘束优化问题打下优秀的基础。

（3）拘束优化问题的求解能够经过一系列无拘束优化方法来达到。

所以无拘束优化问题的解法是优化设计方法的基本构成部分，也是优化方法的基础。

依据构成搜寻方向所使用的信息性质的不一样，无拘束优化方法能够分为两类。

一：间接法——要使用导数的无拘束优化方法，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。

二：直接法——只利用目标函数值的无拘束优化问题，如坐标轮换法、鲍威尔法纯真形法等。

无拘束优化问题的一般形式可描绘为：求 n 维设计变量X x1x2L x n T R n使目标函数 f ( X )min当前已研究出好多种无拘束优化方法，它们的主要不一样点在于结构搜寻方向上的差异。

无拘束优化问题的求解：1、分析法能够利用无拘束优化问题的极值条件求得。

马上求目标函数的极值问题变为求方程min f ( X * )0的解。

也就是＊使其知足求Ｘf ( X *)0x1f ( X*)x2f ( X*)x n解上述方程组，求得驻点后，再依据极值点所需知足的充足条件来判断能否为极小值点。

但上式是一个含有ｎ个未知量，ｎ个方程的方程组，在实质问题中一般是非线性的，很难用分析法求解，要用数值计算的方法。

由第二章的叙述我们知道，优化问题的一般解法是数值迭代的方法。

所以，与其用数值方法求解非线性方程组，还不如用数值迭代的方法直接求解无拘束极值问题。

2、数值方法数值迭代法的基本思想是从一个初始点 X (0)出发，依据一个可行的搜寻方向 d ( 0)搜寻，确立最正确的步长0使函数值沿 d (0 )方向降落最大，获得 X (1)点。

无约束最优化直接方法和间接方法的异同

无约束最优化直接方法和间接方法的异同

无约束最优化直接方法和间接方法的异同一、什么是无约束最优化最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。

最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。

其的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。

实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。

最优化问题分为无约束最优化和约束最优化问题，约束最优化问题是具有辅助函数和形态约束条件的优化问题，而无约束优化问题则没有任何限制条件。

无约束最优化问题实际上是一个多元函数无条件极值问题。

虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。

或者是将约束优化问题部分转化为无约束优化问题，在远离极值点和约束边界处按无优化约束来处理，在接近极值点或者约束边界时按照约束最优化问题处理。

所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。

无约束最优化方法大致分为两类：一类是使用导数的间接方法，即在计算过程中要用到目标函数的导数；另一类是直接方法，即只要用到目标函数值，不需要计算导数。

这里我们比较这两类方法的异同。

二、无约束最优化方法1.使用导数的间接方法1.1 最速下降法函数的负梯度方向是函数值在该点下降最快的方向。

将 n 维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。

无约束优化问题的数学模型可以表示为：min f x x R n，我们假设函数xf x 具有一阶连续偏导数。