常用的无约束优化方法

第四章 常用的无约束优化 方法王桂从

无约束优化问题的数学模型 min F ( x) n x [ x x x ] R 1 2 n 求上述问题最优解(x*, F*)的方法称为无约束优化方法 无约束优化方法理论研究开展的比较早，构成的优 化方法已很多，也比较成熟。使用无约束优化方法 ，不仅可以直接求无约束优化设计问题的最优解， 而且通过对无约束优化方法的研究给约束优化方法 建立明确的概念及提供良好的基础，某些优化设计 方法就是先把优化设计问题转化为无约束问题后， 再直接用无约束优化方法求解。 #

无约束优化问题的求解方法 解析法(间接法):用函数的一阶、二阶导数进行求解的算法 直接搜索法(直接法):只利用函数值求最优解的解法直接法 坐标轮换法

鲍威尔法梯度法 共轭梯度法 牛顿法 变尺度法

间接法

解析法的收敛速率较高，直接法的可靠性较高。 #

无约束优化方法的基本过程 从选定的某初始点x(k)出发，沿着以一定规律产生的搜索方向S(k) ,取适当的步长a(k) ,逐次搜寻函数值下降的新迭代点 x(k+1) ,使之逐步逼近最优点x* 。

初始点x(k) 、搜索方向S(k) 、迭代步长a(k)称为优化方法算法的三要素。其中以搜索方向S(k) 更为突出和重要，它从根本上 决定着一个算法的成败、收敛速率的快慢等

所以，一个算法的搜索方向成为该优化方法的基本标志，分析、确定搜索方向S(k)是研究优化方法的最根本的任务之一 #

4.1 坐标轮换法 坐标轮换法由D’esopo于1959年提出； 坐标轮换法是每次搜索只允许一个变量变化， 其余变量保持不变，即沿坐标方向轮流进行搜 索的寻优方法； 坐标轮换法把多变量的优化问题轮流地转化成 了单变量的优化问题。

属于直接搜索法。即只需要目标函数的数值信息而不需要目标函数的导数；#

4.1 坐标轮换法-基本原理 既可以用于无约束优化问题的求解，又可以经过适当的处理用于约束优化问题；

基本特征：将迭代方向 S 取为一系列按序号排列的坐标轴方向，通常都用单位矢量 ei 作为迭代的方向矢 量。对于n 维优化问题，当 n 个坐标轴方向依次取过 一次后，称为完成了一轮迭代。

基本原理：将一个 n 维的无约束最优化问题转化为一系列沿坐标轴方向的一维搜索问题来求解。在每一 次迭代中，只改变 n 个变量中的一个，其余变量固定 不动，因此常称为单变量法或变量交错法或降维法 #

4.1 坐标轮换法-迭代步长的确定(1) 最优步长在沿坐标轴方向的搜索中，利用一维优化方法来确定沿该方向 上具有最小目标函数值的步长，即：

min F ( x ( k ) aS ( k ) ) F ( x (

k ) a( k ) S ( k ) )(2) 加速步长先选择一个不大的初始步长 a0,在每次一维搜索中都是先沿正 向从 a 到 a0,开始做试探计算函数值，若函数值下降，则以倍 增的速度加大步长，步长序列为a0, 2a0, 4a0… 直到函数值保持 下降的最后一个步长为止。 在无约束优化问题求解中采用最优步长方法是方便的。

#

4.1 坐标轮换法-迭代过程第一轮迭代：(1) 任取一初始点x(0) 作为初始 点x0(1),先沿第一坐标轴的方 向e1=[1 0]T 作一维搜索，用一 维优化方法确定最优步长 1(1) ,得第一轮的第一个迭代点： x1(1) =x0(1) + 1(1) e1 (2) 以 x1(1) 为新起点，沿第二 坐标轴的方向e2=[0 1]T作一 维搜索，确定步长 2(1) ,得 第一轮的第二个迭代点： x2(1) =x1(1) + 1(1) e2

#

4.1 坐标轮换法-迭代过程第二轮迭代： x0(2) x2(1) x1(2) = x0(2) + 1(2) e1 x2(2) = x1(2) + 2(2) e2 依次类推,可进行第三轮、第 四轮…迭代注意：右上角括号内的数字表 示轮数，右下角数字表示该轮 中的第几个迭代点号

#

4.1 坐标轮换法-终止准则采用点距准则

(k ) (k ) x x n 0注意： 若采用点距准则或函数值准则，其中采用的点应 该是一轮迭代的始点和终点，而不是某搜索方向的 前后迭代点。

#

4.1 坐标轮换法-计算步骤⑴ 任选初始点 (0) (0) x ( 0) x1( 0) x 2 xn (1)T

作为第一轮的起点 x 0 ,置n个坐标轴方向矢量为单位坐标矢量：

1 0 e1 0 0

0 1 e 2 0 0

0 0 e n 0 1

#

⑵ 按照下面迭代公式进行迭代计算k) (k ) xi( k ) xi( 1 i ei

k为迭代轮数的序号，取 k=1,2,……; i为该轮中一维搜索的序号，取 i=1,2,……n 步长α一般通过一维优化方法求出其最优步长

⑶ 按下式判断是否终止迭代(k ) (k ) xn x0 ?

如满足，迭代终止， 并输出最优解 否则，令k←k+1 返回步骤(2)

最优解

x* x

(k ) n

F * F ( x*)#

例题4.1例题4.1 用坐标轮换法求目标函数2 F ( x) x12 x2 x1x2 10x1 4x2 60

的无约束最优解。给定初始点 x(0) =[0,0]T ,精度要求ε=0.1解：做第一轮迭代计算(1) (1) 沿e1方向进行一维搜索 x1 x0 1e1

(1) 式中， 为第一轮的起始点，取 x0 x x0

(1)

( 0)

x

(1) 1

0 1 1 1 0 0 0

按最优步长原则确定最优步长α1,即极小化

#

(1) min F ( x1 ) 12 10 1 60

暂且用微分学求导解出，令其一阶导数为零2 1 10 0

1 5

x

(1) 1

5 0

(1) 以 x

1 为新起点，沿 e2 方向一维搜索

x

(1) 2

x

(1) 1

5 0 5 2 e2 2 0 1 2

以最优步长原则确定α2,即为极小化

min F ( x ) 10 1 60(1) 1 2 1

2 4.5

x

(1) 2

5 4.5

#

对于第一轮按终止条件检验(1) (1) x2 x0 52 4.52 6.7

继续进行第2轮迭代计算。 计算5轮后，有 故近似优化解为(5) (5) x2 x0 0.0413

x* x

( 5) 2

7.9883 5 . 9981

F * F ( x*) 7.95025

#

入口 给定 x ,ε k←1 i←1(0)

坐 标 轮 换 法 的 流 程 图

xi( k ) x ( 0)沿ei方向一维搜索αi(k ) (k ) (k ) x x e i i 1 i i

x xi( k ) F←F(x)

i←i+1

-

i=n?

k←k+1

+(k ) (k ) xn x0 ?

-

x

(0)

x

(k) n

x* x*

+#

F F(x*)出口