下载文档原格式
最速下降法1.最速下降⽅向函数f(x)在点x处沿⽅向d的变化率可⽤⽅向导数来表⽰。
对于可微函数，⽅向导数等于梯度与⽅向的内积，即：Df(x;d) = ▽f(x)Td,因此，求函数f(x)在点x处的下降最快的⽅向，可归结为求解下列⾮线性规划：min ▽f(x)Tds.t. ||d|| ≤ 1当 d = -▽f(x) / ||▽f(x)||时等号成⽴。
因此，在点x处沿上式所定义的⽅向变化率最⼩，即负梯度⽅向为最速下降⽅向。
2.最速下降算法最速下降法的迭代公式是x(k+1) = x(k) + λkd(k) ,其中d(k)是从x(k)出发的搜索⽅向，这⾥取在x(k)处的最速下降⽅向，即d = -▽f(x(k)).λk是从x(k)出发沿⽅向d(k)进⾏⼀维搜索的步长，即λk满⾜f(x(k) + λkd(k)) = min f(x(k)+λd(k)) (λ≥0).计算步骤如下：(1)给定初点x(1) ∈ Rn，允许误差ε> 0，置k = 1。
(2)计算搜索⽅向d = -▽f(x(k))。
(3)若||d(k)|| ≤ ε，则停⽌计算；否则，从x(k)出发，沿d(k)进⾏⼀维搜索，求λk，使f(x(k) + λkd(k)) = min f(x(k)+λd(k)) (λ≥0).(4)令x(k+1) = x(k) + λkd(k) ，置k = k + 1，转步骤(2)。
共轭梯度法1.共轭⽅向⽆约束问题最优化⽅法的核⼼问题是选择搜索⽅向。
以正定⼆次函数为例，来观察两个⽅向关于矩阵Ａ共轭的⼏何意义。
设有⼆次函数：f(x) = 1/2 (x - x*)TA(x - x*) ,其中A是n×n对称正定矩阵，x*是⼀个定点，函数f(x)的等值⾯1/2 (x - x*)TA(x - x*) = c是以x*为中⼼的椭球⾯，由于▽f(x*) = A(x - x*) = 0，A正定，因此x*是f(x)的极⼩点。
设x(1)是在某个等值⾯上的⼀点，该等值⾯在点x(1)处的法向量▽f(x(1)) = A(x(1) - x*)。
Matlab中的最优化问题求解方法近年来，最优化问题在各个领域中都扮演着重要的角色。
无论是在工程、经济学还是科学研究中，我们都需要找到最优解来满足特定的需求。
而Matlab作为一种强大的数值计算软件，在解决最优化问题方面有着广泛的应用。
本文将介绍一些Matlab中常用的最优化问题求解方法，并探讨其优缺点以及适用范围。
一. 无约束问题求解方法1. 最速下降法最速下降法是最简单且直观的无约束问题求解方法之一。
其基本思想是沿着梯度的反方向迭代求解，直到达到所需的精度要求。
然而，最速下降法的收敛速度通常很慢，特别是在局部极小值点附近。
2. 共轭梯度法共轭梯度法是一种改进的最速下降法。
它利用了无约束问题的二次函数特性，通过选择一组相互共轭的搜索方向来提高收敛速度。
相比于最速下降法，共轭梯度法的收敛速度更快，尤其适用于大规模优化问题。
3. 牛顿法牛顿法是一种基于二阶导数信息的优化方法。
它通过构建并求解特定的二次逼近模型来求解无约束问题。
然而，牛顿法在高维问题中的计算复杂度较高，并且需要矩阵求逆运算，可能导致数值不稳定。
二. 线性规划问题求解方法1. 单纯形法单纯形法是一种经典的线性规划问题求解方法。
它通过在可行域内进行边界移动来寻找最优解。
然而，当问题规模较大时，单纯形法的计算复杂度会大幅增加，导致求解效率低下。
2. 内点法内点法是一种改进的线性规划问题求解方法。
与单纯形法不同，内点法通过将问题转化为一系列等价的非线性问题来求解。
内点法的优势在于其计算复杂度相对较低，尤其适用于大规模线性规划问题。
三. 非线性规划问题求解方法1. 信赖域算法信赖域算法是一种常用的非线性规划问题求解方法。
它通过构建局部模型，并通过逐步调整信赖域半径来寻找最优解。
信赖域算法既考虑了收敛速度，又保持了数值稳定性。
2. 遗传算法遗传算法是一种基于自然进化过程的优化算法。
它模拟遗传操作，并通过选择、交叉和变异等操作来搜索最优解。
遗传算法的优势在于其适用于复杂的非线性规划问题，但可能需要较长的计算时间。
运筹学实习报告姓名： xxxxxxxxxx 学号： xxxxxxxxxxx 专业班级： xxxxxxxxxxxx 2 0 1 3年 7 月 0 4 日题目：用最速下降法求解无约束非线性规划问题 摘要：无约束最优化问题的求解方法分为解析法和直接法两大类。
解析法需要计算函数的梯度，其中最速下降法就属于解析法中的一种。
对于一个无约束非线性规划利用最速下降法求解，首先需要确定其优化方向，此优化方向应该选择为f 在当前点处的负梯度方向，利用一维搜索法找出沿此方向上的最小值及其对应点，此后将该点作为新的出发点重复上述过程，直到达到允许的误差为止。
本文通过理论的计算方法，进一步分析，最后用c++编程实现求出允许误差内的最优解。
此编程可用于计算符合下列形式的函数求最优解过程：f(x)=a[0]x1*x1+a[1]x2*x2+a[2]x1*x2+a[3]x1+a[4]x2+a[5]其中：a[i] (i=0,1,2,3,4,5) 为函数的系数。
本文以“ 李占利 主编，中国矿业大学出版社出版”的《最优化理论与方法》 第五章 “无约束最优化方法，5.1 最速下降法 ”例5—1为实例，首先利用上述迭代的方法，计算出各迭代点的函数值，梯度及其模。
然后应用c++语言编程，得到在精度范围内的精确最优解。
C++编程计算的最优解为 : T x x ]0329218.0,00823045.0[)3(*-==。
即转化为分数结果为：⎥⎦⎤⎢⎣⎡-==412432)3(*x x 。
满足精度要求的模为：1010736154.0||||)3(=<=εp 。
关键词：无约束非线性规划 解析法 最速下降法 梯度 模 最优解一、算法思想无约束最优化方法中的最速下降法首先需要确定其优化方向，此优化方向应该选择为f 在当前点处的负梯度方向，利用一维搜索法找出沿此方向上的最小值及其对应点，此后将该点作为新的出发点重复上述过程，直到达到允许的误差为止。
用Matlab实现非线性无约束优化的几种方法比较王娜;朱逸夫【摘要】在实际规划问题的求解过程中,优化解的真值具有不可预知性,为了寻找可用的稳定解,往往需要用不同的算法进行试算,并对所有计算结果进行甄别,这需要应用者具备良好的经验.为此,利用Matlab工具箱中的fminunc和fminsearch命令格式,并根据牛顿法、拟牛顿法、最速下降法、阻尼牛顿法和修正牛顿法等方法,分别编程实现在经典算例中求解无约束非线性优化问题,并对计算结果进行了比较和分析.【期刊名称】《长春工程学院学报（自然科学版）》【年(卷),期】2018(019)004【总页数】5页(P95-99)【关键词】非线性规划;Matlab;无约束优化;一维搜索;搜索方向【作者】王娜;朱逸夫【作者单位】长春工程学院教务处 ,长春 130012;长春工程学院计算机技术与工程学院 ,长春 130012【正文语种】中文【中图分类】TP3910 引言非线性无约束最优化技术是一门实践性很强的方法，应用者往往要在实践中不断地总结[1-4]。
对有些应用者来说，不必要浪费了大量的时间和精力，系统而深入地学习优化算法及公式，他们只希望能够快速地找到有效的解法、合适的优化软件，并能在计算机上尽快地求出问题的解[5]。
为此本文针对非线性无约束优化模型，利用几种不同的Matlab求解非线性无约束优化问题的调用格式，或根据无约束优化的算法编程进行求解，并进行解的比较和分析，提高非线性规划模型的应用效果和能力。
1 非线性无约束优化的基本理论设无约束非线性规划的模型为minf(x)，x=(x1，x2，…，xn)T∈Rn，(1)求解无约束优化问题的主要思想是下降算法：每一步都要求函数值有所下降，其迭代格式为x(k+1)=x(k)+αkd(k)，即对应于点列{xk}上的函数值列{f(xk)}必须是逐渐减小的，或者至少是不增加的，因而有f(x0)≥f(x1)≥…≥f(xk)≥f(xk+1)≥…(2)我们还要求这些点列收敛于全局最优解。
毕业论文题目非线性最优化计算方法与算法学院数学科学学院专业信息与计算科学班级计算1201学生陶红学号20120921104指导教师邢顺来二〇一六年五月二十五日摘要非线性规划问题是一般形式的非线性最优化问题。
本文针对非线性规划的最优化问题进行方法和算法分析。
传统的求解非线性规划的方法有最速下降法、牛顿法、可行方向法、函数逼近法、信赖域法，近来研究发现了更多的求解非线性规划问题的方法如遗传算法、粒子群算法。
本文对非线性规划分别从约束规划和无约束规划两个方面进行理论分析。
利用最速下降法和牛顿法两种典型算法求解无约束条件非线性规划问题，通过MATLAB程序求解最优值，探讨其收敛性和稳定性。
另外给出了阻尼牛顿法，探讨其算法的收敛性和稳定性，求解无约束非线性规划比牛顿法的精确度更高，收敛速度更快。
惩罚函数是经典的求解约束非线性的方法，本文采用以惩罚函数法为核心的遗传算法求解有约束条件非线性规划问题，通过MATLAB程序求解最优值，探讨其收敛性和稳定性。
并改进遗传算法，给出适应度函数，通过变换适应度函数，提高算法的收敛性和稳定性。
关键词：非线性规划；最速下降法；牛顿法；遗传算法ABSTRACTNonlinear programming problem is the general form of the nonlinear optimization problem. In this paper, we carry on the analysis of the method and algorithm aiming at the optimization problem of nonlinear programming. The traditional methods of solving nonlinear programming problems include steepest descent method, Newton method, the feasible direction method, function approximation method and trust region method. Recent studies found more method of solving nonlinear programming problems, such as genetic algorithm, particle swarm optimization (pso) algorithm. In this paper, the nonlinear programming is analyzed from two aspects: the constraint programming and the unconstrained programming.We solve unconstrained condition nonlinear programming problem by steepest descent method and Newton's method, and get the optimal value through MATLAB. Then the convergence and stability are discussed. Besides, the damped Newton method is furnished. By discussing the convergence and stability of the algorithm, the damped Newton method has higher accuracy and faster convergent speed than Newton's method in solving unconstrained nonlinear programming problems.Punishment function is a classical method for solving constrained nonlinear. This paper solves nonlinear programming problem with constraints by using genetic algorithm method, the core of which is SUMT. Get the optimal value through MATLAB, then the convergence and stability are discussed. Improve genetic algorithm, give the fitness function, and improve the convergence and stability of the algorithm through transforming the fitness function.Key words：Nonlinear Programming; Pteepest Descent Method; Newton Method; GeneticAlgorithm目录摘要 (I)ABSTRACT .......................................................................................................................... I I 1 前言 .. (4)1.1 引言 (4)1.2 非线性规划的发展背景 (5)1.3 国内外研究现状 (5)1.4 研究主要内容及研究方案 (6)1.4.1 研究的主要内容 (6)1.4.2 研究方案 (6)1.5 研究难点 (7)2 预备知识 (8)2.1 向量和矩阵范数 (8)2.1.1 常见的向量范数 (8)2.1.2 谱范数 (9)2.2符号和定义 (9)2.3 数值误差 (10)2.4 算法的稳定性 (10)2.5 收敛性 (12)3 非线性规划模型 (13)3.1 非线性规划模型 (13)3.2 无约束非线性规划 (14)3.2.1 最速下降法 (16)3.2.2 牛顿法 (18)3.2.2 阻尼牛顿法 (18)3.3 约束非线性规划 (20)3.3.1 惩罚函数法 (21)3.3.2 遗传算法 (21)3.3.3 自适应遗传算法 (22)结论 (26)参考文献 (27)致谢 (28)附录 (29)1 前言1.1 引言我们知道最优化是一门很古老的求极值问题，最优化在求解线性规划，非线性规划，随机规划，多目标规划，非光滑规划，整数规划，几何规划等方面研究得到迅速发展。
《最优化方法》1一、填空题：1 •最优化问题的数学模型一般为：_____________________________ ,其中___________ 为目标函数， _____________ 为约束函数，可行域D可以表示为 _______________________________ ，若 _______________________________ ，称x*为问题的局部最优解，若 _________________________________________ 称X*为问题的全局最优解。
2 •设f(x)= 2x1 2x1X2 X i 5X2 ,则其梯度为_______________________ ,海色矩阵___________ ,令x (1,2)T,d (1,0)T,则f(x)在x处沿方向d的一阶方向导数为___________ 几何意义为________________________________________ 二阶方向导数为 ____________________ ,几何意义为_____________________________3 •设严格凸二次规划形式为：min f (x) 2x； 2x| 2x1x2s.t. 2x1x21x10x20则其对偶规划为4•求解无约束最优化问题：min f(x), x R n，设x k是不满足最优性条件的第k 步迭代点，则:用最速下降法求解时，搜索方向d k= ___________用Newton法求解时，搜索方向d k= ____________用共轭梯度法求解时，搜索方向 d k= ________________二.(10分)简答题：试设计求解无约束优化问题的一般下降算法。
三.(25分)计算题1. (10分)用一阶必要和充分条件求解如下无约束优化问题的最优解：3 2min f (x) 2x! 3为6x^2(^ x21).2. ( 15分)用约束问题局部解的一阶必要条件和二阶充分条件求约束问题:min f (x) x1x22 2s.t. c(x) % X2 1 0的最优解和相应的乘子。
运筹学实习报告姓名： xxxxxxxxxx 学号： xxxxxxxxxxx 专业班级： xxxxxxxxxxxx 2 0 1 3年 7 月 0 4 日题目：用最速下降法求解无约束非线性规划问题摘要：无约束最优化问题的求解方法分为解析法和直接法两大类。
解析法需要计算函数的梯度，其中最速下降法就属于解析法中的一种。
对于一个无约束非线性规划利用最速下降法求解，首先需要确定其优化方向，此优化方向应该选择为f 在当前点处的负梯度方向，利用一维搜索法找出沿此方向上的最小值及其对应点，此后将该点作为新的出发点重复上述过程，直到达到允许的误差为止。
本文通过理论的计算方法，进一步分析，最后用c++编程实现求出允许误差内的最优解。
此编程可用于计算符合下列形式的函数求最优解过程：f(x)=a[0]x1*x1+a[1]x2*x2+a[2]x1*x2+a[3]x1+a[4]x2+a[5]其中：a[i] (i=0,1,2,3,4,5) 为函数的系数。
本文以“ 李占利 主编，中国矿业大学出版社出版”的《最优化理论与方法》 第五章 “无约束最优化方法，5.1 最速下降法 ”例5—1为实例，首先利用上述迭代的方法，计算出各迭代点的函数值，梯度及其模。
然后应用c++语言编程，得到在精度范围内的精确最优解。
C++编程计算的最优解为 : Tx x ]0329218.0,00823045.0[)3(*-==。
即转化为分数结果为：⎥⎦⎤⎢⎣⎡-==412432)3(*xx 。
满足精度要求的模为：1010736154.0||||)3(=<=εp 。
关键词：无约束非线性规划 解析法 最速下降法 梯度 模 最优解一、算法思想无约束最优化方法中的最速下降法首先需要确定其优化方向，此优化方向应该选择为f 在当前点处的负梯度方向，利用一维搜索法找出沿此方向上的最小值及其对应点，此后将该点作为新的出发点重复上述过程，直到达到允许的误差为止。
主要依据解无约束非线性规划问题的最速下降法计算步骤进行设计算法。
具体步骤如下：第1步 选取初始点0x ，给定终止误差 ε>0，令k=0；第2步 计算()k f x ∇，若()k f x ε∇≤，停止迭代，输出k x ，否则进行第3步；第3步 取()k kp f x =-∇； 第4步 进行一维搜索，求k λ，使得0()min ()k k k k k k f x p f x p λλ≥+=+，令1k k kk x x p λ+=+，k=k+1。
转第2步。
由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点。
依据以上步骤就可以用C++编程实现最速下降法求解最优解的算法。
二、算法流程图三、程序代码#include<iostream.h> #include<math.h>double lamda(double x[2],double p[2],double a[2]) { double lam1,lam2; lam1=(pow(a[0],3)*x[0]*x[0]+pow(a[1],3)*x[1]*x[1]); lam2=-(pow(a[0]*x[0],2)+pow(a[1]*x[1],2)); double s;停()k x x *=取(0)x，1.0=εk:=0计算()()()k k pf x =-∇()?k pε≤是否求()k λ()()()()()0()()min k k k k k f x p f x p λλλ≥+=+令(1)()()()k k k k x x p λ+=+k:=k+1s=-lam2/(2*lam1);return s;}void main(){cout<<"@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@"<<endl;cout<<"@@ 最速下降法求解最优解程序运行结果@@"<<endl;cout<<"@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@"<<endl;cout<<endl;double lamd,x[3],a[6];double p[2],g[2],e,y,m,n;int i=0;cout<<"请输入精度e"<<endl;cin>>e;cout<<"请输入初始点x[0],x[1]的值：\n"<<endl;cin>>m;cin>>n;x[0]=m;x[1]=n;cout<<"函数通式为f(x)=a[0]x1*x1+a[1]x2*x2+a[2]x1*x2+a[3]x1+a[4]x2+a[5]"<<endl;cout<<"请依次输入函数的系数：a[0]、a[1]、a[2]、a[3]、a[4]、a[5]:"<<endl;for(i=0;i<6;i++)cin>>a[i];p[0]=(2*a[0]*x[0]+a[2]*x[1]+a[3]);p[1]=(2*a[1]*x[1]+a[2]*x[0]+a[4]);g[0]=-p[0];g[1]=-p[1];i=0;cout<<endl;while(sqrt(g[0]*g[0]+g[1]*g[1])>e&&i<=200){lamd=lamda(x,g,a);x[0]=x[0]+lamd*g[0];x[1]=x[1]+lamd*g[1];p[0]=2*a[0]*x[0]; p[1]=2*a[1]*x[1]; g[0]=-p[0]; g[1]=-p[1]; i++;cout<<"******************************************"<<endl; cout<<"第"<<i<<"次迭代结果："<<endl; cout<<"p 的模为："<<sqrt(g[0]*g[0]+g[1]*g[1])<<endl; cout<<"x 的值"<<x[0]<<" "<<x[1]<<endl; cout<<"******************************************"<<endl; cout<<endl; } y=(a[0]*x[0]*x[0]+a[1]*x[0]*x[1]+a[2]*x[0]*x[1]+a[3]*x[0]+a[4]*x[1]+a[5]);cout<<"此时满足精度要求的p 的模为:"<<sqrt(g[0]*g[0]+g[1]*g[1])<<endl; cout<<endl;cout<<"满足精度的最优近似结果x[1],x[2]分别为："<<endl; cout<<"x[1]="<<x[0]<<endl; cout<<"x[2]="<<x[1]<<endl; cout<<endl; cout<<"满足进度要求所得的最优值为："<<endl; cout<<"minf(x)="<<y<<endl; }四、例子与结果例子为“ 李占利 主编，中国矿业大学出版社出版”的《最优化理论与方法》第五章 “无约束最优化方法，5.1 最速下降法 ”例5—1。
用最速下降法求解22212)(min x x x f +=，初始迭代点⎥⎦⎤⎢⎣⎡=11)0(x ，精度为1.0=ε。
则体现在程序中很明显有：a[0]=2,a[1]=1,a[2]=a[3]=a[4]=a[5]=0;e=0.1；x[0]=x[1]=1;则程序运行结果为：即在允许的精度范围内22212)(min x x x f +=，初始迭代点⎥⎦⎤⎢⎣⎡=11)0(x ，精度为1.0=ε。
得到在精度范围内的精确最优解为：T x x ]0329218.0,00823045.0[)3(*-==，即⎥⎦⎤⎢⎣⎡-==412432)3(*x x 。
满足精度要求的模为：1010736154.0||||)3(=<=εp 。
五、结论与总结最速下降法为最优化万千方法中的一种，要想更好地利用最优化方法解决我们身边的问题，光靠这一种方法远远不够。
因此我必须要好好掌握其他的各种方法。
还有通过这次实习让我深深认识到，并不是所有的问题都能够手工完成的，我们平常接触的例题，都非常基础，那完全可以手工计算得到答案，但如果问题比较复杂时，我们是没有办法用手工完成的。
所以我们必须借助计算机来解决那些复杂的问题。
因此这就要求我们必须要熟练掌握编程技巧，要能够把实际的复杂问题通过编写程序来解决它。
还有此次用最速下降法求解最优解的程序，我编的还不够完美，还有很多不足之处，只能用于研究二元函数的最优解问题，不能进行其他的更深入的研究，所以还有很多改进的地方，以后我还要继续努力。
对于编程一定要多练、多动手操作，通过这次实习让我深深地认识到，光靠理论知识是不行的，理论知道再多，如果不动手实践的话照样编不出程序，只有在实践中，在编写程序的过程中我们才能发现自己的不足，才能知道问题出在哪儿。
所以无论学习什么编程语言，我今后一定要多动手，今后无论学习什么我都要勤动手，多动手，多写，多练。
六、参考文献[1]龚尚福，贾澎涛. C/C++语言程序设计 [M].徐州：中国矿业大学出版社，2006.12.[2]李占利，张卫国.最优化理论与方法[M].徐州：中国矿业大学出版社，2012.8.[3]范玉妹，徐尔.数学规划及其应用 [M].北京：冶金工业出版社，2009.9.[4]孙文瑜，徐成贤，朱德通. 最优化方法 [M].北京：高等教育出版社，2004.8.。
