无约束最优化方法

无约束最优化方法无约束最优化方法? 题 求解无约束最优化问题 min f(x) 的数值迭代解法。的数值迭代解法。? 构成约束最优化方法的基础解法 。? 求解无约束最优化问题的下降迭代解法具有统一的迭代格式，其基本问题是选择搜索方向和在这些搜索方向上进行一维搜索。求解无约束最优化问题的下降迭代解法具有统一的迭代格式，其基本问题是选择搜索方向和在这些搜索方向上进行一维搜索。? 由于构成搜索方向的方式可以不同 ， 从而形成了各种不同的无约束最优化方法。无约束优化的直接搜索法各种无约束优化方法的区别就在于确定其搜索方向无约束优化的直接搜索法各种无约束优化方法的区别就在于确定其搜索方向S (k)的方法不同，所以搜索方向的构成问题是无约束优化方法的关键。根据构造搜索方向所使用的信息性质的不同，无约束优化的方法不同，所以搜索方向的构成问题是无约束优化方法的关键。根据构造搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类 ：X (k+1) =X (k) + α α (k) S (k) (k =0 , 1 , 2 , …)方法可以分为两类 ：一类是只利用目标函数值信息的无约束优化方法，如坐标轮换法、鲍威尔法，称为直接搜索法；另一类是利用目标函数的一阶或二阶导数信息的无约束优化方法，如梯度法、牛顿法、共轭梯度法、变尺度法，称为间接搜索法。

一类是只利用目标函数值信息的无约束优化方法，如坐标轮换法、鲍威尔法，称为直接搜索法；另一类是利用目标函数的一阶或二阶导数信息的无约束优化方法，如梯度法、牛顿法、共轭梯度法、变尺度法，称为间接搜索法。? 基本思想坐标轮换法（变量轮换法、交替法、降维法）将 将n 维无约束优化问题转化为n 个沿坐标轴方向e i(i=1, 2, … , n) 的一维优化问题来求解，并记完成n次一维搜索为一轮。若一轮搜索后未得到满足精度要求的最优点，次一维搜索为一轮。若一轮搜索后未得到满足精度要求的最优点，一 一 则继续下 轮迭代搜索 。 如此反复 ， 直至得到满足精度要求的最优点为止。在每一轮搜索中，每次迭代仅对n元函数的一个变量沿其坐标轴方向进行一维搜索，其余元函数的一个变量沿其坐标轴方向进行一维搜索，其余n-1个变量均保持不变，再依次轮换进行一维搜索的坐标轴，直至完成沿个变量均保持不变，再依次轮换进行一维搜索的坐标轴，直至完成沿n 个坐标轴方向的n 次一维搜索。x 2X 0 (1)X 2 (1)x 10X 1 (1)点 取初始点X (0) =X 0 (1) ， x 1 坐标轴方向的单位向量S 1 (1) =e 1 =[1 0] T ，x 2 量 坐标轴方向的单位向量S 2 (1) =e 2 =[0 1] T 。

