当前位置：文档之家 › 常用无约束最优化方法(一)

常用无约束最优化方法(一)

  • 格式：doc
  • 大小：30.50 KB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

第三章 无约束最优化方法

第三章 无约束最优化方法

f x f x
*

所以函数f(x)在 x * 处取得局部极小值，称x *为
局部极小点。 而优化问题一般是要求目标函数在某一区域内 的全局极小点。 函数的局部极小点是不是一定是全局极小点呢？
5
第三章 无约束最优化方法
下凸的一元函数
可以证明凸规划问题的局部最小点就是其全局最小点。
6
第三章 无约束最优化方法
f x 0
x Rn

的问题。一般地，这是一个非线性方程组， 17 可对其采用迭代法求解之。
第三章 无约束最优化方法
下降迭代算法
算法：给定目标函数 f x 的极小点的一个初始估计点 x0 ， 然后按一定的规则产生一个序列 xk ，这种规则通常称 为算法。如果这个序列的极限恰好是问题（3-1）的极 小点 x* ，即
正定矩阵 设 Q是n×n 阶对称矩阵。
若 x Rn 且 x 0 都有 x T Q x 0 ，则称矩阵Q 是正定的 若 x R
n n
T x 都有 Q x 0 ，则称矩阵Q 是半正定的
若 x R 且 x 0 都有 xT Q x 0 ，则称矩阵Q 是负定的 若 x Rn 都有 x T Q x 0 ，则称矩阵Q 是半负定的
为正定的定义是：若对任何向量d (d!=0)，有
d T 2 f x* d 0
对称正定方阵 2 f x* 的检验方法是所有主子式均大于零。 二、迭代方法 求解 无约束最优化问题 T f x min x x1, x2 , , xn 的问题可以转变为求解n 元方程组
26
3-2
一维搜索（0.618法）
设给定一个较小的步长δ，从α=0开始，先计算φ(0)，然 后计算在 (1.618)0 的函数值φ(δ)；如果φ(δ)<φ(0)， 则讲步长δ增大1.618倍，得到一个新点 1.618 2.618 , 计算φ(2.618δ)；如果φ(2.618δ)仍小于φ(δ)，再继续增加 步长为原步长的1.618倍，如下图所示，从而得到一系列 j 点的αj的值为 '

无约束问题的最优化条件

无约束问题的最优化条件

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 ,只迭代一次

第三章 无约束最优化--梯度方法(1)

第三章 无约束最优化--梯度方法(1)

2 做直线搜索 zk 1 LS( zk , - gk ), 计算f k 1 f ( zk 1 ), gk 1 g ( zk 1 ); 3 判定终止准则H是否满足，若满足则打印最优解 z k+1 , f k+1， 终止。否则转2。 将最速下降法用于具有对称正定矩阵Q的二次函数： 1 T f ( z ) z Qz bT z c，可以推出步长公式来 : 2 设第 k 次迭代点为zk 。下面求zk 1的表达式:
f z k f z k 1 f z k f z k f zk
但λ到底取多大，没有统一的标准， λ取小了，收敛太慢，而λ取大 了，又会漏掉极小点。
1 T f ( z ) z Qz , 定理：对于二次函数 2
四 用于二次函数时的收敛速度
为了清除最优步长最速下降法中两个搜索方向正交的不良 后果，人们发明了不少方法，如： （1）选择不同初始点。
例如：对问题： min
取初点
为求 z1 ，沿 f z0 方向从 z0 出发求 f z 的极点，即在线 搜索 min f ( z0 tf z0 )
f ( z) x 25x T z0 2,2 f z0 104 , f z0 4,100T

2 T

