最优化：最速下降法和Newton法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最速下降法与牛顿法及其区别摘要：无约束优化方法是优化技术中极为重要和基本内容之一。

它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后用无约束优化方法来求解。

最速下降法和牛顿法是比较常见的求解无约束问题的最优化方法，这两种算法作为基本算法，在最优化方法中占有重要的地位。

其中最速下降法又称梯度法，其优点是工作量少，存储变量较少，初始点要求不高；缺点是收敛慢，效率低。

牛顿法的优点是收敛速度快；缺点是对初始点要求严格，方向构造困难，计算复杂且占用内存较大。

同时，这两种算法的理论和方法渗透到许多方面，特别是在军事、经济、管理、生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。

因此，研究最速下降法和牛顿法的原理及其算法对我们有着及其重要的意义。

关键字：无约束优化最速下降法牛顿法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一、算法的基本原理1.1 最速下降法的基本原理在基本迭代公式k k k k P t X X +=+1中，每次迭代搜索方向k P 取为目标函数)(X f 的负梯度方向，即)(k k X f P -∇=，而每次迭代的步长k t 取为最优步长，由此确定的算法称为最速下降法。

1、最速下降法function f=fun_obj(x)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;function g=fun_grad(x)g=[2*x(1)-400*x(1)*(-x(1)^2+x(2))-2,-200*x(1)^2+200*x(2)];% 用armijo搜索确定步长，其中xk是当前迭代点,rho,sigma为armijo参数，gk为当前下降方向function mk=armijo(xk,rho,sigma,gk )%assert(rho>0&&rho<1); % 限制Armijo参数rho在(0,1)之间%assert(sigma>0&&sigma<0.5); % 限制Armijo参数sigma在(0,0.5)之间mk=0;max_mk=100; % 最大迭代次数while mk<=max_mkx=xk+rho^mk*gk; % 求解x(k+1)iffeval('fun_obj',x)<=feval('fun_obj',xk)-sigma*rho^mk*(fun_grad(xk))*g k' %终止条件break;endmk=mk+1; % 更新迭代endfunction [xk,fk,k]=steepestmain(x0)max_iter=5000; % max number of iterationsEPS=1e-6; % threshold of gradient normrho=0.8;sigma=0.59; % Armijo parametersk=0;xk=x0; % initializationwhile k<max_iterdk=fun_grad(xk);d=-dk; % search directionif norm(dk)<EPS %precisionbreak;endmk=armijo(xk,rho,sigma,d); %armijo line searchxk=xk+rho^mk*d; %updatefk=fun_obj(xk);k=k+1;endx0=[-1,2];[xk,fk,k]=steepestmain(x0);2、Newton法function f=fun_obj(x)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;function g=fun_grad(x)g=[2*x(1)-400*x(1)*(-x(1)^2+x(2))-2,-200*x(1)^2+200*x(2)];function He=Hess(x)He=[1200*x(1)^2-400*x(2)+2,-400*x(1);-400*x(1),200];% 用armijo搜索确定步长，其中xk是当前迭代点,rho,sigma为armijo参数，gk为当前下降方向function mk=armijo(xk,rho,sigma,gk )%assert(rho>0&&rho<1); % 限制Armijo参数rho在(0,1)之间%assert(sigma>0&&sigma<0.5); % 限制Armijo参数sigma在(0,0.5)之间mk=0;max_mk=100; % 最大迭代次数while mk<=max_mkx=xk+rho^mk*gk; % 求解x(k+1)iffeval('fun_obj',x)<=feval('fun_obj',xk)-sigma*rho^mk*(fun_grad(xk))*g k' %终止条件break;endmk=mk+1; % 更新迭代endfunction [xk,fk,k]=Newtonmain(x0)max_iter=5000; % 最大迭代次数EPS=1e-6; % 精度rho=1;sigma=1e-4; % Armijo 参数k=0;xk=x0; % 初值while k<max_iter % 迭代次数超过最大迭代次数时跳出循环k=k+1;dk=fun_grad(xk); % x(k)处的梯度H=Hess(xk); % x(k)处的Hessian矩阵d=-H\dk'; % x(k)处的搜索方向if norm(dk)<EPS % 终止条件break;endmk=armijo(xk,rho,sigma,d'); % 利用armijo搜索确定步长xk=xk+rho^mk*d'; % 计算x(k+1)的值fk=fun_obj(xk); % 计算x(k+1)处函数的值endx0=[1.2,1.2];[xk,fk,k]=Newtonmain(x0);3、Newton-最速下降法function f=fun_obj(x)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;function g=fun_grad(x)g=[2*x(1)-400*x(1)*(-x(1)^2+x(2))-2,-200*x(1)^2+200*x(2)];function He=Hess(x)He=[1200*x(1)^2-400*x(2)+2,-400*x(1);-400*x(1),200];% 用armijo搜索确定步长，其中xk是当前迭代点,rho,sigma为armijo参数，gk为当前下降方向function mk=armijo(xk,rho,sigma,gk )%assert(rho>0&&rho<1); % 限制Armijo参数rho在(0,1)之间%assert(sigma>0&&sigma<0.5); % 限制Armijo参数sigma在(0,0.5)之间mk=0;max_mk=100; % 最大迭代次数while mk<=max_mkx=xk+rho^mk*gk; % 求解x(k+1)iffeval('fun_obj',x)<=feval('fun_obj',xk)-sigma*rho^mk*(fun_grad(xk))*g k' %终止条件break;endmk=mk+1; % 更新迭代endfunction [xk,fk,k]=newton_steepest(x0)max_iter=5000; % 最大迭代次数EPS=1e-6; % 精度rho=1;sigma=1e-4; % Armijo 参数 rho=0.8;sigma=0.59;k=0;xk=x0; % 初值while(k<max_iter)k=k+1;dk=fun_grad(xk); % x(k)处的梯度，注意dk为行向量G=Hess(xk); % x(k)处的Hessian矩阵d=-G\dk'; % x(k)处的搜索方向,注意此时d为列向量if norm(dk)<EPS % x(k)处的搜索方向break;end%% 判断d是否为下降方向if d'*dk'<0 % 若d'*dk<0,则d为下降方向d=d;else% 若d'*dk>=0,则d不为下降方向，令下降方向为负梯度方向 d=-dk';endmk=armijo(xk,rho,sigma,d'); % 利用armijo搜索确定步长 xk=xk+rho^mk*d'; % 计算x(k+1)的值fk=fun_obj(xk); % 计算x(k+1)处函数的值endx0=rand(1,2000);[xk,fk,k]=newton_steepest(x0);。

机器学习算法系列最速下降法牛顿法拟牛顿法最速下降法（Gradient Descent）最速下降法是一种常用的优化算法，用于求解无约束的最小化问题。

其原理是通过不断迭代更新参数的方式来逼近最优解。

在最速下降法中，每次迭代的方向是当前位置的负梯度方向，即沿着目标函数下降最快的方向前进。

具体地，对于目标函数f(x)，在当前位置x_k处的梯度为g_k=▽f(x_k)，则下一次迭代的位置x_{k+1}可以通过以下公式计算：x_{k+1}=x_k-α*g_k其中，α 是一个称为学习率（learning rate）的参数，用于控制每次迭代的步长。

最速下降法的优点是简单易实现，收敛速度较快。

然而，它也有一些缺点。

首先，最速下降法的收敛速度依赖于学习率的选择，过小的学习率会导致收敛速度过慢，而过大的学习率可能会导致跳过最优解。

其次，最速下降法通常会在目标函数呈现弯曲或者高度相关的情况下表现不佳，很难快速收敛到最优解。

牛顿法（Newton's Method）牛顿法是一种通过二阶导数信息来优化的算法，可以更快地收敛到目标函数的最优解。

在牛顿法中，每次迭代的位置x_{k+1}可以通过以下公式计算：x_{k+1}=x_k-(H_k)^{-1}*▽f(x_k)其中，H_k是目标函数f(x)在当前位置x_k处的黑塞矩阵。

黑塞矩阵描述了目标函数的二阶导数信息，可以帮助更准确地估计参数的更新方向。

牛顿法的优点是收敛速度较快，特别是对于目标函数呈现弯曲或者高度相关的情况下，相较于最速下降法可以更快地达到最优解。

然而，牛顿法也有一些缺点。

首先，计算黑塞矩阵的代价较高，尤其是当参数较多时。

其次，黑塞矩阵可能不可逆或者计算代价较大，这时可以通过使用拟牛顿法来避免。

拟牛顿法（Quasi-Newton Method）拟牛顿法是一类基于牛顿法的优化算法，通过估计黑塞矩阵的逆来逼近最优解，从而避免了计算黑塞矩阵的代价较高的问题。

在拟牛顿法中，每次迭代的位置x_{k+1}可以通过以下公式计算：x_{k+1}=x_k-B_k*▽f(x_k)其中，B_k是一个对黑塞矩阵逆的估计。

最速下降法和牛顿法【引言】在数学和计算机领域中，最速下降法和牛顿法都是经典的优化算法。

它们在不同的问题中有着不同的应用，但它们都是以误差最小化为目标，寻找最优解的算法。

本文将对这两个算法进行详细介绍，以帮助读者更好地理解它们的应用和优缺点。

【正文一：最速下降法】最速下降法，又称为梯度下降法，是一种基于梯度的优化算法。

在寻找某个函数的最小值时，最速下降法的思路是从任何一个点出发，按照函数梯度的反方向移动，直到到达最小值处为止。

因此，最速下降法的关键就是确定每一步移动的方向和步长。

最速下降法的优点是简单易懂，可以用于解决大多数的优化问题。

在逃避局部最优解的情况下，其效果非常好。

然而，最速下降法也有缺点。

由于只是按照梯度的反方向移动，可能会产生震荡现象，从而导致计算速度缓慢等问题。

【正文二：牛顿法】与最速下降法不同，牛顿法是一种利用二阶导数信息，在每个迭代步骤中更新预测的最优解的优化算法。

它可以更快地收敛于函数的极小值点。

在求解非线性方程组、多项式拟合和机器学习等问题时，牛顿法是一种有效的优化算法。

与最速下降法相比，牛顿法的优点是其快速收敛和高效性。

但是，缺点是它需要耗费更多的时间和计算能力来求解每一步迭代。

在某些情况下，由于Hessian矩阵可能不可逆或昂贵，因此此算法的实现可能具有挑战性。

【正文三：最速下降法 VS 牛顿法】最速下降法和牛顿法各有优缺点，它们在不同的问题中应用广泛。

在求解凸优化问题时，最速下降法的效果比较好，在处理大量数据时，牛顿法更加高效。

在实际应用中，可以根据具体问题的不同，选择合适的优化算法。

【结尾】综上所述，最速下降法和牛顿法是经典的优化算法，它们在各自的领域都有着广泛的应用。

两种算法都有其优点和缺点，要选择哪一种算法取决于具体问题和可行性的考虑。

本文的介绍，希望能够帮助读者更好地理解这两种算法，并在实际问题中正确应用它们。

最优化算法（⽜顿、拟⽜顿、梯度下降）1、⽜顿法 ⽜顿法是⼀种在实数域和复数域上近似求解⽅程的⽅法。

⽅法使⽤函数f (x)的泰勒级数的前⾯⼏项来寻找⽅程f (x) = 0的根。

⽜顿法最⼤的特点就在于它的收敛速度很快。

具体步骤： ⾸先，选择⼀个接近函数f (x)零点的x0，计算相应的f (x0) 和切线斜率f ' (x0)（这⾥f ' 表⽰函数f 的导数）。

然后我们计算穿过点(x0, f (x0)) 并且斜率为f '(x0)的直线和x 轴的交点的x坐标，也就是求如下⽅程的解： 我们将新求得的点的x 坐标命名为x1，通常x1会⽐x0更接近⽅程f (x) = 0的解。

因此我们现在可以利⽤x1开始下⼀轮迭代。

迭代公式可化简为如下所⽰： 已经证明，如果f ' 是连续的，并且待求的零点x是孤⽴的，那么在零点x周围存在⼀个区域，只要初始值x0位于这个邻近区域内，那么⽜顿法必定收敛。

并且，如果f ' (x)不为0, 那么⽜顿法将具有平⽅收敛的性能. 粗略的说，这意味着每迭代⼀次，⽜顿法结果的有效数字将增加⼀倍。

下图为⼀个⽜顿法执⾏过程的例⼦。

由于⽜顿法是基于当前位置的切线来确定下⼀次的位置，所以⽜顿法⼜被很形象地称为是"切线法"。

⽜顿法的搜索路径（⼆维情况）如下图所⽰： ⽜顿法搜索动态⽰例图：2、拟⽜顿法（Quasi-Newton Methods） 拟⽜顿法是求解⾮线性优化问题最有效的⽅法之⼀，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。

Davidon设计的这种算法在当时看来是⾮线性优化领域最具创造性的发明之⼀。

不久R. Fletcher和M. J. D. Powell证实了这种新的算法远⽐其他⽅法快速和可靠，使得⾮线性优化这门学科在⼀夜之间突飞猛进。

拟⽜顿法的本质思想是改善⽜顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使⽤正定矩阵来近似Hessian矩阵的逆，从⽽简化了运算的复杂度。

牛顿法：函数fun，初值x0，误差e，结果x例子：fun=x^4-4*x^3-6*x^2-16*x+4function [x]=newton(fun,x0,e)f1=diff(fun);f2=diff(fun,2);x=x0-subs(f1,x0)/subs(f2,x0);while (abs(x-x0)>=e)x0=x;x=x0-subs(f1,x0)/subs(f2,x0);end平分法：函数fun，初始区间（a，b），误差e，结果x 例子：fun=3*x^4-16*x^3+30*x^2-24*x+8function [x]=pingfen(fun,a,b,e)x=(a+b)/2;f1=diff(fun);while (abs(a-b)>=e)if(subs(f1,x)>0)b=x;x=(a+b)/2;elseif (subs(f1,x)<0)a=x;x=(a+b)/2;elseif(subs(f1,x)==0)break;endend成功失败法:函数fun，初值x0，步长h，误差e例子：fun=x^5+2*x^4-4*x^3+x^2+x+2function [x]=suc_fail(fun,x0,h,e) x=x0;y0=subs(fun,x);while(1)y=subs(fun,(x+h))if(y<y0)y0=y;x=x+h;h=2*helseif(y>=y0)if(abs(h)<e)break;elseh=-h*(1/4);endendend0.618法：例子：fun=x^2+2*xfunction [x]=f0618(fun,a0,b0,e) n=0.618;a=a0;b=b0;r=a+(1-n)*(b-a);u=a+n*(b-a);yr=subs(fun,r);yu=subs(fun,u);while(abs(b-a)>=e)if(yr>yu)a=r;r=u;u=a+n*(b-a);yr=subs(fun,r);yu=subs(fun,u);elseb=u;u=r;r=a+(1-n)*(b-a);yu=subs(fun,u);yr=subs(fun,r);endendx=0.5*(a+b);确定初始区间和初始值：function [a,b,x0]=f(fun)t0=0;h=1;y0=subs(fun,t0);t2=t0+h;y2=subs(fun,t2);if(y2<=y0)t1=t0+h;y1=subs(fun,t1);elseh=-h;t1=t0+h;y1=subs(fun,t1);endwhile(y1<=y0)h=2*h;t2=t0;t0=t1;if(y2<=y0)t1=t0+h;y1=subs(fun,t1);elseh=-h;t1=t0+h;y1=subs(fun,t1);endenda=min(t1,t2);b=max(t1,t2);x0=(a+b)/2;海塞矩阵：[n,m]=size(x);syms x1 x2 x3 x4 x5;xk=[x1;x2;x3;x4;x5];for k=1:ny(k)=xk(k);endfor i=1:ng(i)=diff(fun,xk(i));h=g(i);for k=1:ny(i)=subs(h,xk(k),x(k));h=y(i);endendg=double(y);end海塞矩阵二阶偏导：function [g]=hassion2(fun,x)[n,m]=size(x);syms x1 x2 x3 x4 x5;xk=[x1;x2;x3;x4;x5];for k=1:ny(k)=xk(k);endfor i=1:ng1(i)=diff(fun,xk(i));for j=1:ng2(i,j)=diff(g1(i),xk(j));h=g2(i,j);for p=1:ny(i,j)=subs(h,xk(p),x(p));h=y(i,j);endendendg=double(y);一维精确搜索：[n,m]=size(x);syms x1 x2 x3 x4 x5 r;xk=[x1;x2;x3;x4;x5];xx=x+r*s;for i=1:nf=subs(fun,xk(i),xx(i));fun=f;endrr=solve(diff(f,r));r=double(rr);求函数值：function [f]=fx(fun,x0)[n,m]=size(x0);syms x1 x2 x3 x4 x5;x=[x1;x2;x3;x4;x5];for k=1:nf=subs(fun,x(k),x0(k));fun=f;endf=double(f);不精确的一维搜索方法：步长r，函数fun，初值x0，方向s0 例子：fun=100*(x2-x1^2)^2+(1-x1)^2;function [r]=ods(fun,x0,s0)[n,m]=size(x0);syms x1 x2 x3 x4 x5;x=[x1;x2;x3;x4;x5];for k=1:ny(k)=x(k);y0(k)=x(k);endc1=0.1;c2=0.5;a=0;b=+inf;r=1;j=0;s=s0;x1=x0+r*s;h0=fun;h=fun;for k=1:nf=subs(h,x(k),x1(k));h=f;f0=subs(h0,x(k),x0(k));h0=f0;endy0=hassion(fun,x0);y=hassion(fun,x1);while(double(f0-f) < double((-1)*c1*r*y0*s) || double(y*s) < double(c2*y0*s))j=j+1;if(double(f0-f) < double((-1)*c1*r*y0*s))b=r;r=(r+a)/2;elsea=r;r=min(2*r,(r+b)/2);endx1=x0+r*s;h0=fun;h=fun;for k=1:nf=subs(h,x(k),x1(k));h=f;endy=hassion(fun,x1);end最速下降法：函数fun，初值x0，误差e 例子：fun=3*x1^2+2*x2^2-4*x1-6*x2function [x]=fast(fun,x0,e)x=x0;s=hassion(fun,x);while(norm(s)>=e)x0=x;r=ods(fun,x0,-s');x=x0-r*s';s=hassion(fun,x);end牛顿法（N维）：结果x，函数fun，初值x0，精度e 例子：fun=x1^2+25*x2^2function [x]=newton2(fun,x0,e)x=x0;s1=hassion(fun,x)s2=hassion2(fun,x)while(norm(s1)>=e)x0=xx=x0-inv(s2)*s1';s1=hassion(fun,x);s2=hassion2(fun,x);end阻尼牛顿法：结果x，函数fun，初值x0，精度e例子：fun=x1^2+2*x2^2-4*x1-2*x1*x2function [x]=znnewton(fun,x0,e)x=x0;y1=hassion(fun,x0);y2=hassion2(fun,x0);while(norm(y1)>=e)s0=-inv(y2)*y1';r=search(fun,x0,s0);x0=x;x=x0+r*s0;y1=hassion(fun,x);y2=hassion2(fun,x);end共轭梯度法：结果x，函数fun，初值x0，精度e 例子：fun=x1^2+2*x2^2-4*x1-2*x1*x2function [x]=gongertidu(fun,x0,e)[n,m]=size(x0);k=0;flag=0;while(k==0 & flag==0)x=x0;g0=hassion(fun,x);s0=-g0;r=search(fun,x,s0');x=x0+r*s0';g1=hassion(fun,x);flag=flag+1;while(norm(g1)>=e)if(k==n-1)x0=x;k=0;flag=0;break;endu=norm(g1)^2/norm(g0)^2;s1=-g1+u*s0;r=search(fun,x,s1');x=x+r*s1';g1=hassion(fun,x);k=k+1;s0=s1;endendDPF算法：结果x，函数fun，初值x0，精度e例子：fun=x1^2+2*x2^2-4*x1-2*x1*x2function [x]=dfp(fun,x0,e)[n,m]=size(x0);h0=eye(n);k=0;flag=0;while(k==0 & flag==0)h=h0;x=x0;g0=hassion(fun,x);s0=-h0*g0';r=search(fun,x0,s0);x=x0+r*s0;g1=hassion(fun,x);flag=flag+1;while(norm(g1)>=e)if(k==n-1)x0=x;k=0;flag=0;break;endh=h0+((x-x0)*(x-x0)')/((x-x0)'*(g1-g0)')-(h0*(g1-g0)'*(h0*(g1-g0)')')/((g1-g0)*h0*(g1-g0)');s1=-h*g1';r=search(fun,x,s1);x=x+r*s1;g1=hassion(fun,x);h0=h;x0=x;k=k+1;endendBFGS算法：例子：fun=x1^2+x1*x2+x2^2;function [x]=wg(fun,x0,e)[n,m]=size(x0);k=0;flag=0;while(k==0 & flag==0)h0=eye(n);h=h0;x=x0;g0=hassion(fun,x0);g=g0;flag=flag+1;while(norm(g)>=e)if(k==n)k=0;flag=0;x0=x;break;ends=-h'*g';r=search(fun,x,s);x=x+r*s;g=hassion(fun,x);u=1+((g-g0)*h0*(g-g0)')/((x-x0)'*(g-g0)');h=h0+(u*(x-x0)*(x-x0)'-h0*(g-g0)'*(x-x0)'-(x-x0)*(g-g0)*h0)/((x-x0)'*(g-g0)')x0=x;g0=g;h0=h;k=k+1;endendpowell算法：例子：fun=x1^2+2*x2^2-4*x1-2*x1*x2function [x]=powell(fun,x0,e)[n,m]=size(x0);e=eye(n);flag=0;for j=1:ns(:,j)=e(:,j);endwhile(k==0 & flag==0)xx=x0;while(k<n)r=search(fun,xx,s(:,k+1));x(:,k+1)=xx+r*s(:,k+1);xx=x(:,k+1);k=k+1;endflag=flag+1;while(norm(x(:,n)-x0)>=e)d=fx(fun,x0)-fx(fun,x(:,1));for i=1:n-1f=fx(fun,x(:,i+1));f0=fx(fun,x(:,i));if((f0-f)>d)d=f0-f;endendf1=fx(fun,x0);f2=fx(fun,x(:,n));f3=fx(fun,(2*x(:,n)-x0));if((2*d) >= (f1-2*f2+f3))ss=x(:,n)-x0;for i=1:n-1s(:,i)=s(:,i+1);ends(:,n)=ss;elsex0=x(:,n);k=0;flag=0;break;endr=search(fun,x(:,n),ss);x0=x(:,n)+r*ss;k=0;flag=0;break;endx=x(:,n);惩罚函数（外点法）乘法因子：function [p]=chengfayinzi(g,h,x) syms x1 x2 x3 x4 x5;xk=[x1;x2;x3;x4;x5];s=length(x);m=length(g);n=length(h);k=n+m;p=x1-x1;for i=1:kif i<=ngj(i)=h(i).^2;elseq=g(i-n);for j=1:sy(j)=subs(q,xk(j),x(j));q=y(j);enda=double(q);if a<=0gj(i)=x1-x1;elsegj(i)=g(i-n).^2;endendp=p+gj(i);end惩罚函数：function [x]=chengfahanshu(f,g,h,x0,e) n=length(x0);syms x1 x2 x3 x4 x5;xk=[x1;x2;x3;x4;x5];M=1;c=10;p=chengfayinzi(g,h,x0);fun=f+M*p;x=dfp1(fun,x0,0.001);p=chengfayinzi(g,h,x);y=fx(M*p,x);while y>=ex0=x;M=c*M;p=chengfayinzi(g,h,x0);fun=f+M*p;x=dfp1(fun,x0,0.001);p=chengfayinzi(g,h,x);y=fx(M*p,x);end碰壁函数（内点法）：碰壁因子：function [b]=pengbiyinzi(g)syms x1[a,n]=size(g);b=x1-x1;for i=1:ngi(i)=-log(-g(i));b=b+gi(i);end碰壁函数：function [x]=pengbihanshu(f,g,n)m=length(g);syms x1 x2 x3 x4 x5 r;xk=[x1;x2;x3;x4;x5];b=pengbiyinzi(g)fun=f+r*bflag=0;b=0;for i=1:nfi(i)=diff(fun,xk(i));endif n==1[xx1]=solve(fi(1),'x1')l1=limit(xx1,r,0);for i=1:n %验证所求出来的结果中，哪个合法for j=1:mif fx(g(j),[l1(i);l2(i)])<=0b=1;elseb=0;endendif b==1breakendendx=[double(l1(i))];elseif n==2[xx1,xx2]=solve(fi(1),fi(2),'x1','x2');l1=limit(xx1,r,0);l2=limit(xx2,r,0);for i=1:nfor j=1:mif fx(g(j),[l1(i);l2(i)])<=0b=1;elseb=0;endendif b==1breakendendx=[double(l1(i));double(l2(i))];elseif n==3[xx1,xx2,xx3]=solve(fi(1),fi(2),fi(3),'x1','x2','x3') l1=limit(x1,r,0);l2=limit(x2,r,0);l3=limit(x3,r,0);for i=1:nfor j=1:mif fx(g(j),[l1(i);l2(i)])<=0b=1;elseb=0;endendif b==1breakendendx=[double(l1(i));double(l2(i));double(l3(i))]; end。

最优化方法无约束最优化方法一、无约束最优化方法中常用的方法无约束最优化方法应用广泛，理论也比较成熟；可将约束优化问题转化为无约束优化问题来处理。

1.最速下降法优点：理论明确，程序简单，每次的计算量小，所需的存储量小，对初始点要求不严格。

缺点：收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。

最速下降法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，远快近慢。

最速下降法不是好的实用算法，但是一些有效算法是通过对它的改进或利用它与其他收敛快的算法结合而得到的，因此它是无约束优化的方法之一。

2.Newton法由Newton方向的构造知,对于正定二次函数,Newon方向就是指向其极小点的方向.能快速求得最优解。

对于目标函数不是二次函数的无约束最优化问题,一般地说,用Newton法通过有限轮迭代并不能保证可求得最优解.在初始点离最优解不远的条件下,Newton法是二次收敛的.但初始点远离最优解时,此法并不一定收敛。

Newton法具有二次收敛的优点,但它存在下面四个严重的缺点:虽每次迭代不会使目标函数f(X)上升,但不能保证 f(X)下降.（1）当Hesse矩阵非正定时,Newton法的搜索将会失败.（2）对初始点要求严格.一般要求比较接近或有利于接近极值点,而这在实际计算中是比较难办的. 因搜索方向要求Hesse矩阵的逆,在某迭代时可能求不出此方向.（3）若目标函数Hesse矩阵为奇异,则不有构成牛顿方向,无法迭代.（4）牛顿方向构造困难,计算相当复杂,除了求梯度以外还需计算Hesse矩阵及其逆矩阵,占用机器内存相当大.3.拟牛顿法为了克服Newton法的缺点,人们保留选取Newton方向作为搜索方向,摒弃其步长恒取1,而用一维搜索确定最优步长,由此产生的算法称为拟Newton法.拟Newton法克服了Newton法的缺点.特别是,当迭代点接近于最优解时,此法具有收敛速度快的优点,对初始点的选择要求不严.但是,拟Newton法仍需要计算目标函数的Hesse矩阵和逆矩阵,所以求解的计算量和存贮量均很大.另外,当目标函数的Hesse矩阵在某点处出现奇异时,迭代将无法进行.因此拟Newton法仍有相当的局限性.4.共轭梯度法实际上,可以把共轭梯度法看作是最速下降法的一种改进.当令λk=0时,就变为最速下降法.共轭梯度法由于不涉及矩阵,仅仅有向量运算,因而存储量小,适合于维数较高的优化问题.另外,共轭梯度法可以不要求精确的直线搜索.但是,不精确的直线搜索可能导致迭代出来的向量不再共轭,从而降低方法的效能.克服的办法是,重设初始点,即把经过n+1次迭代得到的Xn+1作为初始点重新迭代.计算实践指出,用Xn+1比Xn用重作初始点要好.5.变尺度法Newton法最突出的优点是收敛速度快,在这一点上其它算法无法比拟的.因此,建议凡是Hesse矩阵比较容易求出的问题尽可能使用Newton法求解.Newton法也有一个严重缺陷,就是每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵,当问题的维数较大时,计算量迅速增加,从而就抵消了Newton法的优点.为此,人们开始寻找一种算法既可以保持Newton法收敛速度快的优点,又可以摆脱关于Hesse矩阵的计算,这就是变尺度算法.变尺度法是一种非常好的方法.其中DFP算法和BFGS算法,可以说直到目前为止在不用Hesse矩阵的方法中是最好的算法.二、最速下降法对于无约束最优化问题的求解,按最优化算法的基本思想是从一个给定的初始点X0出发,通过基本迭代格式Xk+1=Xk+tkPk,按照特定的算法A产生一串点列{Xk},如果此点列收敛,则其极限点为所求的最优解.1.最速下降法基本原理在基本迭代格式Xk+1=Xk+tkPk中,每次迭代搜索方向Pk取目标函数f(X)的负梯度方向,即Pk=- f (Xk) ,而每次迭代的步长tk取最优步长,由此所确定的算法A称为最速下降法.如图所示,假经过k次迭代得到第 k个迭代点 Xk.现在从Xk出发,可选择的下降方向很多,一个非常自然的想法是沿最速下降方向(即负梯度方向)进行搜索应该是有利的,至少在 Xk邻近的范围内是这样.2.步长因子的确定3.最速下降法迭代步骤4.目标函数为正定二次函数的最速下降法5.最速下降法算法三、利用最速下降法求解10。