最速下降法求解无约束最优化问题

黄金分割法1.运用0.618法求()2min 2+-=x x x f在区间]3,1[-上的极小点。

要求最终区间长度不大于原区间长度的0.08倍。

（计算结果精确到0.001）2.在区间[1,1]-上用黄金分割法求函数2()2f x x x =-+的极小点，求出初始的两个试点及保留区间。

无约束最优化问题1.（10分）用一阶必要和充分条件求解如下无约束优化问题的最优解：)1(632)(min 21212131----=x x x x x x x f .2.用共轭梯度法求解无约束优化问题22121212min 22x x x x x x ++-+取初始点0(0,0)T x =，精度为310-。

3.用最速下降法求解无约束问题 ()()()22213423min -+-=x x x f ，取初始点()()T x 3,41=。

有约束（有等式，无等式）1.考虑不等式约束问题},,2,1{,0)(..)(minm I i x c t s x f i =∈≤其中))((),(I i x c x f i ∈具有连续的偏导数，设x 是约束问题的可行点，若在x 处d 满足)(,0)(,0)(x I i d x c d x f T i T ∈<∇<∇则d 是x 处的可行下降方向。

2.考虑约束优化问题()221212min 4..3413f x x x s t x x =++≥用两种惩罚函数法求解。

建模问题某银行有投资资金0x ，投资于A,B 两个项目，计划5年为一个周期。

A,B 两个项目的资金回收率分别为a,b （01,01a b ≤<≤<）。

设第i 年（i ＝1，2，…,4）底根据现有投资资金i x 对A,B 两个项目的投资额做出决策，以i y 投资于A 项目，一年中可产生经济效益()i g y ，余额（i i x y -）投资于B 项目，一年可产生经济效益()i i h x y -，其中g,h 为两个单调非减函数（显然不投资则效益为0）.问每年底作何投资决策，可使在第5年底的总效益最大？试合理选择问题的特征量，建立特征量之间的定量关系，写出数学模型。

Matlab中的最优化问题求解方法近年来，最优化问题在各个领域中都扮演着重要的角色。

无论是在工程、经济学还是科学研究中，我们都需要找到最优解来满足特定的需求。

而Matlab作为一种强大的数值计算软件，在解决最优化问题方面有着广泛的应用。

本文将介绍一些Matlab中常用的最优化问题求解方法，并探讨其优缺点以及适用范围。

一. 无约束问题求解方法1. 最速下降法最速下降法是最简单且直观的无约束问题求解方法之一。

其基本思想是沿着梯度的反方向迭代求解，直到达到所需的精度要求。

然而，最速下降法的收敛速度通常很慢，特别是在局部极小值点附近。

2. 共轭梯度法共轭梯度法是一种改进的最速下降法。

它利用了无约束问题的二次函数特性，通过选择一组相互共轭的搜索方向来提高收敛速度。

相比于最速下降法，共轭梯度法的收敛速度更快，尤其适用于大规模优化问题。

3. 牛顿法牛顿法是一种基于二阶导数信息的优化方法。

它通过构建并求解特定的二次逼近模型来求解无约束问题。

然而，牛顿法在高维问题中的计算复杂度较高，并且需要矩阵求逆运算，可能导致数值不稳定。

二. 线性规划问题求解方法1. 单纯形法单纯形法是一种经典的线性规划问题求解方法。

它通过在可行域内进行边界移动来寻找最优解。

然而，当问题规模较大时，单纯形法的计算复杂度会大幅增加，导致求解效率低下。

2. 内点法内点法是一种改进的线性规划问题求解方法。

与单纯形法不同，内点法通过将问题转化为一系列等价的非线性问题来求解。

内点法的优势在于其计算复杂度相对较低，尤其适用于大规模线性规划问题。

三. 非线性规划问题求解方法1. 信赖域算法信赖域算法是一种常用的非线性规划问题求解方法。

它通过构建局部模型，并通过逐步调整信赖域半径来寻找最优解。

信赖域算法既考虑了收敛速度，又保持了数值稳定性。

2. 遗传算法遗传算法是一种基于自然进化过程的优化算法。

它模拟遗传操作，并通过选择、交叉和变异等操作来搜索最优解。

遗传算法的优势在于其适用于复杂的非线性规划问题，但可能需要较长的计算时间。

《MATLAB 程序设计实践》课程考核实践一、编程实现以下科学计算法，并举一例应用之。

（参考书籍《精通MATLAB 科学计算》，王正林等著，电子工业出版社，2009年）“最速下降法无约束最优化”最速下降法：解： 算法说明：最速下降法是一种沿着N 维目标函数的负梯度方向搜索最小值的方法。

原理：由高等数学知识知道任一点的负梯度方向是函数值在该点下降最快的方向，那么利用负梯度作为极值搜索方向，达到搜寻区间最速下降的目的。

而极值点导数性质，知道该点的梯度=0，故而其终止条件也就是梯度逼近于0，也就是当搜寻区间非常逼近极值点时，即：当▽f(a ）→0推出f(a ）→极值）（x f ，f(a ）即为所求。

该方法是一种局部极值搜寻方法。

函数的负梯度表示如下：-g(x ）=-▽f(x)=-⎢⎣⎡∂∂1)(x x f 2)(x x f ∂∂ … T N x x f ⎥⎦⎤∂∂)(搜索步长可调整，通常记为αk （第k 次迭代中的步长）。

该算法利用一维的线性搜索方法，如二次逼近法，沿着负梯度方向不断搜索函数的较小值，从而找到最优解。

方法特点（1）初始值可任选，每次迭代计算量小，存储量少，程序简短。

即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。

（2）任意相邻两点的搜索方向是正交的，它的迭代路径胃绕道逼近极小点。

当迭代点接近极小点时，步长变得很小，越走越慢。

（3）全局收敛，线性收敛，易产生扭摆现象而造成早停。

算法步骤：最速下降法的基本求解流程如下：第一步迭代次数初始化为k=0，求出初始点0x 的函数值f 0=f （0x ）。

第二步迭代次数加1，即k=k+1，用一维线性搜索方法确定沿负梯度方向-1-k g 的步长1k -α，其中1k -α=ArgMinaf （111k /----k k g g x α）。

第三步沿着负梯度方向寻找下一个接近最小值的点，其中步长为1k -α，得到下一点的坐标为：1111/-----=k k k k k g g x x α。

运筹学实习报告姓名： 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 在当前点处的负梯度方向，利用一维搜索法找出沿此方向上的最小值及其对应点，此后将该点作为新的出发点重复上述过程，直到达到允许的误差为止。

无约束优化算法无约束优化算法问题，是指优化问题的可行集为nR ，无约束的标准形式为： min ():n f x f R R →1. 最优性条件（1） 极小值点的一阶必要条件设():n f x R R →为连续可微函数，如果*x 为局部极小值点，则*x 为驻点，即梯度*()0f x ∇=。

（2） 极小值的二阶必要条件设():n f x R R →为二阶连续可微函数，如果*x 为局部极小值点，则*x 为驻点，即梯度*()0f x ∇=，二阶hesse 2*()f x ∇半正定。

（3） 极小值点的二阶充分条件设():n f x R R →为二阶连续可微函数，如果梯度*()0f x ∇=，二阶h e s s e 2*()f x ∇正定，则*x 为f 的局部极小值点，*n x R ∈。

以上三个定理为搜索最优点以及判断一个点是否为最优点的基本依据。

经典的优化算法的停止条件为*()0f x ∇=，例如在程序中*8()110f x -∇≤⨯ ，即在导数范数小于某特定误差限时停止。

误差限较大，则算法迭代次数减少，计算时间缩短，但解得质量降低；误差限较小，则算法迭代次数增加，计算时间增加，但解的质量提高；误差限一般为8110-⨯，可以根据实际情况设定合适的误差限。

当然，还有极小值点的二阶必要条件与极小值点的二阶充分条件，对2*()f x ∇的判断，由于目标函数比较复杂，二阶导数矩阵的计算量极大，所以一般算法都在迭代过程中对2()()k f x∇进行修正，得到2(1)()k f x +∇，在修正的过程中始终保持2*()f x ∇的正定性，以此方法解决极小值点的二阶条件问题。

2. 最速下降法2.1 算法原理最速下降法是早期的优化算法，其理论根据函数的一阶泰勒展开： 由()()()()Tf x d f x f x d d ααοα+=+∇+ 得到()()()()T f x d f x f x d d ααοα+-=∇+根据下降要求()()0f x d f x α+-≤ 故()()0Tf x d d αοα∇+≤实际中要求()0T f x d α∇≤根据上式选取合适的d ，得()0T f x d α∇≤。

最优化方法实验报告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 ）。

第五题：解：选择类型为：2/13()x ty t x ex =+其中123,,x x x 是待求参数。

根据最小二乘原理，参数123,,x x x 是下面优化问题的解。

[]281231m in (,,)()i i i f x x x y t y ==-å用最速下降法求解这一无约束的最优化问题。

zuiyouhua.mfunction sh=zuiyouhua(x0) % x0为初始猜测值 syms x y z a al;%====================================== t=[0.2,1,2,3,5,7,11,16];r1=[5.05,8.88,11.63,12.93,14.15,14.73,15.30,15.60]; minf=0; for i=1:8r(i)=x*exp(y/t(i))+z-r1(i); %构造最小二乘最优化的目标函数 minf=r(i)^2+minf;end%====================================== f1=diff(minf,x); f2=diff(minf,y);f3=diff(minf,z); %求目标函数的梯度 F=[f1,f2,f3];%====================================== Fx1= -subs(F,{x,y,z},x0); Fx=Fx1/norm(Fx1); k=0;%====================================== %最速下降法核心迭代程序 while 1 x1=x0+a*Fx;P=subs(minf,{x,y,z},x1);xx1=xianxing(P); %调用线性搜索函数 al=huangjing(P,xx1); %调用黄金分割法函数； x0=x0+al*Fx;Fx1= -subs(F,{x,y,z},x0); Fx=Fx1/norm(Fx1); if norm(Fx1)<5e-4 sh=x0;return; end end%====================================== function xx=xianxing(Pa) %一维搜索法线性搜索函数 aa=findsym(Pa); a1=1; h=0.5; k=0; t1=2; while 1 a2=a1+h;Pa1=subs(Pa,aa,a1); Pa2=subs(Pa,aa,a2); if Pa2< Pa1 h=t1*h; a0=a1; a1=a2; k=k+1;if k>1000disp('迭代步数太多，可能不收敛！'); end else if k==0 h=-h; a0=a2; elsec1=min(a0,a2); d1=max(a0,a2); xx=[c1,d1]; return; end endend%====================================== function al1=huangjing(Pb,xx2)%黄金分割法函数 ab=findsym(Pb); c=xx2(1); d=xx2(2);lamda=0.618;eps1=1e-3; u=d-lamda*(d-c); v=c+lamda*(d-c); N=1000; pu=subs(Pb,ab,u); pv=subs(Pb,ab,v); for K=1:Nif abs(v-u)<eps1 g=(u+v)/2; al1=g; return; endif pu <= pv c=c; d=v; v=u; pv=pu;u=d-lamda*(d-c); pu=subs(Pb,ab,u); else c=u; d=d; u=v; pu=pv;v=c+lamda*(d-c); pv=subs(Pb,ab,v); end if K==Ndisp('迭代次数过多，不收敛！'); end end%==================================== >> x0=[0,0,0]; >> zuiyouhua(x0) ans =11.3459 -1.0730 4.9972所以：12311.3459, 1.0730, 4.9972x x x ==-=%=====================================================================================画图程序：x=[11.3459,-1.0730,4.9972];tdata=[0.2,1,2,3,5,7,11,16];ydata=[5.05,8.88,11.63,12.93,14.15,14.73,15.30,15.60];f=x(1)*exp(x(2)./tdata)+x(3); plot(tdata,ydata,'o',tdata,f,'r-')计算所得得图为：。