* T z ( 0 , 0 ) z 然后再从 1开始迭代，经过10次迭代，近似得最优解
f ( z1 ) 3.686164 .
计算中可以发现，开始几次迭代，步长比较大，函数值下将降 较快但当接近最优点时，步长很小，目标函数值下降很慢。如 T ,0)T虽然后一初点较前一 果不取初点为 z0 (2,2) 而取 z0 (100 初点离最优点 z * (0,0)T 远，但迭代中不出现锯齿现象。这时：

第3章 无约束最优化方法 3-1 最速下降法 3-2 牛顿法

第3章 无约束最优化方法 3-1 最速下降法 3-2 牛顿法
2
1
u f ( x)u m u
T 2
2
u R
n


则从任意的初始点 x 0 出发，阻尼牛顿法产 生的迭代点列 满足： （1）当 x k 为有穷点列时，其最后一个点 为 f ( x) 的唯一极小点。 （2）当 x k 为无穷点列时，收敛到 f ( x) 的
第3.2节 Newton法及其改进
第3.1节 最速下降法（Steepest Method）



对于最速下降法的几点说明 （1）第2.6节中介绍的关于下降算法的收敛 性定理对最速下降法都是成立的 。 （2）目标函数在负梯度方向下降得最快只 是局部性质。 （3）锯齿现象 （4）改进策略：在计算的开始阶段使用最 速下降法，在迭代数次后，改用其他算法。
本节的主要内容：
（1）牛顿法的基本思想
（2）阻尼牛顿法
（3）带保护措施的阻尼牛顿法
（4）吉尔-默里稳定牛顿法
（5）信赖域方法（一）
第3.2节 Newton法及其改进

（1）牛顿法的基本思想： * 在目标函数f ( x)的极小点 x 的近似点 x k 附近将 f ( x) 二阶Tayler展开，用展开的二次 函数去逼近 f ( x)，将这个二次函数的极小点 * x 作为 的一个新的近似点 x k 1 ，依次下去， 用一系列二次函数的极小点 xk 1 去逼近 f ( x) 的极小点 x * 。
第3.2节 Newton法及其改进
设 f ( x)二次连续可微，则 f ( x) 在 x k 处的二次 近似为： 1 T f ( x) qk ( x) f ( xk ) f ( xk ) ( x xk ) ( x xk )T 2 f ( xk )( x xk ) 2 令

第3章 无约束最优化方法 3-1 最速下降法 3-2 牛顿法

第3章 无约束最优化方法 3-1 最速下降法 3-2 牛顿法
性定理对最速下降法都是成立的 。 n （2）目标函数在负梯度方向下降得最快只
是局部性质。 n （3）锯齿现象 n （4）改进策略：在计算的开始阶段使用最
速下降法，在迭代数次后，改用其他算法。
第3.1节 最速下降法（Steepest Method）
n [引理3.2]（康德洛维奇Kntorovich不等式）
第3.2节 Newton法及其改进
n [推论3.8]设 且对任意的 在水平集
在开凸集D上二阶连续可微， ，存在常数 ，使得
上满足
则从任意的初始点 出发，牛顿法产生的迭
代点列 满足
，且收敛到
的唯一极小点。
第3.2节 Newton法及其改进
n 阻尼牛顿法的优点与缺点： 阻尼牛顿法克服了牛顿法要求初始点充分靠
n
，则d是下降方向；
n
，则 是下降方向。
第3.2.4节 吉尔-默里稳定牛顿法
n Gill-Murray稳定牛顿法的基本思想： n 当Hesse矩阵 在迭代点
处为不定矩阵时，对其进行强迫正 定的 分解；当 趋于零时， 采用负曲率方向使函数值下降。
第3.2.4节 吉尔-默里稳定牛顿法
n [算法3.15]（求负曲率方向的算法）
得到方向 ，令
。
n （6）精确线性搜索求 ，且令
n （7）若
，则进行步（8）；否则，
令
，转步（2）。
n （8）输出
，停止计算。
第3.2.4节 吉尔-默里稳定牛顿法
n [定理3.18]设 二阶连续可微，且存在
，使得
为有界闭
凸集。假定在吉尔-默里稳定牛顿法中取
，且初始点
，则吉尔-默里稳
定牛顿法产生的迭代序列 满足：

运筹学第15讲 约束最优化方法 (1)

运筹学第15讲 约束最优化方法 (1)

第六章 约束最优化方法
6.1 Kuhn-Tucker 条件
一、等式约束性问题的最优性条件： 考虑 min f(x) s.t. h(x)=0 回顾高等数学中所学的条件极值： 问题 求z=f(x,y) 在ф(x,y)=0 条件下的极 值。 即 min f(x,y) S.t. ф(x,y)=0 引入Lagrange乘子：λ
充要条件是
⎧ min ∇ f ( x ) T d ⎪ A 1d ≥ 0 ⎪ ⎨ Ed = 0 ⎪ ⎪ | d j |≤ 1 , j = 1 , L n ⎩ 0。
的目标函数最优值为
第六章
6.2 既约梯度法
显 然 d = 0 是 可 行 解 , 所 以 P1的 最 优 值 必 ≤ 0 。 1 o 若 目 标 函 数 的 最 优 值 < 0 , 则 d 为 ( P )的 下 降 可 行 方 向 ； 2 o 若 目 标 函 数 的 最 优 值 = 0， 则 x 为 K − T 点 。 < 确定一维搜索的步长： 设 x( k )是 可 行 解 , d ( k ) 为 下 降 可 行 方 向 , 求 λ k 使 x( k + 1 ) = x( k ) + λ k d ( k ) . ⎧ m in f ( x( k ) + λ d ( k ) ) ⎪ ⎪ s .t . A ( x( k ) + λ d ( k ) ) ≥ b λk满 足 : ⎨ ⎪ E ( x( k ) + λ d ( k ) ) = e ⎪ ⎩ λ ≥ 0 $ = b − A x( k ) , d $ = A d (k), 显 然 b $ < 0. 令b 2 2 2 利 用 定 理 1可 得 λ 的 上 限 λ m a x $i ⎧ b $ i < 0} ⎪ m in { $ | d = ⎨ di ⎪ +∞ ⎩ $< 0 d $≥ 0 d

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

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

step4. 若 || f ( xk1) || ,停止，x* xk1 ;
否则，令 k : k 1, 转step 2 。
14
➢算法框图
给定初始点x0和精度 || f ( x0 ) ||
停止，输出x1
否
是
| x1 x0 |
是 停止，输出x0
否 否
2 f (x0) 0
计算x1
x0
f ( x0 ) 2 f (x0)
1
13 62
x2
x1
1d 1
(
36 , 31
8 31
)T
7
三、最速下降法的特点
1.性质. 设 f ( x) 有一阶连续偏导数，若 步长 满足 k
f ( xk d k ) min f ( xk d k )
k
则有 f ( xk d k )T d k 0。 k
证明：令 ( ) f ( xk d k )，所以
5
一、梯度法（最速下降法）：
1. 搜索方向：d k f ( xk ) ,也称为最速下降方向；
2. 搜 索 步 长: k 取 最 优 步 长, 即 满 足
f (xk
kd k )
min
f
(xk
d k ) 。
二、梯度法算法步骤：
1. 给定初始点 x1 Rn ,允许误差 0, 令k 1。
2. 计算搜索方向 d k f ( xk ) ;
Step3. 令 xk 1 xk kd k , 其中tk : f ( xk kd k ) min f ( xk d k )。
24
Step 4. 判断 xk 1 是否满足终止准则： yes: 计算 stop, 则x* : xk1
No : 转 step 5 。

非线性规划-无约束问题的最优化方法

非线性规划-无约束问题的最优化方法

f x( ) + l e1 = 3( + l ) + 2? 22 1
1
(
)
2
32 = 3( + l ) + 17 1
2
fl ' = 0 ? l 1
- 1
轾 轾 1 1 犏 犏 2 1 x( ) = x( ) + l e1 = 犏 + (- 1)犏 = 2 0 犏 犏 犏 犏 3 0 臌 臌
轾 0 犏 犏 ? f x(2) 2 犏 犏 3 臌
第 二 节 最
二、最速下降法的算法步骤
速 下
降 法
第1步：给定初始点 x(0)，及终止误差 e > 0 ，令k =0 第2步：求梯度向量的范数 Ñ f (x(k )) 若 ? f (x(k )) 停止计算，输出x e ，停止计算，输出 (k)作为极小点的近
p( ) = - f x( )
k k
似值，否则转到下一步。 似值，否则转到下一步。 第3步：构造负梯度方向
第 一 节
一、基本思想
变
量
轮 换
法
认为最有利的搜索方向是各坐标轴的方向， 认为最有利的搜索方向是各坐标轴的方向，因此它轮流 按各坐标的方向搜索最优点。 按各坐标的方向搜索最优点。 过程：从某一个给定点出发，按第 个坐标轴 个坐标轴x 过程：从某一个给定点出发，按第i个坐标轴 i的方向搜 索时，假定有 个变量 则只有x 在变化，其余(n-1)个变量 个变量， 索时，假定有n个变量，则只有 i在变化，其余 个变量 都取给定点的值保持不变。这样依次从 做了n次单变 都取给定点的值保持不变。这样依次从x1到xn做了 次单变 量的一维搜索，完成了变量轮换法的一次迭代。 量的一维搜索，完成了变量轮换法的一次迭代。

最优化方法解可新

最优化方法解可新

最优化方法解可新最优化问题是数学建模中一个重要的问题类别，它的主要目标是在给定一些约束条件下找到一个使得目标函数取得最大或最小值的最优解。

最优化方法是解决这类问题的一种有效手段，通过对问题进行数学建模和算法求解，可以得到最优解或近似最优解。

最优化问题可以分为无约束优化和有约束优化两类。

在无约束优化问题中，目标函数的优化不受约束条件的限制；而在有约束优化问题中，目标函数的优化需要满足一定的约束条件。

下面将分别介绍无约束优化和有约束优化的最优化方法。

一、无约束优化的方法：1. 梯度下降法（Gradient Descent）：梯度下降法是最为常用的无约束优化方法之一。

它通过迭代的方式不断地沿着目标函数梯度的反方向更新参数，直至达到收敛条件。

梯度下降法的核心思想是利用函数的导数信息进行搜索，从而找到函数的最小值点。

2. 牛顿法（Newton Method）：牛顿法是一种基于函数局部二阶泰勒展开的优化方法。

它通过迭代的方式利用目标函数的一阶和二阶导数信息来求解最优解。

牛顿法在每次迭代时通过求解线性方程组来计算更新的步长，因此通常具有更快的收敛速度。

3. 拟牛顿法（Quasi-Newton Method）：拟牛顿法是对牛顿法的改进，它通过估计目标函数的二阶导数信息来近似求解最优解。

拟牛顿法不需要计算目标函数的二阶导数，而是通过迭代更新一个代表二阶导数信息的矩阵。

拟牛顿法比牛顿法更加稳定和易于实现，因此被广泛应用于实际问题中。

二、有约束优化的方法：1. 线性规划（Linear Programming）：线性规划是求解线性约束下的最优解的一种方法。

它的目标函数和约束条件均为线性函数，可以利用线性规划的特殊结构进行高效求解。

线性规划在工程、经济和管理等领域有广泛应用，如生产调度、资源分配等问题。

2. 非线性规划（Nonlinear Programming）：非线性规划是求解非线性约束下的最优解的方法。

它的目标函数和/或约束条件为非线性函数，常常需要使用数值优化方法进行求解。

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

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

赋以0.618。
2 ,
；并计算其对应
的函数值。 3）根据区间消去法原理缩短搜索区间。为了能用原来的 坐标点计算公式，需进行区间名称的代换，并在保留区间 中计算一个新的试验点及其函数值。
如果
令 b , , f f 记N0=0； 2 2 1 2 1 如果 ，则新区间＝ ，
2
2

图2-5 黄金分割法
• 黄金分割法要求插入两点： a1 a (1 )(b a), f1 f (a1 )
a2 a (b a), f 2 f (a2 )
黄金分割法的搜索过程：
1）给出初始搜索区间及收敛精度 2）按坐标点计算公式计算 1
，将
在搜索区间内[a,b] 任取两点a1、b1，令f1＝f（a1）， f2＝f（b1） • (1)如f1<f2, 则缩小的新区间为[a,b1]; • (2)如f1>f2, 则缩小的新区间为[a1,b]; • (3)如f1=f2, 则缩小的新区间为[a1,b1]
f(b1) f(a1) f(a1) f(b1) f(a1) f(b1)
a
a1

b
a
a1
b1 b
a
a1
b1
b
§3.2 一维搜索方法
黄金分割法： • 黄金分割法适用于[a,b]区间上的任何单谷函数求极小值问题。对 函数除要求“单谷”外不作其他要求，甚至可以不连续。因此，这种 方法的适应面相当广。 • 黄金分割法也是建立在区间消去法原理基础上的试探方法。 • 在搜索区间内[a,b]适当插入两点，将区间分成三段；利用区间消 去法，使搜索区间缩小，通过迭代计算，使搜索区间无限缩小，从而 得到极小点的数值近似解。 •

第五章 无约束优化方法

第五章 无约束优化方法
0 1 2 1 4 2 10
由（5.3）得 X (1) X (0) [H ( X (0) )]1 F ( X (0) ) 0 3 1
S (0) 1 4,10T 0.3714 ,0.9285 T 10.770329
2 2 例 5-3 试用牛顿法求例5-1给出的目标函数 f ( X ) x1 x2 x1 x2 4x1 10x2 60的极小值， ( 0) T 设初始点 X (0) [ x1(0) , x2 ] [0，0]。 2 f 2 f
f ( X ) f ( X ) T 解： f ( X ( 0) ) , 4,10 x 2 x1
(0)
6 8
H 1F
X (k ) X*
X
X (1) 6 8
T
(1)
X
S
( 0)
x1(1) 0 0.3714 0.3714 0.9285 (1) 0 0 . 9285 x2
f ( X ) f ( X ) T 解： f ( X ) , 2 x1 x 2 4,2 x 2 x1 10 x 2 x1 2 2 f ( X ( 0) ) f ( X ( 0) ) ( 0) 2 2 f ( X ) x x (4) (10) 10.770329 1 2
即为最优点，只迭代一次就达到了X*。
图5.8牛顿法的修正
• 5.3.2 牛顿法的特点
由上述可见，当目标函数为二次函数时，收敛很快，属于二阶收敛，是目前算法中最快的 一种。即使目标函数不是二次函数，当初始点选得好时，也会很快收敛。但如果目标函数 非凸，初始点选择不当有可能远离极小点或导致不收敛（图5.8）。基于这种原因，为保 证每次迭代下降，对古典的牛顿法要做些修改，于是便出现了修正牛顿法。其修正方法是 在 X ( k ) 沿牛顿方向做一次一维搜索，避免远离极小点 X (k 1) X (k ) k [H ( X (k ) )]1 F ( X (k ) )

无约束优化模型

无约束优化模型
其中[fiminu的]opt(6)=0（缺省）:拟牛顿法BFGS公式； opt(6)=1:拟牛顿法DFP公式； opt(6)=2:最速下降法。（控制搜索方向）
其中[fiminu的]opt(7)=0 （缺省）:混合二次，三次多项式插值； opt(7)=1：三次插值。（控制步长的一维搜索）。
任务：用三种不同算法求f(x,y)= 10 (y0 x2)2(1x)2
法 , 割线法 .
或者插值方法
: 对 f ( x k d k ) 采帮用二次
插值函数 f ( x k d k ) q ( ) a 2 b c
其中 a , b , c 可求 q ( 0 ) f ( x k ), q ' ( 0 ) f ( x k ) T d k ,
q ( ) f ( x k d k ) 确定 , 而 的最优值取 q ( ) 达到
的最优解，初始值选为(-1.9,2),比较算法的优劣。
四：产销量模型和经济增长模型的求解。
1：产销量模型的求解
（1）：分析：
求maxz(x1,x2),转化为m 求inz(x1,x2);
先求初始:先 值忽略成,并 本令p1, p2中较小系数 0. 为
求z1 b1a11x1x1b2 a22x2x2的驻点 ,
技术水平不像资金，劳动力那样容易定量化，作为初步的 模型，可认为技术水平不变，只讨论产值与资金，劳动力 之间的关系;在资本主义初期，这模型应该有意义.目的寻 求产值与资金，劳动力之间的关系。
（1）：假设变量：设Q，K，L分别表示产值，资金劳动
力，求Q（K，L）。
（2）建模：
A：产值依赖于每个劳动力的投资强度，并且与劳动 力数量成正比（G表示某一函数）
fu n ctio n [f,g]= f(x)

5 常用无约束最优化方法

5 常用无约束最优化方法

0.22152 f ( X 1 ) 0.06134 ， g 2 f ( X 2 ) ， g 2 0.91335． 0.88008
因为
T g1 g0 0.0000， T g 2 g1 0.0000，
说明相邻两个搜索方向是正交的．
有关说明
最速下降法的优点是算法简单，每 次迭代计算量小，占用内存量小， 即使从一个不好的初始点出发，往 往也能收敛到局部极小点，但它有 一个严重缺点就是收敛速度慢． 沿负梯度方向函数值下降很快的说法，容易使人们产生 一种错觉，认为这一定是最理想的搜索方向，沿该方向 搜索时收敛速度应该很快，然而事实证明，梯度法的收 敛速度并不快．特别是对于等值线（面）具有狭长深谷 形状的函数，收敛速度更慢．其原因是由于每次迭代后 下一次搜索方向总是与前一次搜索方向相互垂直，如此 继续下去就产生所谓的锯齿现象．即从直观上看，在远 离极小点的地方每次迭代可能使目标函数有较大的下降， 但是在接近极小点的地方，由于锯齿现象，从而导致每 次迭代行进距离缩短，因而收敛速度不快．
第 五 章 常 用 无 约 束 优 化 方 法
在基本迭代公式 X k 1 X k tk Pk 中，每次迭代搜索方向 Pk 取为目标函数 f (X )的负梯度方向，即 Pk f ( X k )，而 每次迭代的步长 t k 取为最优步长，由此所确定的算法 称为最速下降法．
第 五 章 常 用 无 约 束 优 化 方 法
f ( X * ) f ( X ) （5.2）
成立．点 X *就是问题（5.1）的全局最优点．但是， 大多数最优化方法只能求到局部最优点．这个矛盾对 于实际问题来讲一般容易解决，因为根据问题的实际 意义多半可以直接判定用优化方法求出的局部最优解 是否为全局最优解．但在理论上这是个比较复杂的问 题，本书不涉及． 无约束优化方法是优化技术中极为重要,它不仅可以直 接用来求解无约束优化问题，而且很多约束优化问题 也常将其转化为无约束优化问题，然后用无约束优化 方法来求解．同时，有些无约束优化方法只需略加处 理，即可用于求解约束优化问题．

4 无约束最优化方法-直接搜索法

4 无约束最优化方法-直接搜索法

7）收缩：当 fn+2≥ f
G
时，则需收缩。 （ =0.5）
若 fn+2 < fH，则取收缩点Xn+4 ： Xn+4 = Xn+1 + (Xn+2 – Xn+1)
fn+4 = f (Xn+4 )
否则，以XH代替上式中的Xn+2 ， 计算收敛点Xn+4 ： Xn+4 = Xn+1 + (XH – Xn+1) fn+4 = f (Xn+4 )
坐标轮换法（变量轮换法、交替法、降维法）
• 基本思想
将 n 维 无 约 束 优 化 问 题 转 化 为 n 个 沿 坐 标 轴 方 向 ei (i=1, 2, … , n)的一维优化问题来求解，并记完成n次一 维搜索为一轮。若一轮搜索后未得到满足精度要求的最优点， 则继续下一轮迭代搜索。如此反复，直至得到满足精度要求 的最优点为止。在每一轮搜索中，每次迭代仅对 n元函数的 一个变量沿其坐标轴方向进行一维搜索，其余 n-1个变量均 保持不变，再依次轮换进行一维搜索的坐标轴，直至完成沿 n个坐标轴方向的n次一维搜索。
若满足，则结束迭代计算，并输出 X * = XL 和 f 否则，转下一步。 5）计算除XH点外的各点的“重心” Xn+1 ，即 Xn+1 = (∑Xi –XH) / n
*
=f
L
计算反射点： Xn+2 = 2Xn+1 –XH
和
fn+2 = f (Xn+2 ) 当 f L ≤ fn+2 < fG 时，以Xn+2 代替XH ， fn+2 代 替 fH ，构造新的单纯形，然后返回到 3）。

第三章非线性规划无约束问题的最优化方法

第三章非线性规划无约束问题的最优化方法

x0
0p 0
1.919877 还需要经过10次迭代才
能满足精度要求
0.003070
第三节 牛顿法
3. 牛顿法的缺点： 牛顿法要求初始解离最优解不远，若初始点选得离最优解太
远时，牛顿法并不能保证其收敛，甚至也不是下降方向。因此， 常将牛顿法与最速下降法结合起来使用。前期使用最速下降法， 当迭代到一定程度后，改用牛顿法，可得到较好的效果。 4. 修正牛顿法 基本思想： 保留了从牛顿法中选取牛顿方向作为搜索方向，摒弃其步长恒 为1的做法，而用一维搜索确定最优步长来构造算法。
2
2
0
2e2 2 3
00 21 0
03
f x3 9
第二节 最速下降法
再从x(3)点 出发，沿x3轴方向e3进行一维搜索：
0 x 3 e3 0
3
00 00 13
f x 3 e3
32
f' 0 x4 x3
3
3
0
3e3 0 0
f x4 0
第二节 最速下降法
因为 x 1
x 4 ，0故.0以1 x(4)点作为新的x(1) ，进行新一轮迭代。
0
1 33 22
f x0
p0
52 5
42
f' x0
p0 5 5 0
22
01
第三节 牛顿法
x1 x0
1 p0 3
2
3
f x1
14
12 2
0
30
12 1 2
2
f x1
所以选取 x* x 1
1 3 作为极小点。 2
第三节 牛顿法
6. 修正牛顿法的缺点： 修正牛顿法虽然比牛顿法有所改进，但也有不足之处：
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

项目三 常用无约束最优化方法（一）
[实验目的]
编写最速下降法、Newton 法（修正Newton 法）的程序。

[实验学时]
2学时
[实验准备]
1．掌握最速下降法的思想及迭代步骤。

2．掌握Newton 法的思想及迭代步骤；
3．掌握修正Newton 法的思想及迭代步骤。

[实验内容及步骤]
编程解决以下问题：【选作一个】
1．用最速下降法求
22120min ()25[22]0.01T f X x x X ε=+==，，，．
2．用Newton 法求
22121212min ()60104f X x x x x x x =--++-，
初始点
0[00]0.01T X ε==，，．
最速下降法
Matlab 程序：
clc;clear;
syms x1 x2;
X=[x1,x2];
fx=X(1)^2+X(2)^2-4*X(1)-6*X(2)+17;
fxd1=[diff(fx,x1) diff(fx,x2)];
x=[2 3];
g=0;
e=0.0005;
a=1;
fan=subs(fxd1,[x1 x2],[x(1) x(2)]);
g=0;
for i=1:length(fan)
g=g+fan(i)^2;
end
g=sqrt(g);
step=0;
while g>e
step=step+1;
dk=-fan;
%点x(k)处的搜索步长
ak=((2*x(1)-4)*dk(1)+(2*x(2)-6)*dk(2))/(dk(1)*dk(2)-2*dk(1)^2-2*dk(2)^2);
xu=x+ak*dk;
x=xu;
%输出结果
optim_fx=subs(fx,[x1 x2],[x(1) x(2)]);
fprintf(' x=[ %d %d ] optim_fx=%d\n',x(1),x(2),optim_fx);
%计算目标函数点x(k+1)处一阶导数值
fan=subs(fxd1,[x1 x2],[x(1) x(2)]);
g=0;
for i=1:length(fan)
g=g+fan(i)^2;
end
g=sqrt(g);
end
%输出结果
optim_fx=subs(fx,[x1 x2],[x(1) x(2)]);
fprintf('\n最速下降法\n结果：\n x=[ %d %d ] optim_fx=%d\n',x(1),x(2),optim_fx); c++程序
#include<stdio.h>
#include<iostream.h>
#include<iomanip.h>
#include<math.h>
float goldena(float x[2],float p[2])
{float a;
a=-1*(x[0]*p[0]+4*x[1]*p[1])/(p[0]*p[0]+4*p[1]*p[1]);
return a;
}
void main()
{float a=0,x[2],p[2],g[2]={0,0},e=0.001,t;
int i=0;
x[0]=1.0;
x[1]=1.0;
p[0]=2*x[0];
p[1]=8*x[1];
g[0]=-p[0];
g[1]=-p[1];
printf("\n\n");
while(sqrt(g[0]*g[0]+g[1]*g[1])>e&&i<=100)
{
i=i+1;
a=goldena(x,g);
x[0]=x[0]+a*g[0];
x[1]=x[1]+a*g[1];
p[0]=2*x[0];
p[1]=8*x[1];
g[0]=-p[0];
g[1]=-p[1];
t=float(sqrt(g[0]*g[0]+g[1]*g[1]));
printf("第%d次t=%f x1=%f\tx2=%f\ta=%f\n",i,sqrt(g[0]*g[0]+g[1]*g[1]),x[0],x[1],a);
}
printf("\n最优解为：x1=%f,x2=%f\n最优值为y=%f\n",x[0],x[1],x[0]*x[0]+4*x[1]*x[1]); }。