第四章 无约束优化方法
——最速下降法，牛顿型方法
概述
在求解目标函数的极小值的过程中，若对设计变量的取值范围不加限制，则称这
种最优化问题为无约束优化问题。尽管对于机械的优化设计问题，多数是有约束的，
无约束最优化方法仍然是最优化设计的基本组成部分。因为约束最优化问题可以通过
对约束条件的处理，转化为无约束最优化问题来求解。
为什么要研究无约束优化问题?
（1）有些实际问题，其数学模型本身就是一个无约束优化问题。
（2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。
（3）约束优化问题的求解可以通过一系列无约束优化方法来达到。
所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。
根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。
一：间接法——要使用导数的无约束优化方法，如梯度法、（阻尼）牛顿法、变尺度
法、共轭梯度法等。
二：直接法——只利用目标函数值的无约束优化问题，如坐标轮换法、鲍威尔法单纯
形法等。
无约束优化问题的一般形式可描述为：
求n 维设计变量 []12T
n n X x x x R =∈L 使目标函数 ()min f X ?
目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。
无约束优化问题的求解：
1、解析法
可以利用无约束优化问题的极值条件求得。即将求目标函数的极值问题变成求方
程
0)(min *=X f
的解。也就是求Ｘ＊使其满足
解上述方程组，求得驻点后，再根据极值点所需满足的充分条件来判定是否为极小值
点。但上式是一个含有ｎ个未知量，ｎ个方程的方程组，在实际问题中一般是非线性
的，很难用解析法求解，要用数值计算的方法。由第二章的讲述我们知道，优化问题
的一般解法是数值迭代的方法。因此，与其用数值方法求解非线性方程组，还不如用
数值迭代的方法直接求解无约束极值问题。
2、数值方法 数值迭代法的基本思想是从一个初始点)
0(X 出发，按照一个可行的搜索方向)0(d ρ搜索，确定最佳的步长0α使函数值沿)0(d ρ方向下降最大，得到)1(X 点。依此一步一步地重复数值计算，最终达到最优点。优化计算所采用的基本迭代公式为
),2,1,0()()()1(Λρ=+=+k d X X K K K K α （4.2）
在上式中， ()K d r 是第是 k+1 次搜索或迭代方向，称为搜索方向（迭代方向）。
由上面的迭代公式可以看出，采用数值法进行迭代求优时，需要确定初始点)(k X 、搜索方向)(k d ρ和迭代步长K α，称为优化方法迭代算法的三要素。第三章我们已经讨论了如何在搜索方向)(k d ρ上确定最优步长K α的方法，本章我们将讨论如何确定搜索方向)(k d ρ。
最常用的数值方法是搜索方法，其基本思想如下图所示：
0)(0)(0)(*2*1*=??=??=??n
x X f x X f x X f
M
无约束优化方法可以分为两类。一类是通过计算目标函数的一阶或二阶导数值确
定搜索方向的方法，称为间接法，如最速下降法、牛顿法、变尺度法和共轭梯度法。
另一类是直接利用目标函数值确定搜索方向的方法，称为直接法，如坐标轮换法、鲍
威尔法和单形替换法。各种无约束优化方法的区别在于确定其搜索方向0d 的方法不
同。
4．1最速下降法
最速下降法是一个求解极值问题的古老算法，1847年由柯西（Cauchy ）提出。
4.1.1最速下降法的基本原理
由第二章优化设计的数学基础可知，梯度方向是函数增加最快的方向，负梯度方
向是函数下降最快的方向，所以最速下降法以负梯度方向为搜索方向，每次迭代都沿
着负梯度方向进行一维搜索，直到满足精度要求为止。因此，最速下降法又称为梯度
法。由公式（4.2）
),2,1,0()()()1(Λρ=+=+k d X X K K K K α
可知，若某次选代中己取得点)(k X ，从该点出发，取负梯度方向
)
()()()()(k k k X f X f d ??-=ρ 为搜索方向。则最速下降法的迭代公式为
()(1)()()()(0,1,2,)()k K K K k f X X X k f X α+?=-=?L （4.3）
当第ｋ次的迭代初始点)(k X
和搜索方向)(k d ρ已经确定的情况下，原目标函数成为关于
步长α的一维函数。即 ()()()()K K f X S ?αα=+
最优步长K α可以利用
一维搜索的方法求得
(1)()()()()min ()()()min ()k K k K k k f X f X d f X d αα
?ααα+==+=+r r
根据一元函数极值
的必要条件和多元复合
函数的求导公式，得
()()()()()()0T K k K f X d f X ?αα??'=-?+?=??
r (1)()()()0T
K K f X f X +????=?? 或写成 (1)()[]0K T k d
d +=r r 由此可知，在最速下降法中相邻两个搜索方向互相正交。也就是说在用最速下降
法迭代求优的过程中，走的是一条曲折的路线，该次搜索方向与前一次搜索方向垂直，
形成“之”字形的锯齿现象，如图4.1所示。最速下降法刚开始搜索步长比较大，愈
靠近极值点其步长愈小，收敛速度愈来愈慢。特别是对于二维二次目标函数的等值线
是较扁的椭圆时，这种缺陷更加明显。因此所谓最速下降是指目标函数在迭代点附近
出现的局部性质，从迭代过程的全局来看，负梯度方向并非是目标函数的最快搜索方
向。
图4.1最速下降法的搜索路径
此外，最速下降法的迭代公式也可以写成下面的形式
(1)()()()(0,1,2,)K K k K X X f X k α+=-?=L （4.4）
将其与式4.3相比较，可知，此处K α等于4.3式中步长除以函数在()K X 点导数的模
()()k f X ?，而此时的搜索方向()()()k k d f X =?r 也不再是个单位向量。
4.1.2最速下降法的迭代过程
１） 给定初始点(0)X ，收敛精度ε，并令计算次数0k ?；
２） 计算)(k X 点的梯度()()K f X ?及梯度的模()()k f X ?，并令
)
()()()()(k k k X f X f d ??-=ρ ３） 判断是否满足精度指标()()k f X ε?≤；若满足，)(k X 为最优点，迭代停止，
输出最优解*()k X X =和*()()()k f X f X =，否则进行下一步计算；
４） 以)(k X
为出发点，沿)(k d ρ进行一维搜索，求能使函数值下降最多的步长K α，
即 ()()()()min ()()k k k k K f X d f X d ααα+=+r r
５） 令(1)()()k k k K X X d α+=+r ，ｋ＝ｋ＋１，转到步骤2)。
最速下降法的程序框图如图4.2所示。
4.2最速下降法的程序框图
例题4.1 用最速下降法求目标函数2212()(1)(1)f X x x =-+-的极小值，设初始
点(0)T [0 0]X =，计算精度210ε-=。
解 （１）计算初始点(0)X 处目标函数的梯度和梯度的模
11(0)22(0)()2(1)2() 2(1)()2 ()f X x x f X x f X x f X ??????--???????===????-?-???????????
?=
（２）由于(0)()f X ε?=>，不满足精度指标，转下一步计算。
（３）确定搜索方向
(0)(0)(0)2()2()f X d f X -??=-==?-??r （４）计算新的迭代点
由公式（4.2）可得
(1)(0)(0)00X X d αα??=+=+=????r 代入目标函数
(1)22()1)1)f X =+-
沿)(k d ρ方向进行一维搜索（或对α求导，并令其为零）
(1)()1)1)df X d α=-+- 令(1)()0df X d α
=
，，求得最优步长0α。 （５）计算新迭代点
(1)11X ??===???? （６）计算新迭代点的梯度及梯度的模
1(1)
22(1)0()2(1)0x f X x -?????==????-???? (0)()0f X ε?=<
因已满足精度要求，停止迭代，得最优解为
*11X ??=????
，*()0f X = 可见，对于目标函数的等值线为圆的情况，只要一次迭代就能达到极小值点*X 。
这是因为圆周上任意一点的负梯度方向总是指向圆心的，如图4.3所示。
图4.3例题4.1目标函数极小值的搜索过程
通过上面的分析可知最速下降法具有以下特点：
（1）理论明确，程序简单，对初始点要求不严格，每次迭代所需的计算量和存储
量也较小，适用于计算机计算。
（2）对一般函数而言，最速下降法的收敛速度并不快，因为最速下降方向仅仅是
指某点的一个局部性质。
（3）最速下降法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯
齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。
（4）最速下降法的收敛速度与目标函数的性质以及初始点的选择密切相关。对于
等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。若目标函数为二
次函数，等值线为椭圆，当初始点选在长轴或短轴上时，一次搜索也可达到极小值点。最速下降法的收敛速度和变量的尺度关系很大，这一点可从最速下降法收敛速度的估
计式上看出来。在适当条件下，有
式中的海赛矩阵最大特征值上界；其
最小特征值下界。
当相邻两个迭代点之间满足上式时（右边的系数为小于等于1的正的常数），我们称
相应的迭代方法是具有线性收敛速度的迭代法。因此，最速下降法是具有线性收敛速
度的选代法。
鉴于应用最速下降法可以使目标函数在开头几步下降很快，所以它可与其它无约束优
化方法配合使用。
即在开始阶段用梯度法求得一个较优的初始点，然后用其它收敛快的方法继续寻找极
小点。
4．2牛顿法
牛顿法是根据目标函数的等值线在极值点附近为同心椭圆族的特点，在极值点*
X 邻域内用一个二次函数()X ?来近似代替原目标函数()f X ，并将()X ?的极小值点作
为对目标函数()f X 求优的下一个迭代点，经多次迭代，使之逼近原目标函数()f X 的
极小值点。
4.2.1牛顿法的基本原理
设目标函数是连续二阶可微的，将函数在)(k X 点按泰勒级数展开，并保留到二次项，得
()()()()2()()1()()()[()]()()()() 2
K K T K K T K K f X X f X f X X X X X f X X X ?≈=+?-+-?-此式是个二次函数，设(1)k X +为()X ?的极小值点，则
(1)()0k X ?+?=
即
()2()(1)()()()()0k k k k f X f X X X +?+?-=(1)()2()1()[()]()(0,1,2,)K K K K X X f X f X k +-=-??=L （4.5）
这就是多元函数求极值的牛顿法迭代公式。式中取()2()1()[()]()k K K d f X f X -=-??r 称为牛顿方向，为常数。式中没有步长k α，或者可以
看成步长恒等于1，所以牛顿法是一种定步长的迭代。
例题4.4 用牛顿法求目标函数2212()25f X x x =+的极小值。
解 （１）取初始点(0)T [2 2]X =
（２）计算梯度、二阶偏导数矩阵及其逆矩阵
1(0)221224()5010020 ()050102()1050x f X x f X f X -?????==??????
?????=????
???????=?????????
?
（３）计算新的迭代点
(1)(0)2(0)1(0)102402[()]()121000050X X f X f X -??????????=-??=-=????????????????????
经过一次迭代即可求得极小值点*T [0 0]X =，函数极小值*()0f X =。
4.2.2 阻尼牛顿法
由以上的两个例题可以看出，对于二次函数，用牛顿法迭代一次即可得到最优点；对于非二次函数，若函数的迭代点已进入极小点的邻域，则其收敛速度也是很快的。但是从牛顿法迭代公式的推导可以看出，迭代点是由近似二次函数()X ?的极值条件确定的，该点可能是()X ?极小值点，也可能是()X ?的极大值点。因此在用牛顿法迭代时，可能会出现函数上升的现象，即(1)()()()k k f X f X +>，使迭代不能收敛于最优点。例如上例中若取初始点(0)T [0 1]X =，第一次迭代点的函数值就增大。这表明牛顿法不能保证函数值稳定地下降，在严重的情况下甚至不能收敛而导致计算失败。可见，牛顿法对初始点的要求是比较苛刻的，所选取的初始点离极小值点不能太远。而在极小值点位置未知的情况下，上述要求很难达到。
为了消除牛顿法的上述这些弊病，需要对其做一些修改。将牛顿法定步长的迭代，改为变步长的迭代，引入步长α，在()k X 的牛顿方向进行一维搜索，保证每次迭代点的函数值都是下降的。这种方法称为阻尼牛顿法，其迭代公式为
(1)()2()1()[()]()(0,1,2,)
K K K K k X X f X f X k α+-=-??=L （4.6）
式中，K α为牛顿方向的最优步长。这种方法对初始点的选取不再苛刻，从而提高了牛顿法的可靠度。但采用阻尼牛顿法，每次迭代都要进行一维搜索，使收敛速度大大降
低。例如，对于例 4.6所示的目标函数，取同样的初始点，采用阻尼牛顿法进行迭代，达到同样的精度，要经过25次的迭代，越靠近极小值点收敛速度越慢，使牛顿法收敛速度快的优势损失殆尽。
阻尼牛顿法的迭代过程：
阻尼牛顿法的计算步骤如下：
１）给定初始点(0)X ，收敛精度ε，并令计算次数0k ?；
２）计算)(k X 点的梯度()()K f X ?和梯度的模()()k f X ?；
３）判断是否满足精度指标()()k f X ε?≤；若满足，)(k X 为最优点，迭代停止，输出最优解*()k X X =和*()()()k f X f X =，否则进行下一步计算；
5）计算)(k X 点的牛顿方向()k d r
()2()1()[()]()k K K d f X f X -=-??r
6）以)(k X 为出发点，沿()k d r 进行一维搜索，求能使函数值下降最多的步长K α，即
()()()()min ()()k k k k K f X d f X d ααα+=+r r
令(1)()()k k k K X X d α+=+r ，ｋ＝ｋ＋１，转到步骤2)。
阻尼牛顿法的程序框图如图4.7所示：
4.7阻尼牛顿法的程序框图
牛顿法的总结
牛顿法和阻尼牛顿法统称为牛顿型方法。这类方法的最大优点是收敛速度快。也
就是说，它的迭代次数相对其他方法来说少得多。特别是对于一些性态较好的目标函数，例如二次函数，只需保证求梯度和二阶偏导数矩阵时的精度，不管初始点在何处，均可一步就找出最优点。可是这类方法也有很大的缺点。首先，在每次迭代决定牛顿
方向时，都要计算目标函数的一阶导数和二阶导数矩阵及其逆矩阵。这就使计算较为
复杂，增加了每次迭代的计算工作量和计算机的存储量。
选用原则和条件：该方法适用于目标函数具有一阶、二阶偏导数，海森矩阵非奇异，维数不太高的场合。
《最优化》课程设计 题目：牛顿法与阻尼牛顿法算法分析 学院: 数学与计算科学学院 专业：数学与应用数学 姓名学号：廖丽红 1000730105 欧艳 1000730107 骆宗元 1000730122 沈琼赞 1000730127 指导教师：李向利 日期：2012年11月08日
摘要 本文基于阻尼牛顿法在解决无约束最优化问题中的重要性，对其原理与算法予以讨论。论文主要是参阅大量数学分析和最优化理论方法，还有最优化方法课程以及一些学术资料，结合自己在平时学习中掌握的知识，并在指导老师的建议下，拓展叙述牛顿法和其改进方法——阻尼牛顿法的优缺点，同时针对阻尼牛顿法的基本思路和原理进行研究，其搜索方向为负梯度方向，改善了牛顿法的缺点，保证了下降方向。 关键词：无约束牛顿法下降方向阻尼牛顿法最优解
Abstract This thesis is based on the importance of the damping Newton's method to solve unconstrained optimization problems, we give the discussion about its principles and algorithms. We search a large number of mathematical analysis and optimization theory methods, optimization methods courses, as well as some academic information ,and at the same time combined with knowledge we have learning in peacetime and thanks to the instructor's advice, we also give an expanding narrative for the Newton's method and the improved method -- damping Newton method's advantages and disadvantages, and make a study of the basic ideas and principles for damping Newton method at the same time , we find that a negative gradient direction is for the search direction of the damping Newton method, this method improves the shortcomings of the Newton method which can ensure the descent direction. Keywords: unconstrained , Newton's method , descent direction , damping Newton's method ,optimal solution
实验的题目和要求 一、所属课程名称： 最优化方法 二、实验日期： 2010年5月10日~2010年5月15日 三、实验目的 掌握最速下降法，牛顿法和共轭梯度法的算法思想，并能上机编程实现相应的算法。 二、实验要求 用MATLAB实现最速下降法，牛顿法和共轭梯度法求解实例。 四、实验原理 最速下降法是以负梯度方向最为下降方向的极小化算法，相邻两次的搜索方向是互相直交的。牛顿法是利用目标函数)(x f在迭代点 x处的Taylor展开式作为模型函数，并利用这个二次模型函数的极k 小点序列去逼近目标函数的极小点。共轭梯度法它的每一个搜索方向是互相共轭的，而这些搜索方向 d仅仅是负梯度方向k g-与上一次接 k 待的搜索方向 d的组合。 k - 1 五．运行及结果如下: 最速下降法： 题目：f=(x-2)^2+(y-4)^2 M文件： function [R,n]=steel(x0,y0,eps) syms x; syms y; f=(x-2)^2+(y-4)^2; v=[x,y]; j=jacobian(f,v); T=[subs(j(1),x,x0),subs(j(2),y,y0)]; temp=sqrt((T(1))^2+(T(2))^2); x1=x0;y1=y0; n=0; syms kk; while (temp>eps) d=-T;
f1=x1+kk*d(1);f2=y1+kk*d(2); fT=[subs(j(1),x,f1),subs(j(2),y,f2)]; fun=sqrt((fT(1))^2+(fT(2))^2); Mini=Gold(fun,0,1,0.00001); x0=x1+Mini*d(1);y0=y1+Mini*d(2); T=[subs(j(1),x,x0),subs(j(2),y,y0)]; temp=sqrt((T(1))^2+(T(2))^2); x1=x0;y1=y0; n=n+1; end R=[x0,y0] 调用黄金分割法： M文件： function Mini=Gold(f,a0,b0,eps) syms x;format long; syms kk; u=a0+0.382*(b0-a0); v=a0+0.618*(b0-a0); k=0; a=a0;b=b0; array(k+1,1)=a;array(k+1,2)=b; while((b-a)/(b0-a0)>=eps) Fu=subs(f,kk,u); Fv=subs(f,kk,v); if(Fu<=Fv) b=v; v=u; u=a+0.382*(b-a); k=k+1; elseif(Fu>Fv) a=u; u=v; v=a+0.618*(b-a); k=k+1; end array(k+1,1)=a;array(k+1,2)=b; end Mini=(a+b)/2; 输入： [R,n]=steel(0,1,0.0001) R = 1.99999413667642 3.99999120501463 R = 1.99999413667642 3.99999120501463 n = 1 牛顿法：
题目和要求 最速下降法是以负梯度方向最为下降方向的极小化算法，相邻两次的搜索方向是互相直交的。牛顿法是利用目标函数)(x f在迭代点 x处的Taylor展开式作为模型函数，并利用这个二次模型函数的极k 小点序列去逼近目标函数的极小点。共轭梯度法它的每一个搜索方向是互相共轭的，而这些搜索方向 d仅仅是负梯度方向k g-与上一次接 k 待的搜索方向 d的组合。 k - 1 运行及结果如下: 最速下降法： 题目：f=(x-2)^2+(y-4)^2 M文件： function [R,n]=steel(x0,y0,eps) syms x; syms y; f=(x-2)^2+(y-4)^2; v=[x,y]; j=jacobian(f,v); T=[subs(j(1),x,x0),subs(j(2),y,y0)]; temp=sqrt((T(1))^2+(T(2))^2); x1=x0;y1=y0; n=0; syms kk; while (temp>eps) d=-T; f1=x1+kk*d(1);f2=y1+kk*d(2); fT=[subs(j(1),x,f1),subs(j(2),y,f2)]; fun=sqrt((fT(1))^2+(fT(2))^2); Mini=Gold(fun,0,1,0.00001); x0=x1+Mini*d(1);y0=y1+Mini*d(2); T=[subs(j(1),x,x0),subs(j(2),y,y0)]; temp=sqrt((T(1))^2+(T(2))^2); x1=x0;y1=y0; n=n+1; end R=[x0,y0] 调用黄金分割法：
最优化方法结课作业 年级数学121班 学号201200144209 姓名李强
1、几种方法比较 无约束优化：不对定义域或值域做任何限制的情况下，求解目标函数的最小值。这是因为实际应用中，许多情形被抽象为函数形式后均为凸函数，对于凸函数来说局部最小值点即为全局最小值点，因此只要能求得这类函数的一个最小值点，该点一定为全局最小值。（直接法：又称数值方法，它只需计算目标函数驻点的函数数值，而不是求其倒数，如坐标轮换法，单纯型法等。间接法：又称解析法，是应用数学极值理论的解析方法。首先计算出目标函数的一阶或一阶、二阶导数，然后根据梯度及海赛矩阵提供的信息，构造何种算法，从而间接地求出目标函数的最优解，如牛顿法、最速下降法共轭梯度法及变尺度法。）在优化算法中保证整体收敛的重要方法就是线搜索法与信赖域法,这两种算法既相似又有所不同。根据不同的线搜索准则就延伸出不同的线搜索算法,譬如比较常见和经典的最速下降法,牛顿法,拟牛顿法以及共辄梯度法等。 一维搜索又称线性搜索(Line Search),就是指单变量函数的最优化,它是多变量函数最优化的基础,是求解无约束非线性规划问题的基本方法之一。 一维搜索技术既可独立的用于求解单变量最优化问题,同时又是求解多变量最优化问题常用的手段,虽然求解单变量最优化问题相对比较简单,但其中也贯穿了求解最优化问题的基本思想。由于一维搜索的使用频率较高,因此努力提高求解单变量问题算法的计算效率具有重要的实际意义。 在多变量函数的最优化中,迭代格式Xk+1=Xk+akdk其关键就是构造搜索方向dk和步长因子ak 设Φ(a)=f(xk+adk) 这样从凡出发,沿搜索方向dk,确定步长因子ak,使Φ(a)<Φ(0)的问题就是关于步长因子a 的一维搜索问题。其主要结构可作如下概括:首先确定包含问题最优解的搜索区间，然后采用某种分割技术或插值方法缩小这个区间，进行搜索求解。 一维搜索通常分为精确的和不精确的两类。如果求得ak使目标函数沿方向dk达到极小,即使得f (xk+akdk)=min f (xk+ adk) ( a>0)则称这样的一维搜索为最优一维搜索,或精确一维搜索,ak叫最优步长因子;如果选取ak使目标函数f得到可接受的下降量,即使得下降量f (xk)一f (xk+akdk)>0是用户可接受的,则称这样的一维搜索为近似一维搜索,或不精确一维搜索,或可接受一维搜索。由于在实际计算中,一般做不到精确的一维搜索,实际上也没有必要做到这一点,因为精确的一维搜索需要付出较高的代价,而对加速收敛作用不大,因此花费计算量
常用无约束最优化方法评价准则 方法算法特点适用条件 最速下降法属于间接法之一。方法简便，但要计算一阶偏导 数，可靠性较好，能稳定地使函数下降，但收敛 速度较慢，尤其在极点值附近更为严重 适用于精度要求不高或用于对 复杂函数寻找一个好的初始 点。 Newton法属于间接法之一。需计算一、二阶偏导数和Hesse 矩阵的逆矩阵，准备工作量大，算法复杂，占用 内存量大。此法具有二次收敛性，在一定条件下 其收敛速度快，要求迭代点的Hesse矩阵必须非 奇异且定型（正定或负定）。对初始点要求较高， 可靠性较差。 目标函数存在一阶\二阶偏导 数，且维数不宜太高。 共轭方向法属于间接法之一。具有可靠性好，占用内存少， 收敛速度快的特点。 适用于维数较高的目标函数。 变尺度法属于间接法之一。具有二次收敛性，收敛速度快。 可靠性较好，只需计算一阶偏导数。对初始点要 求不高，优于Newton法。因此，目前认为此法是 最有效的方法之一，但需内存量大。对维数太高 的问题不太适宜。 适用维数较高的目标函数 （n=10～50）且具有一阶偏导 数。 坐标轮换法最简单的直接法之一。只需计算函数值，无需求 导，使用时准备工作量少。占用内存少。但计算 效率低，可靠性差。 用于维数较低（n<5）或目标函 数不易求导的情况。 单纯形法此法简单，直观，属直接法之一。上机计算过程 中占用内存少，规则单纯形法终止条件简单，而 不规则单纯形法终止条件复杂，应注意选择，才 可能保证计算的可靠性。 可用于维数较高的目标函数。
常用约束最优化方法评价标准 方法算法特点适用条件 外点法将约束优化问题转化为一系列无约束优化问题。 初始点可以任选，罚因子应取为单调递增数列。 初始罚因子及递增系数应取适当较大值。 可用于求解含有等式约束或不等 式约束的中等维数的约束最优化 问题。 内点法将约束优化问题转化为一系列无约束优化问题。 初始点应取为严格满足各个不等式约束的内点， 障碍因子应取为单调递减的正数序列。初始障碍 因子选择恰当与否对收敛速度和求解成败有较大 影响。 可用于求解只含有不等式约束的 中等维数约束优化问题。 混合罚函数法将约束优化问题转化为一系列无约束优化问题， 用内点形式的混合罚函数时，初始点及障碍因子 的取法同上；用外点形式的混合罚函数时，初始 点可任选，罚因子取法同外点法相同。 可用于求解既有等式约束又有不 等式约束的中等维数的约束化问 题。 约束坐标轮换法由可行点出发，分别沿各坐标轴方向以加步探索 法进行搜索，使每个搜索点在可行域内，且使目 标函数值下降。 可用于求解只含有不等式约束， 且维数较低（n<5），目标函数的 二次性较强的优化问题。 复合形法在可行域内构造一个具有n个顶点的复合形，然 后对复合形进行映射变化，逐次去掉目标函数值 最大的顶点。 可用于求解含不等式约束和边界 约束的低维优化问题。
无约束优化方法---鲍威尔方法 本实验用鲍威尔方法求函数f(x)=(x1-5)2+(x2-6)2 的最优解。 一、简述鲍威尔法的基本原理 从任选的初始点x⑴o出发，先按坐标轮换法的搜索方向依次沿e1.e2.e3进行一维搜索，得各自方向的一维极小点x⑴ x⑵ x⑶.连接初始点xo⑴和最末一个一维极小点x3⑴,产生一个新的矢量 S1=x3⑴-xo⑴ 再沿此方向作一维搜索，得该方向上的一维极小点x⑴. 从xo⑴出发知道获得x⑴点的搜索过程称为一环。S1是该环中产生的一个新方向，称为新生方向。 接着，以第一环迭代的终点x⑴作为第二环迭代的起点xo⑵,即 Xo⑵←x⑴ 弃去第一环方向组中的第一个方向e1，将第一环新生方向S1补在最后，构成第二环的基本搜索方向组e2,e3,S1，依次沿这些方向求得一维极小点x1⑵,x2⑵,x3⑵.连接 Xo⑵与x3⑵,又得第二环的新生方向 S2=x3⑵-xo⑵ 沿S2作一维搜索所得的极小点x⑵即为第二环的最终迭代点 二、鲍威尔法的程序 #include "stdafx.h" /* 文件包含*/ #include
#include
项目三 常用无约束最优化方法（一） [实验目的] 编写最速下降法、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
MATLAB实现最速下降法_和牛顿法和共轭梯度法最速下降法: 题目:f=(x-2)^2+(y-4)^2 M文件: function [R,n]=steel(x0,y0,eps) syms x; syms y; f=(x-2)^2+(y-4)^2; v=[x,y]; j=jacobian(f,v); T=[subs(j(1),x,x0),subs(j(2),y,y0)]; temp=sqrt((T(1))^2+(T(2))^2); x1=x0;y1=y0; n=0; syms kk; while (temp>eps) d=-T; f1=x1+kk*d(1);f2=y1+kk*d(2); fT=[subs(j(1),x,f1),subs(j(2),y,f2)]; fun=sqrt((fT(1))^2+(fT(2))^2); Mini=Gold(fun,0,1,0.00001); x0=x1+Mini*d(1);y0=y1+Mini*d(2); T=[subs(j(1),x,x0),subs(j(2),y,y0)]; temp=sqrt((T(1))^2+(T(2))^2); x1=x0;y1=y0;
n=n+1; end R=[x0,y0] 调用黄金分割法: M文件: function Mini=Gold(f,a0,b0,eps) syms x;format long; syms kk; u=a0+0.382*(b0-a0); v=a0+0.618*(b0-a0); k=0; a=a0;b=b0; array(k+1,1)=a;array(k+1,2)=b; while((b-a)/(b0-a0)>=eps) Fu=subs(f,kk,u); Fv=subs(f,kk,v); if(Fu<=Fv) b=v; v=u; u=a+0.382*(b-a); k=k+1; elseif(Fu>Fv) a=u; u=v; v=a+0.618*(b-a); k=k+1;
revisenewton.m syms x1 x2 x3 xx; % f = x1*x1 +x2*x2 -x1*x2 -10*x1 -4*x2 + 60 ; % f = x1^2 + 2*x2^2 - 2*x1 *x2 -4*x1 ; f = 100 * (x1^2 - x2^2) + (x1 -1 )^2 ; hessen = jacobian(jacobian(f , [x1,x2]),[x1,x2]) ; gradd = jacobian(f , [x1,x2]) ; X0 = [0,0]' ; B = gradd' ; x1 = X0(1); x2 = X0(2); A = eval(gradd) ; % while sqrt( A(1)^2 + A(2)^2) >0.1 i=0; while norm(A) >0.1 i = i+1 ; fprintf('the number of iterations is: %d\n', i) if i>10 break; end B1 = inv(hessen)* B ; B2= eval(B1); % X1 = X0 - B2 % X0 = X1 ; f1= x1 + xx * B2(1); f2= x2 + xx* B2(2); % ff = norm(BB) ? syms x1 x2 ; fT=[subs(gradd(1),x1,f1),subs(gradd(2),x2,f2)]; ff = sqrt((fT(1))^2+(fT(2))^2); MinData = GoldData(ff,0,1,0.01); x1 = X0(1); x2 = X0(2); x1 = x1 + MinData * B2(1) x2 = x2 + MinData * B2(2) A = eval(gradd) End GoldData.m function MiniData = GoldData( f,x0,h0,eps) syms xx;
第四章 无约束优化方法 ——最速下降法，牛顿型方法 概述 在求解目标函数的极小值的过程中，若对设计变量的取值范围不加限制，则称这种最优化问题为无约束优化问题。尽管对于机械的优化设计问题，多数是有约束的，无约束最优化方法仍然是最优化设计的基本组成部分。因为约束最优化问题可以通过对约束条件的处理，转化为无约束最优化问题来求解。 为什么要研究无约束优化问题? （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。 所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。 根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。 一：间接法——要使用导数的无约束优化方法，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。 二：直接法——只利用目标函数值的无约束优化问题，如坐标轮换法、鲍威尔法单纯形法等。 无约束优化问题的一般形式可描述为： 求n 维设计变量 []1 2T n n X x x x R =∈L 使目标函数 ()min f X ? 目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。 无约束优化问题的求解： 1、解析法
可以利用无约束优化问题的极值条件求得。即将求目标函数的极值问题变成求方程 0)(min *=X f 的解。也就是求Ｘ＊使其满足 解上述方程组，求得驻点后，再根据极值点所需满足的充分条件来判定是否为极小值点。但上式是一个含有ｎ个未知量，ｎ个方程的方程组，在实际问题中一般是非线性的，很难用解析法求解，要用数值计算的方法。由第二章的讲述我们知道，优化问题的一般解法是数值迭代的方法。因此，与其用数值方法求解非线性方程组，还不如用数值迭代的方法直接求解无约束极值问题。 2、数值方法 数值迭代法的基本思想是从一个初始点) 0(X 出发，按照一个可行的搜索方向) 0(d ρ搜索，确定最佳的步长0α使函数值沿) 0(d ρ方向下降最大，得到)1(X 点。依此一步一步 地重复数值计算，最终达到最优点。优化计算所采用的基本迭代公式为 ),2,1,0() () () 1(Λρ=+=+k d X X K K K K α （4.2） 在上式中， () K d r 是第是 k+1 次搜索或迭代方向，称为搜索方向（迭代方向）。 由上面的迭代公式可以看出，采用数值法进行迭代求优时，需要确定初始点)(k X 、搜 索方向) (k d ρ和迭代步长K α，称为优化方法迭代算法的三要素。第三章我们已经讨论了 如何在搜索方向) (k d ρ上确定最优步长K α的方法，本章我们将讨论如何确定搜索方向) (k d ρ。 最常用的数值方法是搜索方法，其基本思想如下图所示： 0) (0) (0) (*2*1*=??=??=??n x X f x X f x X f M
实验报告日期：2013年6月2日 一、实验概述 【实验名称】：牛顿法 【实验性质】：验证性 【实验目的及要求】：配合课堂教学，培养学生动手能力，根据牛顿法求极小值的思想设计程序。 【基本原理】：牛顿法的迭代公式：)()(12)()1(k k k k x f x f x x ??-=-+，其中)(2k x f k ?是f(x)在k x 处的Hesse 矩阵。【实施环境】： MATLAB 7.0 二、实验内容 【项目内容及要求】 用牛顿法求解以下问题： min z=(x1-1)4+x22 三、实验过程 【实验操作步骤】 function [x1k]=newton(x1,j) %x1为初始点x1=[8,8]';j=1e-10; hs=inline('(x-1)^4+y^2');
ezcontour(hs,[-1010-1010]);hold on; syms x y f=(x-1)^4+y^2; grad1=jacobian(f,[x,y]);%求梯度 grad2=jacobian(grad1,[x,y]);%求Hesse矩阵 k=0; while1 grad1z=subs(subs(grad1,x,x1(1)),y,x1(2));%求梯度值 grad2z=subs(subs(grad2,x,x1(1)),y,x1(2));%求Hesse矩阵x2=x1-inv(grad2z)*(grad1z');%牛顿迭代公式 if norm(x1-x2) 题目和要求 最速下降法是以负梯度方向最为下降方向的极小化算法，相邻 两次的搜索方向是互相直交的。牛顿法是利用目标函数)(x f 在迭代点k x 处的Taylor 展开式作为模型函数，并利用这个二次模型函数的极小 点序列去逼近目标函数的极小点。共轭梯度法它的每一个搜索方向是互相共轭的，而这些搜索方向k d 仅仅是负梯度方向k g -与上一次接待 的搜索方向1-k d 的组合。 运行及结果如下: 最速下降法： 题目：f=(x-2)^2+(y-4)^2 M 文件： function [R,n]=steel(x0,y0,eps) syms x ; syms y ; f=(x-2)^2+(y-4)^2; v=[x,y]; j=jacobian(f,v); T=[subs(j(1),x,x0),subs(j(2),y,y0)]; temp=sqrt((T(1))^2+(T(2))^2); x1=x0;y1=y0; n=0; syms kk ; while (temp>eps) d=-T; f1=x1+kk*d(1);f2=y1+kk*d(2); fT=[subs(j(1),x,f1),subs(j(2),y,f2)]; fun=sqrt((fT(1))^2+(fT(2))^2); Mini=Gold(fun,0,1,0.00001); x0=x1+Mini*d(1);y0=y1+Mini*d(2); T=[subs(j(1),x,x0),subs(j(2),y,y0)]; temp=sqrt((T(1))^2+(T(2))^2); x1=x0;y1=y0; n=n+1; end R=[x0,y0] 调用黄金分割法： M文件： function Mini=Gold(f,a0,b0,eps) syms x;format long; syms kk; u=a0+0.382*(b0-a0); v=a0+0.618*(b0-a0); k=0; a=a0;b=b0; array(k+1,1)=a;array(k+1,2)=b; while((b-a)/(b0-a0)>=eps) Fu=subs(f,kk,u); Fv=subs(f,kk,v); if(Fu<=Fv) b=v; v=u; u=a+0.382*(b-a); k=k+1; elseif(Fu>Fv) a=u; u=v; v=a+0.618*(b-a); k=k+1; end array(k+1,1)=a;array(k+1,2)=b; end Mini=(a+b)/2; 输入： [R,n]=steel(0,1,0.0001) R = 1.99999413667642 3.99999120501463 R = 1.99999413667642 3.99999120501463 n = 1 牛顿法： 题目：f=(x-2)^2+(y-4)^2 M文件： 牛顿法 迭代公式：(1)2()1()[()]()k k k k x x f x f x +-=-?? Matlab 代码： function [x1,k] =newton(x1,eps) hs=inline('(x-1)^4+y^2'); 写入函数 ezcontour(hs,[-10 10 -10 10]); 建立坐标系 hold on; 显示图像 syms x y 定义变量 f=(x-1)^4+y^2; 定义函数 grad1=jacobian(f,[x,y]); 求f 的一阶梯度 grad2=jacobian(grad1,[x,y]); 求f 的二阶梯度 k=0; 迭代初始值 while 1 循环 grad1z=subs(subs(grad1,x,x1(1)),y,x1(2)); 给f 一阶梯度赋初值 grad2z=subs(subs(grad2,x,x1(1)),y,x1(2)); 给f 二阶梯度赋初值 x2=x1-inv(grad2z)*(grad1z)'; 核心迭代公式 if norm(x1-x2) end end end 优点：在极小点附近收敛快 缺点：但是要计算目标函数的hesse 矩阵 最速下降法 1. ：选取初始点xo ，给定误差 2. 计算一阶梯度。若一阶梯度小于误差，停止迭代，输出 3. 取()()()k k p f x =? 4. 10 t ()(), 1.min k k k k k k k k k k t f x t p f x tp x x t p k k +≥+=+=+=+进行一维搜索，求，使得令转第二步 例题： 求min (x-2)^4+(x-2*y)^2.初始值（0,3）误差为0.1 (1)编写一个目标函数，存为f.m function z = f( x,y ) z=(x-2.0)^4+(x-2.0*y)^2; end (2)分别关于x 和y 求出一阶梯度，分别存为fx.m 和fy.m function z = fx( x,y ) z=2.0*x-4.0*y+4.0*(x-2.0)^3; end 和 function z = fy( x,y ) 最速下降法与牛顿法及其区别 摘要：无约束优化方法是优化技术中极为重要和基本内容之一。它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后用无约束优化方法来求解。最速下降法和牛顿法是比较常见的求解无约束问题的最优化方法，这两种算法作为基本算法，在最优化方法中占有重要的地位。其中最速下降法又称梯度法，其优点是工作量少，存储变量较少，初始点要求不高；缺点是收敛慢，效率低。牛顿法的优点是收敛速度快；缺点是对初始点要求严格，方向构造困难，计算复杂且占用内存较大。同时，这两种算法的理论和方法渗透到许多方面，特别是在军事、经济、管理、生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。因此，研究最速下降法和牛顿法的原理及其算法对我们有着及其重要的意义。 关键字：无约束优化最速下降法牛顿法 Abstract: unconstrained optimization method is to optimize the technology is extremely important and basic content of. It not only can be directly used to solve unconstrained optimization problems, and a lot of constrained optimization problems are often transformed into unconstrained optimization problem, and then use the unconstrained optimization methods to solve. The steepest descent method and Newton-Raphson method is relatively common in the unconstrained problem optimization method, these two kinds of algorithm as the basic algorithm, the optimization method plays an important role in. One of the steepest descent method also known as gradient method, its advantages are less workload, storage variable is less, the initial requirements is not high; drawback is the slow convergence, low efficiency. Newtonian method has the advantages of fast convergence speed; drawback is the initial point of strict construction difficulties, directions, complicated calculation and larger memory. At the same time, these two kinds of algorithm theory and methods into many aspects, especially in the military, economic, management, production process automation, engineering design and product optimization design has important applications. Therefore, to study the steepest descent method and Newton-Raphson method principle and algorithm for us with its important significance. Keywords: unconstrained optimization steepest descent method 优化算法及应用报告 （一）用Newton 法求函数最优解 1.1课本P117页例4.3.2 t 0min （t ） = arctan xdx ?? 1.2方法步骤 Step1：给定初始点 1t ，k ε>0,=1 Step2：对函数求一次导数得到df1，若|1| df <ε ，则迭代停止，输出k t 否则，二次求导dff2=0时，停止，解题失败。 当dff2不等于0时，转下一步。 Step3:计算1(1/2)k k t t df dff += - ，如果1||k k t t +-<ε ，停止迭代，输出1k t +， 否则，k=k+1，转step2 1.3计算结果： Df1= atan(x)（matlab 中arctan （x ）用atan （x ）表示） Dff2= 1/(x^2 + 1) （1）t1=1时 接近最优解* t =0. （2）t1=2时 1.4程序，见附件test1，newton Test1 函数带入 clc clear all syms x t f1=int(atan(x),x,0,t); beex=newton(f1,t,1,0.5); newton 牛顿方法的函数 function[besx]=newton(f1,t,t1,c) %step1 syms t df1=diff(f1,t);%函数一次求导 dff2=diff(f1,t,2);%函数二次求导 while(true) if(abs(subs(df1,t1)) 2008-12-08 12:30 利用梯度法和牛顿法编程求最优解(matlab) f(x)=x1^2+4*x2^2 x0=[2;2] e=0.002 利用梯度法和牛顿法编程求最优解 方法一.梯度法 function y=fun(x1,x2) y=x1^2+4*x2^2; %定义fun.m函数 clc syms x1 x2 d; f=x1^2+4*x2^2; fx1=diff(f,'x1'); fx2=diff(f,'x2'); x1=2; x2=2; for n=1:100 f0=subs(f); f1=subs(fx1); f2=subs(fx2); if (double(sqrt(f1^2+f2^2)) <= 0.002) n vpa(x1) vpa(x2) vpa(f0) break; else D=fun(x1-d*f1,x2-d*f2); Dd=diff(D,'d'); dd=solve(Dd); x1=x1-dd*f1; x2=x2-dd*f2; end end %结果n=10,x1=0.2223e-3,x2=-0.1390e-4,f0=0.5021e-7. 方法二.牛顿法 clc syms x1 x2 ; f=x1^2+4*x2^2; fx1=diff(f,'x1'); fx2=diff(f,'x2'); fx1x1=diff(fx1,'x1');fx1x2=diff(fx1,'x2');fx2x1=diff(fx2,'x1');fx2x2= diff(fx2,'x2'); x1=2; x2=2; for n=1:100 f0=subs(f); f1=subs(fx1); f2=subs(fx2); if (double(sqrt(f1^2+f2^2)) <= 0.002) n x1=vpa(x1,4) x2=vpa(x2,4) f0=vpa(f0,4) break; else X=[x1 x2]'-inv([fx1x1 fx1x2;fx2x1 fx2x2]) *[f1 f2]'; x1=X[1,1]; x2=X[2,1]; end end %结果 n=2,x1=0,x2=0,f0=0. 惩罚函数法（内点法、外点法）求解约束优化问题最优值编程 matlab 1 用外点法求下列问题的最优解 方法一：外点牛顿法： clc m=zeros(1,50);a=zeros(1,50);b=zeros(1,50);f0=zeros(1,50);%a b为最优点坐标，f0为最优点函数值，f1 f2最优点梯度。 syms x1 x2 e; %e为罚因子。m(1)=1;c=10;a(1)=0;b(1)=0; %c为递增系数。赋初值。 f=x1^2+x2^2+e*(1-x1)^2;f0(1)=1; fx1=diff(f,'x1');fx2=diff(f,'x2');fx1x1=diff(fx1,'x1');fx1x2=diff(fx1 ,'x2');fx2x1=diff(fx2,'x1');fx2x2=diff(fx2,'x2');%求偏导、海森元素。for k=1:100 %外点法e迭代循环. x1=a(k);x2=b(k);e=m(k); for用MATLAB实现最速下降法-牛顿法和共轭梯度法求解实例
最优化牛顿法最速下降法共轭梯度法matlab代码
最速下降法与牛顿法及其区别
matab实现牛顿法最速下降法罚函数法
最优化 多目标优化 惩罚函数法 梯度法 牛顿法
相关主题
文本预览