文档介绍:无约束最优化方法无约束最优化方法?求解无约束最优化问题 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 1 x 2X 0 (1)X 1 (1) X 2 (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 2 (1) –X 0 (1) || ≤?? X 1 (1) = X 0 (1) +α 1 (1) e 1 (1) = [ x 1 (0) x 2 (0) ] T + α 1 (1) [1 0] T X 2 (1) = X 1 (1) +α 2 (1) e 2 (1) = [ x 1 (1) x 2 (1) ] T + α 2 (1) [0 1] T 第一轮迭代搜索: 若满足,则输出最优解,否则,继续下一轮迭代搜索。 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+1 个顶点的多面体——称之为单纯形。计算函数在这 n+1 个顶点的函数值,并进行比较,据此来确定有利的搜索方向和步长,找到一个比较好的点来取代单纯形中较差的那个顶点,从而组成了一个新的单纯形,并用之取代原来的单纯形。如此下去,新单纯形不断地向目标函数的极小点靠近,直到搜索到极小点为止。