下载文档原格式
最优化方法实验报告Numerical Linear Algebra And ItsApplications学生所在学院：理学院学生所在班级：计算数学10-1学生姓名：甘纯指导教师：单锐教务处2013年5月实验三实验名称：无约束最优化方法的MATLAB实现实验时间: 2013年05月10日星期三实验成绩：一、实验目的：通过本次实验的学习，进一步熟悉掌握使用MATLAB软件，并能利用该软件进行无约束最优化方法的计算。
二、实验背景：（一）最速下降法1、算法原理最速下降法的搜索方向是目标函数的负梯度方向，最速下降法从目标函数的负梯度方向一直前进，直到到达目标函数的最低点。
2、算法步骤用最速下降法求无约束问题n R()min的算法步骤如下：xxf，a ）给定初始点)0(x ，精度0>ε，并令k=0；b ）计算搜索方向)()()(k k x f v -∇=，其中)()(k x f ∇表示函数)(x f 在点)(k x 处的梯度；c ）若ε≤)(k v ，则停止计算；否则，从)(k x 出发，沿)(k v 进行一维搜索，即求k λ，使得)(min )()()(0)()(k k k k v x f v x f λλλ+=+≥； d ）令1,)()()1(+=+=+k k v x x k k k k λ，转b ）。
（二）牛顿法1、算法原理牛顿法是基于多元函数的泰勒展开而来的，它将)()]([-)(1)(2k k x f x f ∇∇-作为搜索方向，因此它的迭代公式可直接写出来：)()]([)(1)(2)()(k k k k x f x f x x ∇∇-=-2、算法步骤用牛顿法求无约束问题n R x x f ∈),(min 的算法步骤如下：a ）给定初始点)0(x ,精度0>ε，并令k=0；b ）若ε≤∇)()(k x f ，停止，极小点为)(k x ，否则转c ）；c ）计算)()]([,)]([)(1)(2)(1)(2k k k k x f x f p x f ∇∇-=∇--令；d ）令1,)()()1(+=+=+k k p x x k k k ，转b ）。
最速下降法1.最速下降方向函数f(x)在点x处沿方向d的变化率可用方向导数来表示。
对于可微函数，方向导数等于梯度与方向的内积，即：Df(x;d) = ▽f(x)T d,因此，求函数f(x)在点x处的下降最快的方向，可归结为求解下列非线性规划：min ▽f(x)T ds.t. ||d|| ≤ 1当 d = -▽f(x) / ||▽f(x)||时等号成立。
因此，在点x处沿上式所定义的方向变化率最小，即负梯度方向为最速下降方向。
2.最速下降算法最速下降法的迭代公式是x(k+1) = x(k) + λk d(k) ,其中d(k)是从x(k)出发的搜索方向，这里取在x(k)处的最速下降方向，即d = -▽f(x(k)).λk是从x(k)出发沿方向d(k)进行一维搜索的步长，即λk满足f(x(k) + λk d(k)) = min f(x(k)+λd(k)) (λ≥0).计算步骤如下：(1)给定初点x(1) ∈ R n，允许误差ε> 0，置k = 1。
(2)计算搜索方向d = -▽f(x(k))。
(3)若||d(k)|| ≤ε，则停止计算；否则，从x(k)出发，沿d(k)进行一维搜索，求λk，使f(x(k) + λk d(k)) = min f(x(k)+λd(k)) (λ≥0).(4)令x(k+1) = x(k) + λk d(k)，置k = k + 1，转步骤(2)。
共轭梯度法1.共轭方向无约束问题最优化方法的核心问题是选择搜索方向。
以正定二次函数为例，来观察两个方向关于矩阵Ａ共轭的几何意义。
设有二次函数：f(x) = 1/2 (x - x*)T A(x - x*) ,其中A是n×n对称正定矩阵，x*是一个定点，函数f(x)的等值面1/2 (x - x*)T A(x - x*) = c是以x*为中心的椭球面，由于▽f(x*) = A(x - x*) = 0，A正定，因此x*是f(x)的极小点。
共轭梯度法在优化问题中的应用共轭梯度法是一种高效的优化算法，在许多优化问题中都得到了广泛的应用。
它是一种迭代方法，用于解决最小化二次函数的优化问题。
在本文中，我将介绍共轭梯度法的原理和算法，并探讨它在优化问题中的应用。
一、共轭梯度法的原理共轭梯度法的核心思想是通过迭代的方式，找到一个与之前迭代步骤方向相互垂直的搜索方向，以加快收敛速度。
在每一次迭代中，共轭梯度法根据当前的搜索方向更新搜索点，直到找到最优解或达到预定的收敛标准。
具体来说，共轭梯度法从一个初始搜索点开始，计算对应的梯度，并沿着负梯度方向进行搜索。
通过一定的方法找到一个与之前搜索方向相互垂直的新搜索方向，并以一定步长更新搜索点。
迭代过程将重复进行，直到满足收敛标准或达到最大迭代次数。
二、共轭梯度法的算法共轭梯度法的算法包括以下几个步骤：1. 初始化搜索点x0和梯度g0，设置迭代次数k=0。
2. 计算当前搜索方向d_k=-g_k（k为当前迭代次数）。
3. 通过一维搜索方法找到最佳步长α_k。
4. 更新搜索点x_k+1 = x_k + α_k * d_k。
5. 计算更新后的梯度g_k+1。
6. 判断是否满足收敛标准，若满足则算法停止，否则转到步骤7。
7. 计算新的搜索方向β_k+1。
8. 将迭代次数k更新为k+1，转到步骤3。
这个算法保证了每一次迭代中的搜索方向都是彼此相互垂直的，从而加快了收敛速度。
三、共轭梯度法的应用共轭梯度法在优化问题中有广泛的应用，特别是在二次规划、线性规划和非线性规划等领域。
在二次规划问题中，共轭梯度法可以高效地求解线性系统Ax=b，其中A是一个对称正定的矩阵。
由于共轭梯度法的特性，它只需要进行n 次迭代，其中n是问题的维度，就能得到精确的解。
这使得共轭梯度法在大规模线性系统求解中具有重要的应用价值。
在线性规划问题中，共轭梯度法可以用于求解带有线性约束的最小二乘问题。
共轭梯度法通过将线性约束转化为一系列的正交子空间，从而在求解最小二乘问题时能够更快地收敛。
无约束优化方法—共轭梯度法1.共轭梯度法共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算海赛矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。
其基本思想是利用负梯度方向，构造一共轭方向，使其尽快达到最优点。
共轭梯度法迭代过程如图1所示。
1X 2图1 共轭梯度法迭代过程()k 1x +点是沿()k x 点负梯度方向()()K k Sg =-搜索到的极值点。
如果接着从()k 1x +点出发，不是按着其负梯度方向()kg -搜索，而是沿着通过*x 点的方向()1K S +搜索，显然立即就能搜索到极值点*x 。
根据共轭理论，它们应当满足()()(1)1k Tk SAS+=即()KS 与()1K S +是互为共轭方向，新构造的共轭方向()1K S +，可由矢量合成，()(1)(1)()()2k k k k SgSβ++=-+()k β值可根据在极值点附近目标函数等值线近似为二次型函数的道理，推到出：()(1)(1)(1)2()()()()2||||3||||k T k k k k T k k gg g g g g β+++==利用两个点的梯度()k g和(1)k g+，就可以构造一个与梯度矢量为共轭的矢量()1K S +，沿着该方向搜索，即可求得极值点。
共轭梯度法程序框图如图2所示。
图2 共轭梯度法程序框图2. 共轭梯度法的应用用共轭梯度法计算22121212()52410f X x x x x x x =+---+ 的最优解，其中：初始点()0[1,1]T X =。
收敛精度ε=0.0001(1).共轭梯度法程序设计#include "stdio.h" #include "math.h"double fun1(double x1,double x2) {double y;y=x1*x1+x2*x2-5*x1*x2-2*x1-4*x2+10; return y; }double fun2(double g[],double d[]) {double buchang;buchang=-(g[0]*d[0]+g[1]*d[1])/(d[0]*(2*d[0]-5*d[1])+d[1]*(-5*d[0]+2*d[1])); return buchang; }main(){ double t, beta,x1=1,x2=1,d[2],g[4], y, m,e=0.0001; int k=1;g[0]=2*x1-5*x2-2; g[1]=2*x2-5*x1-4; m=(sqrt(g[0]*g[0]+g[1]*g[1]));while(m>e&&k<=200) { if (k==1) {d[0]=-g[0]; d[1]=-g[1];beta=0; } else {beta=(g[0]*g[0]+g[1]*g[1])/(g[2]*g[2]+g[3]*g[3]); d[0]=-g[0]+beta*d[0]; d[1]=-g[1]+beta*d[1]; }t=fun2(g,d); x1=x1+d[0]*t; x2=x2+d[1]*t; g[2]=g[0]; g[3]=g[1];g[0]= 2*x1-5*x2-2;g[1]= 2*x2-5*x1-4;m=sqrt(g[0]*g[0]+g[1]*g[1]); k++; }y=fun1(x1,x2);printf("迭代次数为k=%d\n",k);printf("分别输出x1=%f,x2=%f\n",x1,x2); printf("极小值y=%f",y); }(2).程序运行结果(3).结 论用共轭梯度法计算22121212()52410f X x x x x x x =+---+的最优解为*( 1.142857,0.857143)X =-- ,*()12.857143F X = 。