X 1 (1) =X 0 (1) +α 1 (1) S 1 (1)直线搜索方法,无约束优化方法,约束优化方法， ， X 2 (1) =X 1 (1) +α 2 (1) S 2 (1)X 1 (1) =X 0 (1) +α 1 (1) e 1 (1)= [x 1 (0) x 2 (0) ] T + α 1 (1) [1 0] TX 2 (1) =X 1 (1) +α 2 (1) e 2 (1)= [x 1 (1) x 2 (1) ] T + α 2 (1) [0 1] T第一轮迭代搜索：判断是否满足迭代收敛准则：|| X 2 (1) – X 0 (1) ||≤ε ε ？ ？若满足，则输出最优解，否则，继续下一轮迭代搜索。X i (k) =X i-1 (k) +α i (k) e i (k)( k— 迭代轮次，i— k 轮迭代的第i 次一维搜索α i (k) — 一维搜索求得的最优步长）|| X n (k) – X 0 (k) ||≤ε ε ？ ？? 计算步骤与算法框图1 ）任选初始点X (0) =X 0 (1) = [x 1 (0) x 2 (0) … x n (0) ] T ，给定迭代收敛精度，给定迭代收敛精度ε ε ，i = 1 ，k = 1 。

2 ）置n 个坐标轴方向向量为单位向量，即e 1 =[1 0 … 0 ] T ， ， e 2 =[0 1 0 … 0 ] T ，… ， ， e n =[0 … 0 1] T 。3 ）按如下迭代计算公式进行迭代计算X i (k) =X i-1 (k) +α i (k) e i (k)( k— 迭代轮次，i— k 轮迭代的第i 次一维搜索i =1 ，2， ， … ，n ）判 4 ） 判断是否满足迭代收敛准则|| X n (k) – X 0 (k) ||≤ε ε ？ ？若满足，则输出最优解: X*= X n (k) ，f*= f (X*)否则，令X 0 (k+1) = X n (k) ， ，k ? ? k+1 ，返回3 ）。单纯形替换法? 基本思想通过计算出若干点处的函数值，对其大小进行比较，可以看出函数值变化的大致趋势，从而可以寻求使函数值下降的搜索方向。在通过计算出若干点处的函数值，对其大小进行比较，可以看出函数值变化的大致趋势，从而可以寻求使函数值下降的搜索方向。在n 维空间中，由n+1 个不同点顺序相连，就可以一 一 n —— 构成 个具有n+1 个顶点的多面体 称之为单纯形 。

计算函数在这n+1个顶点的函数值，并进行比较，据此来确定有利的搜索方向和步长，找到一个比较好的点来取代单纯形中较差的那个顶点，从而组成了一个新的单纯形，并用之取代原来的单纯形。如此下去，新单纯形不断地向目标函数的极小点靠近，直到搜索到极小点为止。个顶点的函数值，并进行比较，据此来确定有利的搜索方向和步长，找到一个比较好的点来取代单纯形中较差的那个顶点，从而组成了一个新的单纯形，并用之取代原来的单纯形。如此下去，新单纯形不断地向目标函数的极小点靠近，直到搜索到极小点为止。? 计算步骤1）构造初始单纯形选初始点）构造初始单纯形选初始点X 0 ，和步长h 。从X 0 出发沿各坐标轴方向分别走步长出发沿各坐标轴方向分别走步长h ，得到n 个顶点X i (i=1, 2, … , n) ，与X 0 构成初始单纯形。构成初始单纯形。X 0x 2x 1X 1X 22 ）计算各顶点的函数值f i = f (X i ) (i=0, 1, 2, … , n)3 ）比较函数值大小，确定最好点X L 点 、最差点 X H 和次差点X G ，即:f L = f (X L ) =min{ f i : i = 0, 1, 2, … , n }X f 0 1 f H = f (X H ) =max{ f i : i = 0, 1, 2, … , n }f G = f (X G ) =max{ f i : i = 0, 1, 2, … , n; i ≠H }4 ）检验是否满足迭代收敛条件|( f H – f L ) / f L | ≤ ε ε ?若满足，则结束迭代计算，并输出X*= X L 和 和 f* = f L否则，转下一步。

5 ）计算除X H ” 点外的各点的“重心” X n+1 ，即X n+1 = (∑X i –X H ) / n 计算反射点： ： X n+2 = 2X n+1 –X H 和f n+2 = f (X n+2 )当 当 fL≤ f n+2 < f G 时，以X n+2 代替X H ， ， f n+2 代替代替 f H 到 ，构造新的单纯形，然后返回到 3 ）。X 0x 2x 1X 1X 2X HX LX GX n+1X n+26 ）扩张：当 f n+2 < fL时，取 扩张点X n+3 ，即X n+3X n+3 = X n+1 + α α (X n+2 – X n+1 )(α α=1.2 ～2.0 )算 并计算 f n+3 = f (X n+3 ) 。 若 f n+3 < f n+2 ，则以X n+3 代替X H ， ， f n+3 代替f H ，构造一个新的单纯形；否则，以X n+2 代替代替X H ， ， f n+2 代替f H 到 ，构造新的单纯形；然后返回到 3 ）。7 ）收缩：当 f n+2 ≥ fG时，则需收缩。若时，则需收缩。若 f n+2 < f H ，则取 收缩点X n+4 ：X n+4 = X n+1 + β β (X n+2 – X n+1 ) （ （ β β =0.5） ）f n+4 = f (X n+4 )否则，以X H 代替上式中的X n+2 ， 计算 收敛点X n+4 ：X n+4 = X n+1 + β β (X H – X n+1 )f n+4 = f (X n+4 )x 2X 2X LX n+1X n+2X n+3X n+4X n+4X 0x 1X 1X HX G若 若 f n+4 < f H ，则以X n+4 代替X H ， ， f n+4 代替f H ，形成新的单纯形，然后返回到，形成新的单纯形，然后返回到 3 ）；否则转下一步8 ）。

8 ）缩边：将单纯形向X L 缩边，可以将各向量( X i – X L ) ( i = 0, 1, 2, …, n )的长度都缩小一半，即X i = X L + 0.5 (X i – X L ) = 0.5 (X i + X L )( i = 0, 1, 2, …, n )到 形成新的单纯形，然后返回到 2 ）。鲍威尔（Powell ）法? 基本思想它是直接利用函数值来构造共轭搜索方向的一种共轭搜索方向法，又称鲍威尔共轭方向法或方向加速法。由于对于它是直接利用函数值来构造共轭搜索方向的一种共轭搜索方向法，又称鲍威尔共轭方向法或方向加速法。由于对于n 维正定二次函数，共轭搜索方向具有n 次收敛的特性，所一 一 ， 一 一 以鲍威尔法是直接搜索法中十分有效的 种算法 ， 般认为对于维数n ≤20的目标函数它是成功的。鲍威尔法是在研究具有正定对称矩阵的目标函数它是成功的。鲍威尔法是在研究具有正定对称矩阵H的二次函数的极小化问题时形成的，其基本思想是在不用函数导数信息的前提下，在迭代过程中逐次构造关于的二次函数的极小化问题时形成的，其基本思想是在不用函数导数信息的前提下，在迭代过程中逐次构造关于H 的共轭方向。

? 共轭方向的生成设是X (k) 和 和 X (k+1) 为从不同点出发，沿同一方向进行一维搜索而得到的两个极小点。为从不同点出发，沿同一方向进行一维搜索而得到的两个极小点。S (j)S (j) ▽f (X (k) )S (k)X (k)X (k+1)▽f (X (k+1) )[S (j) ] T ▽f (X (k) ) = 0[S (j) ] T ▽f (X (k+1) ) = 0具有正定对称矩阵H 的二次函数f (X) = 0.5 X T H X + B T X + C在 在 X (k) 和 和 X (k+1) 两点处的梯度可以表示为▽两点处的梯度可以表示为▽f (X (k) ) = H X (k) + B（1）▽）▽f (X (k+1) ) = H X (k+1 ）+ B（2 ） ( )（2 ）－ （1）得▽）得▽f (X (k+1) ) － ▽f (X (k) ) = H ( X (k+1) － － X (k) ) （3）（）（3 ）式两边同时左乘[S (j) ] T 得[S (j) ] T [ ▽f (X (k+1) ) －▽f (X (k) )]= [S (j) ] T H (X (k+1) －X (k) )=0即 [ S (j) ] T H ( X (k+1) － － X (k) ) = 0若取 S (k) = X (k+1) － － X (k) ， 那么， S (k) 和 和 S (j) 关于H 共轭，即[ S (j) ] T H S (k) = 0这说明：沿这说明：沿S (j) 方向分别对函数做两次一维搜索，得到两个极小点方向分别对函数做两次一维搜索，得到两个极小点X (k) 和 和 X (k+1) ，该两点的连线方向S (k) 与S (j) 是关于是关于H 共轭的方向。

x 2S (k)X (k)x 1X*S (j) X (k+1)上述生成共轭方向的方法完全可以推广到n维优化问题中，即在维优化问题中，即在n 维空间中，按上述方法可以生成n个相互共轭的搜索方向。个相互共轭的搜索方向。? 鲍威尔法的基本原理和迭代过程1 ）采用坐标轮换法顺次沿n个坐标轴方向进行一维搜索，然后以初始点个坐标轴方向进行一维搜索，然后以初始点X (0) 和终点X n (1) 构成一个向 新的方向 S (1) ，一 一 X (1) 并以此方向为搜索方向再作 维搜索得到极小点X n+1 。2 ）取始点X 0 (2) = X n+1 (1) ，并去掉原搜索方向组中的第一个方向，并去掉原搜索方向组中的第一个方向S 1 (1) =e 1 ，而将第一轮构成的向 新搜索方向 S (1)作为 最末一个方向 ，以此组成第二轮迭代的n 个方向。依此进行下去，直到获得满足迭代收敛精度要求的近似极小点为止。根据这一原理构造的迭代算法称为依此进行下去，直到获得满足迭代收敛精度要求的近似极小点为止。根据这一原理构造的迭代算法称为 鲍威尔基本算法。S (1)x 2X 1(1)X*S 1 (1)X 0(1)S 2 (1)x 1X 2(1)X 3(1)X 1(2)X 2(2)S (2)? 鲍威尔基本算法的缺点鲍威尔基本算法仅具有理论意义，不要说对于一般的函数，就是对于二次函数，它也可能失效。

因为在迭代过程中的鲍威尔基本算法仅具有理论意义，不要说对于一般的函数，就是对于二次函数，它也可能失效。因为在迭代过程中的n 个搜索方向有时会变成线性相关，而不能形成共轭方向，从而张不成n维空间，导致随后的迭代搜索在降维（“退化”）的空间中进行，可能求不到极小点，故需进行改进。那么，为什么会产生这种情况呢？又该如何去改进呢？维空间，导致随后的迭代搜索在降维（“退化”）的空间中进行，可能求不到极小点，故需进行改进。那么，为什么会产生这种情况呢？又该如何去改进呢？? 鲍威尔条件及鲍威尔修正算法鲍威尔基本算法中，每一轮迭代都是用连接始点和终点所产生的新搜索方向去机械地替换原方向组中的第一个搜索方向，而不做任何的“好坏”判断，这正是产生向量线性鲍威尔基本算法中，每一轮迭代都是用连接始点和终点所产生的新搜索方向去机械地替换原方向组中的第一个搜索方向，而不做任何的“好坏”判断，这正是产生向量线性“ “ ” ” 。 为 “ “ ” ” 相关而发生 退化 的根本原因所在 。 为了避免这种 退化现象的发生，鲍威尔对这一基本算法进行了修正。即在每一轮产生新的搜索方向现象的发生，鲍威尔对这一基本算法进行了修正。

即在每一轮产生新的搜索方向S (k) 后，首先判断原搜索方向组是否可以直接用作下一轮迭代的搜索方向组，若可以，则仍用之，否则，还要进一步判断原搜索方向组中哪个方向上函数值下降量最大或贡献最大，然后再用新搜索方向替换这个贡献最大的搜索方向，以保证逐次生成共轭方向，即每一轮迭代的搜索方向组线性无关。后，首先判断原搜索方向组是否可以直接用作下一轮迭代的搜索方向组，若可以，则仍用之，否则，还要进一步判断原搜索方向组中哪个方向上函数值下降量最大或贡献最大，然后再用新搜索方向替换这个贡献最大的搜索方向，以保证逐次生成共轭方向，即每一轮迭代的搜索方向组线性无关。第 对第 k 轮迭代，记f1= f (X 0 (k) )f2= f (X n (k) )f3= f (2X n (k) -X 0 (k) )及 △ m (k) = max { f (X i-1 (k) ) - f (X i (k) ) , i=1,2,…, n }，并 记，并 记 Sm( k )为 与 △m( k )相 对 应 的 搜 索 方 向 ，S (k) = X n (k) -X 0 (k)鲍威尔条件：若 f3< f1, 且( f 1 - 2f 2 + f 3 ) (f 1 - f 2 - △ m (k) ) 2 < 0.5 △ m (k) (f 1 - f 3 ) 2同时成立，则用S (k) 替代S m (k) ；否则，仍用原搜索方向组。

这就是；否则，仍用原搜索方向组。这就是 鲍威尔修正算法 ，通常所说的 鲍威尔算法就是指这一修正算法。就是指这一修正算法。? 鲍威尔算法的计算步骤及算法框图1 ）任选初始点X (0) =X 0 (1) 度 ，给定迭代收敛精度 ε ε 1 , ε ε 2 。取初始基本方向组为单位坐标向量系，即。取初始基本方向组为单位坐标向量系，即S i (1) =e i ( i = 1,2,...

（编辑：云计算网_宿迁站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!