当前位置：文档之家 › 第8章 无约束问题最优化方法

第8章 无约束问题最优化方法

  • 格式：ppt
  • 大小：922.50 KB
  • 文档页数：35

下载文档原格式

  / 35

合集下载

7(10)无约束最优化问题

7(10)无约束最优化问题
6
无约束最优化问题
三,极值的充分条件
定理2 充分条件) 定理2 (充分条件) 设函数 z = f ( x , y )在点( x0 , y0 ) 的某邻域内连续, 有一阶及二阶连续偏导数, 的某邻域内连续 有一阶及二阶连续偏导数 又 f x ( x0 , y0 ) = 0, f y ( x0 , y0 ) = 0, 令 fxx ( x0 , y0 ) = A, fxy ( x0 , y0 ) = B, f yy ( x0 , y0 ) = C,
18
无约束最优化问题
作业
习题7.10 (112页 习题7.10 (112页) (A)2. 3.(2) 6. (B) 1. 2. 6.
19
�
一元函数 f ( x , y0 ) 在点 x0 处取得有极小值 处取得有极小值, 表示动点 P ( x , y ) ∈ U ( P0 , δ ),且 P ( x , y )沿直线
17
无约束最优化问题
y = y0上, 并沿该直线 即沿平行于 轴的正负 并沿该直线(即沿平行于 即沿平行于Ox轴的正负
方向)趋向于 方向 趋向于P0 ( x0 , y0 )时, f ( x, y) > f ( x0 , y0 ). 它们的关系是: 它们的关系是 取得极大(小 值 f ( x , y ) 在点 ( x0 , y0 ) 取得极大 小)值 f ( x0 , y )和f ( x , y0 )分别在 y0点和x0点 取得极大(小 值 取得极大 小)值.
下半个圆锥面
x
点取极大值. 也是最大值). 在(0,0)点取极大值 (也是最大值 点取极大值 也是最大值 马鞍面
z
O
y
O
x
y
4
无约束最优化问题

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

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

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 ) ；否则，仍用 就是鲍威尔修正算法，通常所说的鲍威尔算法就是指这一修正算法。
• 鲍威尔算法的计算步骤及算法框图

无约束问题最优化方法

无约束问题最优化方法

向可以使函数值下降，只
x2
有在锐角所包含的范围搜
索才可以达到函数值下降
的目的，故坐标轮换法对 此类函数会失效。
脊线
x1
第二轮迭代，需要
x0(2) x2 (1)
依次类推，不断迭代，目标函数值不断下降，最后逼 近该目标函数的最优点。
终止准则
可以采用点距准则
注意： 若采用点距准则或函数值准则，其中采用的点应该是一轮
迭代的始点和终点，而不是某搜索方向的前后迭代点。
8.1.2坐标轮换法的计算步骤
⑴任选初始点
作为第一轮的起点 ，置n个坐标轴方向矢量为单位 坐标矢量：
已知初 始点 x（1） (1, 2, 3)T ，当 x(n1) x(1) 0.01时停止
迭代．
小结
坐标轮换法程序简单，易于掌握。但是计算效率比 较低，尤其是当优化问题的维数较高时更为严重。一 般把此种方法应用于维数小于10的低维优化问题。
对于目标函数存在
“脊线”的情况，在脊线
的尖点处没有一个坐标方
对于n维优化问题，如果只利用函数值求最优值的解法，称 为直接搜索法；
解析法的收敛速率较高，直接法的可靠性较高。
8.1 坐标轮换法
坐标轮换法属于直接法，既可以用于无约束优化问 题的求解，又可以经过适当处理用于约束优化问题求 解。
坐标轮换法是每次搜索只允许一个变量变化，其余 变量保持不变，即沿坐标方向轮流进行搜索的寻优方 法。它把多变量的优化问题轮流地转化成单变量（其 余变量视为常量）的优化问题，因此又称这种方法为 变量轮换法。此种方法只需目标函数的数值信息而不 需要目标函数的导数。
第8章 无约束问题最优化方法
➢无约束优化理论研究开展得较早，构成的优化方法巳很多 ，也比较成熟，新的方法仍在陆续出现。本章的内容与目的 是讨论几个常用无约束优化方法的基本思想、方法构成、迭 代步骤以及终止准则等方面问题。

第8章 无约束问题最优化方法

第8章 无约束问题最优化方法

8 ． 1 ． 3 计算举例
例 8-1 用变量轮换法求解
2 2 min f ( x) 3x12 2x2 x3 ，
( n 1) （1） T x (1) 0.01 时停止 已知初始点 x (1, 2, 3) ，当 x
迭代．
8.2
模式搜索方法
模式搜索方法 ( Pattern Search Method ) 是 R.Hooke 和 T.A.Jeeves 于 1961 年提出的 , 因此也称为 Hook-Jeeves 方法 , 此方法有明显的几何意义 , 为介绍这种方法 , 从求一个二元函 数的极小点谈起．这相当于寻找某个曲面的最低点 , 或者形象 地说 , 相当于从一座山岭的某处出发 , 设法走到附近某一盆地 的最低点 , 怎样才能尽快达到这一目标呢 ? 很显然 , 如果能找 到一条山谷 , 沿山谷行进是最好的方法． 模式搜索方法就是根据上述思想设计的．它由两部分组成 , 包括探测移动和模式移动． 利用这种算法建立的迭代点移动 不需要使用一维搜索技巧．
(1) (1) (1) (1) (1) (1) e2 ) f (t 2 ) , 则 置 t3 t3 t2 e2 ； 否 则 若 f (t 2 t2 e2 ； 否 则
置 t 3 (1) = t 2 (1) ．
(1) 重复以上过程， 最后得到 t n 1 ．
8 ． 2 ． 2 模式移动
8.3 可变单纯形法
可变单纯形法的基本思想是， 给定 R n 中的一个单纯 形， 求出 n +1 个顶点的函数值 , 并确定这些函数值中的 最大值、 次大 值和最小 值， 然后通过 反射 、扩张、 内 缩、缩边 等方 法（几种 方法 不一定同 时使 用）求出 一 个较好点，用它取代最大值的点，以构成新的单纯形， 通过多次 迭代 逼近极小 点， 迭代过程 中逐 渐地把单 纯 形向最优点移动．

无约束问题的最优化条件

无约束问题的最优化条件

f
(x)
f
(xk ) f
(xk )T
(x
xk )
1 (x 2
xk )T 2
f
(xk )(x
xk )
Q(k) (x)
f
(xk ) f
(xk )T (x xk )
1 2
(
x
xk
)T
2
f
(xk )(x xk )
令
Q(k) (x) x
0
f
( xk
)
2
f
(
xk
)(
x
xk
)
0
x xk (2 f (xk ))1f (xk ) xk Gk1gk
k 满足:
f (xk
dk ) 0
T f (xk k dk )gdk 0
ห้องสมุดไป่ตู้
d
T k 1
gd
k
0
14
a
5.3 牛顿法
自动化学院
15
a
一、牛顿迭代公式
牛顿法的基本思想是利用目标函数在当前迭代点 xk 处 的二次近似的极小点作为 f (x) 的近似极小点。
16
a
设 xk 是当前迭代点， 2 f (xk ) 正定，
5.1 无约束问题的 最优性条件
自动化学院
1
a
一、极小点的概念
1．局部极小点 2．严格局部极小点 3．全局（总体）极小点 4．严格全局（总体）极小点。 注：在非线性规划中，大多数算法都致力于求最优化 问题的局部极小点，一般求全局极小点极为困难，仅 当问题为凸规划时，局部极小为全局极小。
2
a
二、无约束问题最优性条件
的极小值,0.01,x(0)(0,0)T ,只迭代一次

第八章 无约束多维问题的最优化方法

第八章 无约束多维问题的最优化方法

5 共轭梯度法
共轭梯度法的迭代公式
设从xk出发，沿dk=-gk 方向作一维搜索到 xk+1点，并算 出xk+1点的梯度方向gk+1。由于gk+1 是沿等直面在该点的法 线方向，而dk是沿等直面在该点的切线方向，故(dk)Tgk+1= 0，即 gk+1Tgk=0，gk+1 与 gk 正交。 为了在 gk+1 和 gk 构成的正交系中确定共轭方向dk+1，令 dk+1 = -gk+1+k dk 即把共轭方向dk+1看成-gk+1与 dk的线性组合，k 为待定 系数。要使dk+1与dk 共轭，就应使 (dk+1)TGdk =0 而 (dk+1)TGdk =(-gk+1+kdk)TGdk =(-gk+1 kgk)TG(-gk ) =gk+1TGgk+k gkTGgk =0
T
0 T 4 100 1 50
T
1 1 2 2 4 0 100 0 4 100 50 2 f x 0

0 0
T
对照梯度法和牛顿法迭代公式，可以看出只相差一项 海赛矩阵的逆矩阵。因此，牛顿法是对梯度法的进一步修 正。事实上，梯度法是对目标函数f(x)在点xk的一阶(线性) 近似，而牛顿法是对f(x)在点xk 的二阶(二次)近似。
2 最速下降法
(1) 最速下降法以负梯度方向作为搜索方向并作一维搜索，因 此又称为“梯度法”，属于求导数的间接法。它的基本思想早 在1847年就已提出。尽管它本身不再被认为是一种有效的方法， 但它是许多优化方法尤其是二次收敛方法的基础。 各点的梯度一般各不相同，因此“最速下降方向”仅对某 一点附近而言，它具有局部性质。 当作一维搜索时，搜索方向是与目标函数等值线相切的， 而切点的梯度方向是与等值线正交的。因此，相邻两次搜索方 向相互垂直，搜索路径呈严重的“之”字形，特别是目标函数 接近二次型时更为明显。 可以利用梯度矢量在极值点为零这一重要性质设立收敛准 则 f(x*)

第三讲 无约束优化(多维无约束优化方法)


2019/10/21
5
1. 梯度法（最速下降法 ）
（2）迭代公式 ： X (k 1) X (k) k S (k) X k f X k
或
X (k1) X (k) k
f f
X k X k
f
X k


f ，f x1 x2
X (2) 1
S (1)
S为S（2）的共轭方向。
S即为S(1)的共轭方向。
2019/10/21
18
（2）共轭梯度法的基本原理
2）共轭方向的构造
S k1 f X k1 k S k
上式的意义是以新的负梯度方向 f X k1 ，加上原
负梯度的一部分k S k 来构造 S k1 。
2019/10/21
3
1. 梯度法（最速下降法 ）
数值迭代格式
X (k 1) X (k ) k S (k )
从数值迭代格式可以看出，构造一种算法的关键 是如何确定一个有利的搜索方向。
梯度方向是函数值上升最快的方向，负梯度 方向是函数值下降最快的方向。
2019/10/21
以负梯度方向作为搜索方向
4）牛顿法不能保证函数值稳定下降，严重时还会造 成点列发散导致迭代失败。
2019/10/21
1 27
3. 多维牛顿法（阻尼牛顿法）
问题的提出
因函数不一定是二次函数，基本牛顿法的步长因子 恒为1，有时会导致迭代发散而失效。
改进方法
仍取牛顿方向，但改用最优步长因子：
X (k1) X (k ) k [H ( X (k ) )]1f ( X (k) ) 一维搜索求最优步长
'X 0

最优化方法 powell法求解无约束优化问题

数学与计算科学学院实验报告
实验项目名称powell法求解无约束优化问题
所属课程名称最优化方法
实验类型算法编程
实验日期
班级
学号
姓名
成绩
附录1：源程序
附录2：实验报告填写说明
1．实验项目名称：要求与实验教学大纲一致。

2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。

3．实验原理：简要说明本实验项目所涉及的理论知识。

4．实验环境：实验用的软、硬件环境。

5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。

概括整个实验过程。

对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。

对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。

对于创新性实验，还应注明其创新点、特色。

6．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。

7．实验结论（结果）：根据实验过程中得到的结果，做出结论。

8．实验小结：本次实验心得体会、思考和建议。

9．指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。

无约束优化方法(最速下降法_牛顿法)

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

尽管对于机械的优化设计问题，多数是有约束的，无约束最优化方法仍然是最优化设计的基本组成部分。

因为约束最优化问题可以通过对约束条件的处理，转化为无约束最优化问题来求解。

为什么要研究无约束优化问题?（1）有些实际问题，其数学模型本身就是一个无约束优化问题。

（2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。

（3）约束优化问题的求解可以通过一系列无约束优化方法来达到。

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

根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。

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

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

无约束优化问题的一般形式可描述为：求n 维设计变量 []12Tn n X x x x R =∈使目标函数 ()min f X ⇒目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。

无约束优化问题的求解： 1、解析法可以利用无约束优化问题的极值条件求得。

即将求目标函数的极值问题变成求方程0)(min *=X f的解。

也就是求Ｘ＊使其满足解上述方程组，求得驻点后，再根据极值点所需满足的充分条件来判定是否为极小值点。

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

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

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

2、数值方法数值迭代法的基本思想是从一个初始点)0(X出发，按照一个可行的搜索方向)0(d搜索，确定最佳的步长0α使函数值沿)0(d 方向下降最大，得到)1(X 点。

04 无约束优化方法


F 1A C
向上的极小点，而非原函数的 -2 -1
0
1
2
3
x1
极小点。
解决办法：阻尼牛顿法。
7
二.阻尼牛顿法
1.迭代公式
沿牛顿方向-[H(X(k))]-1f(X(k))作一维搜索,迭代公式：
X (k1) X (k ) k [H ( X (k ) )]1f ( X (k ) )
其中λ k使
f ( X (k ) k s(k ) ) min f ( X (k ) k s(k ) )
S1
1 0 ,S2
0 1
正交不共轭
19
2.正定二次函数的特点
(1)正定二次二元函数的等值线是椭圆线簇,椭圆线簇的中心
即目标函数的极值点。
(2)过同心椭圆线簇中心作任意直线,此直线与诸椭圆交点处
的切线相互平行。
反之过两平行线与椭圆切点X(a)和
x2
X(b)的连线必通过椭圆的中心。因此
只要沿方向X(a)—X(b)进行一维搜索，
1、坐标轮换法具有程序简单，易于掌握的优点，但它的计
算效率较低，因此它虽然步步在登高，但相当于沿两个垂直方
向在爬山，路途迂迴曲折，收敛很慢，因此它适用于维数较低
(一般n<10)的目标函数求优。
2、有“脊线”的目标函数等值线的情形,沿坐标轴方向函数值
不一定下降。
脊线
x2
A
p
0
x1
13
五、练习 用最优步长法求解 f (X)=(x1-2)4+(x1-2x2)2的极小点。 初始点X(0)=[0,3]T，要求迭代一轮。 请注意沿坐标轴移动的方向。
22
二、迭代过程
以二维问题为例： ① X(0)
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

这里的单纯形指的是 n 维欧氏空间 R n 中具有 n +1 个顶 点的凸多面体．例如，一维空间的线段、二维空间的三角 形、三维空间的四面体等，均为相应空间的单纯形．
考虑无约束最小化问题：
min f ( x), x Rn
设 x(1) , x(2) ,, x(n1) 是构成单纯形的 R n 中的 n +1 个顶点，并 定义这些顶点中的最大值点 x( H ) ，次大值点 x (G ) 和最小值点 x ( L ) 为分别满足以下条件的点：
(2) (1) f ( x (1) e1 ) f ( x ) f ( x 1e1 ) min (2) (1) x x 1e1
(8-1)
其中， f ( x(1) e1 ) 是步长 的一 维函数， f ( x(1) e1 ) 的极小点 1 就 是 e1 方向上的最优 步长．上式表明：从 x (1) 出发，沿 e 1 进行一 维搜索，最优步长 为 1 ，可求得新点 x (2) ．显然新点 x (2) 与 x (1) 相比，只有 x 1 的坐标值不同． 类似地，以 x (2) 为出发点，沿第二 个坐标轴方向 e 2 进行一 维搜索，求出最 优步长 2 ，得新点 x (3) ：
(1) (1) (1) (1) (1) (1) e2 ) f (t 2 ) , 则 置 t3 t3 t2 e2 ； 否 则 若 f (t 2 t2 e2 ； 否 则
置 t 3 (1) = t 2 (1) ．
(1) 重复以上过程， 最后得到 t n 1 ．
8 ． 2 ． 2 模式移动
8． 2． 4
算法终止准则：
当步长 充分小 , 就认为 x ( k ) 在极小点附近了 , 终止 计算．因此终止准则为

其中 ε 是预先给定的精度．
(8-7)
8． 2． 5
算法步骤
1 ． 取 初 始 点 x (1) , 初 始 步 长 >0 , 精 度 要 求 ε >0 ， 令 t 1 = x (1) , k =1 ． 2 ． 对 于 i =1 , 2 , „ , n , 进 行 如 下 操 作 或 计 算 ： 如 果 f (ti ei ) f (ti ) , 则 令 ti 1 ti ei ；否 则 若 f (ti ei ) f (ti ) , 则 令 ti 1 ti ei ； 否 则 令 t i 1 t i ． 3 ． f ( t n 1 ) f ( x ( k ) ) , 则 令
8.3 可变单纯形法
可变单纯形法的基本思想是， 给定 R n 中的一个单纯 形， 求出 n +1 个顶点的函数值 , 并确定这些函数值中的 最大值、 次大 值和最小 值， 然后通过 反射 、扩张、 内 缩、缩边 等方 法（几种 方法 不一定同 时使 用）求出 一 个较好点，用它取代最大值的点，以构成新的单纯形， 通过多次 迭代 逼近极小 点， 迭代过程 中逐 渐地把单 纯 形向最优点移动．
在探测移动后 , 若 动，即令
(1) (1) f (tn ) f ( x ) , 则作模式移 1
(1) x (2) tn 1 ,
t
(2) 1
x
(2)
(x
(2)
x )
(1)
（ 8-4 ）
8． 2． 3
算法的基本思想
算法的基本思想是将探测移动和模式移动有机的结合在一起． 设已 得 到 x(k ) 和 t 1 (k ), 从 t1 (k) 出 发 , 沿 各 个 坐 标 轴 作 探 测 移 动 得 到 t2 (k ), t3 (k ),„ , tn +1 (k )．
(3) (2) (2) f ( x ) f ( x e ) min f ( x e2 ) 2 2 (3) (2) x x 2e2
(8-2)
就这样依次沿各 坐标轴方向进行 一维搜索，直到 n 个坐标轴 方向全部搜索一 遍，最后可得到 点 x ( n +1) ：
二、算法步骤 设 ei 为 第 i 个 坐 标 轴 的 单 位 向 量 ， 即
0 0 ei 1 — 第 i行 (i 1, 2, , n) 0 0
1 ． 给 定 初 始 点 x(1) (c1, c2 ,, cn )T ， 其 中 c1 , c2 ,, cn 为 常 数 ． 2 ． 从 x (1 ) 出 发 ， 先 沿 第 一 个 坐 标 轴 方 向 e 1 进 行 一 维 搜 索 ， 求 出 最 优 步 长 1 ， 得 新 点 x (2 ) ， 即
8.1
变量轮换法
在求解无约束非线性规划问题时， 如果遇到问题的目标函数不可导 或导函数的解析式难以表示时，人们一般需要使用直接搜索方法．同 时，由于这些方法一般都比较直观和易于理解，因而在实际应用中常 为 人 们 所 采 用 ．变 量 轮 换 法 又 叫 坐 标 轮 换 法 (Cyclic Coordinate Method) 就 是 一 种 最 简 单 的 直 接 搜 索 方 法 , 也 称 为 交 替 方 向 法 (Alternating Directions Method) ．
8 ． 1 ． 3 计算举例
例 8-1 用变量轮换法求解
2 2 min f ( x) 3x12 2x2 x3 ，
( n 1) （1） T x (1) 0.01 时停止 已知初始点 x (1, 2, 3) ，当 x
迭代．
8.2
模式搜索方法Leabharlann 模式搜索方法 ( Pattern Search Method ) 是 R.Hooke 和 T.A.Jeeves 于 1961 年提出的 , 因此也称为 Hook-Jeeves 方法 , 此方法有明显的几何意义 , 为介绍这种方法 , 从求一个二元函 数的极小点谈起．这相当于寻找某个曲面的最低点 , 或者形象 地说 , 相当于从一座山岭的某处出发 , 设法走到附近某一盆地 的最低点 , 怎样才能尽快达到这一目标呢 ? 很显然 , 如果能找 到一条山谷 , 沿山谷行进是最好的方法． 模式搜索方法就是根据上述思想设计的．它由两部分组成 , 包括探测移动和模式移动． 利用这种算法建立的迭代点移动 不需要使用一维搜索技巧．
(8-6)
分两种情况讨论： (1) 若 t 1 ( k ) ≠ x
(k)
, 则 t1 (k ) 是 由 上 一 次 的 模 式 移 动 得 到 的 , 而
（ 8.2.3 ） 式 表 明 该 模 式 移 动 使 目 标 函 数 值 上 升 ,即 模 式 移 动 失 败 ,应 将 t1 (k ) 退 回 到 x(k ) 处 , 即 令 t1 (k ) = x(k ),重 复 上 述 计 算 ． (2) 若 t 1 ( k ) = x ( k ) , 这 说 明 上 次 的 模 式 移 动 失 败 且 在 t 1 ( k ) 周 围 的 探 测 移 动 全 部 失 败 ． 这 是 由 于 步 长 过 大 的 原 因 引 起 的 ,应 减 少 步 长 ,再 重 复上述计算．
(k ) (k ) 如 果 f (tn ) ,则 作 模 式 移 动 ,即 令 1 ) f (t
(k ) t ( k 1) tn 1 ,
t
如果
( k 1) 1
t
( k 1)
(t
( k 1)
t
(k )
)
(8-5)
置 k = k +1 ， 重 复 上 述 计 算 ,
(k ) (k ) f (tn )， 1 ) f (t
8． 2． 1 探 测 移 动
这种移动是在某 个已知点附近 , 沿坐标轴 e i 方向进行 探测 , 其目的是获得一 个更小值的点． 取初始点 x (1) , 探测移动的具体过 程如下 : 记 t 1 (1) = x (1) , 先在坐标方向 e 1 上作探测， 设 是固定步 长， (1) 如果 f (t1(1) e1 ) f (t1(1) ) , 则沿 e 1 方向探测成功 , 置 t 2 t1(1) e1 ；否 则探 测失 败 , 考虑 相反 的方 向． 如 果 f (t1(1) e1 ) f (t1(1) ) , 则沿 e1 (1) (1) (1) 方向探测成功 , 置 t 2 t1(1) e1 ；否则探测失败 , 置 t 2 = t 1 ． (1) (1) 再 沿 e 2 方 向 进 行 探 测 ， 如 果 f (t 2 e2 ) f (t 2 ) ，则置
第8章
无约束问题最优化方法
关 于 “无 约 束 问 题 的极 值 条 件 ” 和 “下 降 迭 代 类 算法 ” ， 我们 已在第 6 章中 做过 介绍 ，本 章 介绍 几种 常用 的无 约束 条 件下 多变 量函 数的 最优 化方 法． 无约 束问 题的 最优 化方 法大 致分 为两 类：一类 在计 算过 程 中只 用 到 目标 函 数 值， 而 无需 计 算 导数 ， 通常 称 为 直接 搜 索 法； 另 一 类在 计 算 过程 中 需要 计 算 目标 函 数的 导 数 ，称 为 解 析法 或 使 用导 数 的 最优 化 方法 ． 各 种不 同 的无 约 束 问题 的 最 优化 方 法 中， 其 根 本不 同 之处 在 于 迭代 过 程中 选 择 的搜 索 方 向不 同 ． 变量 轮 换 法、 可 变单 纯 形 法和 模 式搜 索 法 等属 于 直 接搜 索 法 ，而 最 速 下降 法 、牛 顿 法 、共 轭 梯度 法 和 拟牛 顿 法 等属 于 后 一类 ． 我 们先 介 绍直 接 法 ，再 介 绍几 种 使 用导 数 的 方法 ．
( n 1) (n) f ( x( n ) en ) f ( x ) f ( x n en ) min ( n1) ( n) x x n en
(8-3)
从 初 始 点 x (1) 出 发 ， 经 上 述 n 个 坐 标 轴 方 向 的 一 维 搜 索 得 到 点 x ( n +1) ，我们说完成 了变量轮换法的 一次迭代． （ 3 ） 令 x (1) = x ( n +1) ，返回步骤 2 继续迭代． 以上步骤一直进 行到所得新点 x ( n +1) 满足给定精度为 止． 变量轮换法特点 是：基 本原 理 非常 简单 ，它 对 目标 函 数的 解析 性 质没 有特 别的 要 求 ， 适 用于 各 变量 之间 本质 上无 联 系或 沿各 坐标 轴方 向搜 索比 较 容易 的特 殊结 构 ，而对 一般 的目 标 函数 ，它的 收 敛速 度较 慢， 搜 索效 率低 ． 但是变量轮换法 的依次沿各坐标 轴方向寻优的思 想， 是多变 量函数寻优的一 种基本思想，在这 种思想的基础上，后又发展出 了模式搜索法（见 本章下一节）及旋 转方向法等（有兴 趣的读者 可参阅相关参考 文献） ．