下载文档原格式
最优化作业2Armijo准则Armijo准则（Armijo criterion）是最优化算法中一个重要的线准则，用于确定步长的大小。
它通过将目标函数在当前点处的函数值与它沿梯度方向的下降量进行比较，来判断是否接受或拒绝当前的步长。
Armijo准则的基本思想是选择一个小于1的常数幅度因子α（通常为0.1或0.5），并不断减小步长，直到目标函数值满足以下条件：f(x_k+α*d_k)<=f(x_k)+c*α*d_k^T*g_k其中，x_k是当前的位置，d_k是负梯度方向的单位向量，g_k是当前位置处的梯度，c是一个小于1的常数。
这个条件可以解释为，在当前位置沿着负梯度方向前进一段距离α之后，函数值应该下降的足够，大于等于在当前位置直接沿着梯度方向前进一段距离α*c带来的下降量。
如果当前步长满足Armijo准则，那么这个步长就被接受，更新位置为x_{k+1} = x_k + α*d_k。
否则，步长就会被减小，重新计算。
具体来说，根据Armijo准则，可以使用以下的步长算法来确定最优步长：1.设置初始步长α为12.计算f(x_k+α*d_k)。
3.如果f(x_k+α*d_k)<=f(x_k)+c*α*d_k^T*g_k，那么接受这个步长，更新位置为x_{k+1}=x_k+α*d_k。
算法结束。
4.否则，减小步长，重新计算。
一般可以将步长减小为α/2，重复步骤25. 重复步骤4，直到找到满足Armijo准则的步长。
Armijo准则的一个优点是它相对简单且易于实现。
然而，它也有一些缺点。
由于只要求函数值在当前位置沿着梯度方向前进一段距离后下降，所以可能会接受过大的步长，导致算法很难收敛。
此外，Armijo准则只考虑了一阶信息，没有考虑二阶信息，可能导致步长选择不够精确。
因此，在一些情况下，可以使用其他的步长控制准则，如Wolfe准则、Goldstein准则等，来进一步改进最优化算法的性能。
总之，Armijo准则是最优化算法中常用的线准则之一、它通过比较当前步长带来的下降量与在当前位置沿梯度方向前进一段距离带来的下降量，来决定是否接受当前步长。
第三章 牛顿法§3.1 最速下降法一、最速下降法在极小化算法中，若每次都以迭代点处的负梯度方向为搜索方向，产生的算法称为最速下降法，它是无约束最优化算法中最简单、最基本的算法。
算法描述：1） 给出初始点0n x R ∈，允许误差0ε>，0k =； 2） 计算k k d g =-，若k g ε≤，Stop 令 *k x x ≈； 3） 由一维搜索确定步长因子k α，使得()min ()k k k k k f x d f x d ααα≥+=+4） 令1k k k k x x d α+=+，1k k =+，go to 2).二、最速下降算法的收敛性定理3.1 设1f C ∈，则最速下降算法产生的点列{}k x 的每个聚点均为驻点。
证明：设x 是{}k x 的一个聚点，则存在子序列{}1k K x ，使得1lim k k K x x ∈=令()k k d f x =-∇，由1f C ∈，知{}1()k K f x ∇是收敛序列，故{}1k K d 有界，且1lim ()k k K d f x ∈=-∇由定理2.6有2()(())()0Tf x f x f x ∇-∇=-∇=故有 ()0f x ∇=。
定理 3.2 设()f x 二次连续可微，且2()f x M ∇≤，则对任何给定的初始点0n x R ∈，最速下降算法或有限终止，或lim ()k k f x →∞=-∞，或lim ()0k k f x →∞∇=。
证明：不妨设k ∀，()0k f x ∇≠。
由定理2.5有211()()()2k k k f x f x f x M+-≥∇ 于是 []120101()()()()()2kk k i i i i i f x f x f x f x f x M -+==-=-≥∇∑∑令k →∞，由{()}k f x 为单调下降序列，则要么lim ()k k f x →∞=-∞，要么 lim ()0k k f x →∞∇=。
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);。
1、Armijo 准则Armijo 准则是指给定)1,0(∈β，)5.0,0(∈σ。
令步长因子km k βα=，其中k m 为满足下列不等式的最小非负整数.)()(k Tk mk k mk d g x f d x f σββ+≤+ （1）可以证明，若f(x)是连续可微的且满足0<k T k d g 。
则Armijo 准则是有限终止的，即存在正数σ，使得对于充分大的正整数m ，式（1）成立。
为了程序实现的方便起见，将Armijo 准则写成下列详细的算法步骤：Step 1、给定)1,0(∈β，)5.0,0(∈σ，令m ：=0。
Step2、若不等式.)()(k Tk mk k mk d g x f d x f σββ+≤+成立，置k m k k k d x x m m kβ+==+:,:1，停算；否则，转Step 3。
Step 3 、令m ：=m+1，转Step2。
例题：考虑无约束优化问题.)1()(100)(min 2122212-+-=∈x x x x f Rx设当前迭代点)'1,1(-=k x ，下降方向)'2,1(-=k d ，求步长因子α。
在matlab 中编程如下： function f=fun(x)f=100*(x(1)^2-x(2))^2+(x(1)-1)^2;%梯度function gf=gfun(x)gf=[400*x(1)*(x(1)^2-x(2))+2*(x(1)-1),-200*(x(1)^2-x(2))]';function mk=armijo(xk,dk) beta=0.5;sigma=0.2; m=0;mmax=20; while (m<=mmax)if (fun(xk+beta^m*dk)<=fun(xk)+sigma*beta^m*gfun(xk)'*dk) mk=m;break ; end m=m+1; endalpha=beta^mk newxk=xk+alpha*dk fk=fun(xk)newfk=fun(newxk)最后输入：xk=[-1,1]';dk=[1,-2]';mk=armijo(xk,dk)2、最速下降法 算法实现步骤：Step1、取初始点)0(x ，容许误差（精度）0<ε，令k ：=0。
随着人工智能、模糊控制、模式识别、人工网络等新技术的应用和发展。
可以让它们与广义预测控制相结合，建立高精度、多模态的预测模型。
使广义预测控制在异常情况下可以稳定运行，推进广义预测控制的进一步发展。
2.2.1最速下降法最速下降法是无约束最优化中是比较有效的方法，它是以d}=一可(x})作为下降方向的算法。
其迭代格式为xx+i=xx一。
*Of (xk)上式中，一般通过精确线搜索准则求得步长因子。
*，当然也不排除可以利用非精确线搜索准则来求得步长因子。
*。
不管最速下降法采取何种线搜索准则，它均具有全局收敛性，但是这也不能直接就认为最速下降算法就是一个良好的优化算法。
在实际试验中，有很多优化问题利用最速下降法并不是下降的特快，反而下将的十分缓慢。
这是因为出现了锯齿现象:就是在计算过程中，最速下降法开始几步还是挺快的，但是当目标函数f (x)的等高线接近于一个球的时候，就出现了类似锯齿现象，前进十分缓慢，降低了算法的效能。
2.2.12.2.2牛顿法牛顿法也是无约束最优化问题中的一种经典算法，它是利用目标函数.f (x)的二次泰勒展开式，并将二次泰勒展开式进行极小化。
其迭代格式为x}+}=xA十d}(2-5)其中步长因子。
、=l} d、为02f (x} )d + Of (xA ) = 0的解。
当目标函数f(x)是正定二次函数的时候，牛顿法可以一步达到最优解;当目标函数f (x)是非二次函数的时候，牛顿法经过有限次迭代之后就不能确保求得目标函数f (x)的最优解。
我们知道目标函数f (x)在极小点附近是很接近于二次函数的，所以，假如初始点非常靠近无约束最优化问题((1-1)的最优解x的时候，并且}Z.f (x.)正定的时候，那么牛顿法就会有很快的收敛速度，而由此算法产生的点列也具有了超线性收敛速度，同时还在一定条件下具有二次收敛性;假如初始点与无约束最优化问题(1-1)的最优解x’相距比较远的时候，这时的}Z.}(x})就不一定是正定的了，也就存在了一个问题，那就是此时的牛顿方向就不一定是下降方向，有可能是上升方向，此时由此算法产生的点列可能也就不收敛于无约束最优化问题((1-1)的最优解了。
最速下降法Matlab实现实验目的：1.掌握迭代法求解无约束最优化问题的基本思想2.通过实验掌握最速下降法的Matlab算法的基本步骤实验内容：1.迭代法求解无约束最优化问题的基本思想给定一个初始点x(0), 按照某一迭代规则产生一个迭代序列{x(k)}. 使得若该序列是有限的, 则最后一个点就是原问题的极小点; 否则, 若序列{x(k)} 是无穷点列时, 它有极限点且这个极限点即为原问题的极小点.设x(k) 为第k 次迭代点, d(k) 为第k 次搜索方向, a(k)为第k 次步长因子, 则第k 次迭代完成后可得到新一轮(第k + 1 次) 的迭代点x(k+1) = x(k) + a(k) d(k).2.无约束优化问题迭代算法的一般框架步0 给定初始化参数及初始迭代点x(0). 置k := 0.步1 若x(k) 满足某种终止准则, 停止迭代, 以x(k) 作为近似极小点.步2 通过求解x(k) 处的某个子问题确定下降方向d(k).步3 通过某种搜索方式确定步长因子a(k), 使得f(x(k) + a(k) d(k)) < f(x(k)).步4 令x(k+1) := x(k) + a(k) d(k), k := k + 1, 转步1.3. 最速下降法的基本步骤步0 选取初始点x(0) ∈R^n, 容许误差0 ≤e ≪1. 令k := 1.步1 计算g(k) = ∇f(x(k)). 若‖g(k)‖≤e, 停算, 输出x(k)作为近似最优解.步2 取方向d(k)= −g(k).步3 由线搜索技术确定步长因子a(k),即min f(a(k))=f(x(k)+a(k)d(k)).步4 令x(k+1) := x(k) + a(k)d(k)), k := k + 1, 转步1.4. 编写最速下降法Matlab 程序5. 利用程序求解无约束最优化问题f(x，y)=x^2+2y^2的最优值.。
机器学习算法系列最速下降法牛顿法拟牛顿法最速下降法（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是一个对黑塞矩阵逆的估计。
最优化Armijo算法确定步长的最速下降法资料最速下降法是最优化算法中最简单、最基础的一种方法，但其收敛速度较慢且容易陷入局部最优解。
因此，在最速下降法的基础上，可以通过引入步长的方法来提高算法的收敛速度。
而Armijo算法就是一种常见的用于确定步长的方法。
最速下降法基础假设我们要最小化目标函数f(x)，那么最速下降法的思路就是从一个初始点x0开始，不断朝着负梯度方向进行迭代，直到找到最优解x∗，即：$x_{k+1} = x_k - \\alpha_k \ abla f(x_k)$其中，ablaf(x k)是f(x)在x k处的梯度，$\\alpha_k$ 是步长（也称为学习率），表示每次迭代的步长大小。
但这里还有一个问题：如何确定每次迭代的步长呢？Armijo算法Armijo算法是一种基于梯度下降法的步长确定方法。
它的思路是，每次迭代的步长不应该过大，否则容易导致超出收敛区域。
同时，步长也不应该过小，否则收敛速度会变得非常缓慢。
因此，步长的大小应该恰到好处，即在一定范围内找到一个最优的步长大小。
具体地，Armijo算法通过二分搜索的方法，在可行步长范围内找到一个最优的步长 $\\alpha_k$。
具体过程如下：1.首先初始化 $\\alpha_0$，并设定一些参数，如尝试步长大小t、可行步长下界 $\\tau$ 和函数下降的最小比例 $\\gamma$。
2.计算目标函数f(x k−t ablaf(x k))，以及根据一定准则确定下一个$\\alpha$。
3.如果 $f(x_k - \\alpha_k\ abla f(x_k))$ 函数值比f(x k)减小了一些比例$\\gamma$，则认为当前 $\\alpha_k$ 是可行的步长。
4.如果当前 $\\alpha_k$ 不是可行的步长，则将其折半，即 $\\alpha_k\\leftarrow \\alpha_k/2$，直到找到一个可行的步长为止。
最速下降法步长公式最速下降法是一种优化算法，在数学和计算机科学等领域有着广泛的应用。
而其中的步长公式则是决定算法效率和准确性的关键因素之一。
先来说说什么是最速下降法。
想象一下你在一个山坡上，想要尽快到达山底，但是周围雾气弥漫，你看不到太远的地方，只能感受到当前位置的坡度。
最速下降法就是根据这个局部的坡度信息，一步一步地往山下走。
而步长呢，就相当于你每一步迈出去的大小。
在数学表达式中，最速下降法的迭代公式是这样的：$x_{k + 1} = x_k - \alpha_k \nabla f(x_k)$，这里的$\alpha_k$就是步长。
步长要是选得太大，可能一步就迈过了最低点，然后又得往回走；步长要是选得太小，那下山的速度就会特别慢，浪费好多时间和精力。
给大家举个我曾经在教学中的例子吧。
有一次，我给学生们布置了一个用最速下降法求解函数最小值的作业。
有个学生特别积极，上来就选了一个特别大的步长，结果呢，函数值不但没下降，反而跳来跳去，就像一只没头的苍蝇到处乱撞。
我就问他：“你这步子迈这么大，不怕一脚踩空吗？”他挠挠头，不好意思地笑了。
后来，经过仔细的分析和调整，他终于找到了合适的步长，顺利地求出了最小值。
再来说说步长公式的常见形式。
一种常见的步长公式是通过线搜索来确定的，也就是沿着下降方向不断尝试不同的步长，直到找到使得函数值下降最多的那个步长。
这就有点像你在黑暗中摸索着找路，不断试探着往前迈一小步，看看是不是走对了方向。
还有一种比较简单的方法是固定步长法，就是事先给定一个固定的步长值。
但这种方法往往效果不太好，因为很难提前知道一个适用于所有情况的固定步长。
在实际应用中，选择合适的步长公式可不是一件容易的事儿。
这得考虑到函数的性质、计算的效率，还有精度的要求等好多因素。
比如说，如果函数的曲率变化比较大，那可能就需要更灵活的步长选择策略；如果对计算速度要求很高，可能就得在精度上做一些妥协，选择相对简单但快速的步长公式。
armijo-goldstein准则计算步长
Armijo-Goldstein准则是一种确定梯度下降法中的步长的准则，也称为强凹性准则。
步长是在每次迭代中更新自变量的量，影响下一步的方向和距离。
根据Armijo-Goldstein准则，步长应该满足以下条件：
1. 初始步长为一个正数，通常取1。
2. 计算在当前步长下的函数值，记为f(x)。
3. 计算在当前步长下，根据梯度方向进行一步更新后的函数值，记为f(x + αd)。
其中，α为步长，d为梯度方向。
4. 如果f(x + αd) <= f(x) + cαg^T\cdot d，其中c为一个取值在(0,1)之间的常数，g为梯度，则步长满足条件，可以保留。
5. 如果f(x + αd) > f(x) + cαg^T\cdot d，步长不满足条件，则将
步长缩小一定比例（如折半），重新计算。
具体来说，计算步长的算法如下：
1. 初始化步长为一个正数，通常取1。
2. 计算在当前步长下的函数值，记为f(x)。
3. 计算在当前步长下，根据梯度方向进行一步更新后的函数值，记为f(x + αd)。
4. 判断是否满足Armijo-Goldstein准则。
如果满足，返回当前
步长；否则，将步长缩小一定比例（如折半），重新进行第3
步和第4步的计算，直到满足准则或达到一定的迭代次数为止。
注意，步长的选择对梯度下降法的收敛速度和性能有重要影响，
过小的步长可能导致收敛速度过慢，而过大的步长可能导致无法收敛或振荡。
因此，适当选择步长是梯度下降法中的重要问题之一。
最优化算法最速下降法、⽜顿法、拟⽜顿法Python实现---------------------------------------2020.9.23更新---------------------------------把 BFGS(x)改写了⼀下，变简洁了def BFGS(x): #拟⽜顿法epsilon, h, maxiter = 10**-5, 10**-5, 10**4Bk = np.eye(x.size)for iter1 in range(maxiter):grad = num_grad(x, h)if np.linalg.norm(grad) < epsilon:return xdk = -np.dot((np.linalg.inv(Bk)), grad)ak = linesearch(x, dk)x = x + dk*akyk = num_grad(x, h) -gradsk = ak*dkif np.dot(yk, sk) > 0:Bs = np.dot(Bk,sk)ys = np.dot(yk,sk)sBs = np.dot(np.dot(sk,Bk),sk)Bk = Bk - 1.0*Bs.reshape((n,1))*Bs/sBs + 1.0*yk.reshape((n,1))*yk/ysreturn x---------------------------------------2020.9.23更新---------------------------------只⽤到了numpy这⼀个库，只要安装有这个库应该都可以直接运⾏import numpy as npdef f(x): #⽬标函数x1 = x[0]x2 = x[1]y = 100*((x2 - x1**2)**2) + (x1-1)**2return ydef num_grad(x, h): #求梯度df = np.zeros(x.size)for i in range(x.size):x1, x2 = x.copy(), x.copy() #这⾥需要⽤到复制，⽽不能⽤赋值号（=），原因是Python⾥⾯=号只是取别名，不是复制（c/c++⾥⾯是）x1[i] = x[i] - hx2[i] = x[i] + hy1, y2 = f(x1), f(x2)df[i] = (y2-y1)/(2*h)return dfdef num_hess(x, h): #求hess矩阵hess = np.zeros((x.size, x.size))for i in range(x.size):x1 = x.copy()x1[i] = x[i] - hdf1 = num_grad(x1, h)x2 = x.copy()x2[i] = x[i] + hdf2 = num_grad(x2, h)d2f = (df2 - df1) / (2 * h)hess[i] = d2freturn hessdef linesearch(x, dk): #求步长ak = 1for i in range(20):newf, oldf = f(x + ak * dk), f(x)if newf < oldf:return akelse:ak = ak / 4 #迭代更新步长，步长可随意变换，保证newf⽐oldf⼩就可以了（如改为: ak=ak/2 也是可以的）return akdef steepest(x): #最速下降法epsilon, h, maxiter = 10**-5, 10**-5, 10**4for iter1 in range(maxiter):grad = num_grad(x, h)if np.linalg.norm(grad) < epsilon:return xdk = -gradak = linesearch(x, dk)x = x + ak * dkreturn xdef newTonFuction(x): #⽜顿法epsilon, h1, h2, maxiter = 10**-5, 10**-5, 10**-5, 10**4for iter1 in range(maxiter):grad = num_grad(x, h1)if np.linalg.norm(grad) < epsilon:return xhess = num_hess(x, h2)dk = -np.dot((np.linalg.inv(hess)), grad)x = x + dkreturn xdef BFGS(x): #拟⽜顿法epsilon, h, maxiter = 10**-5, 10**-5, 10**4Bk = np.eye(x.size)for iter1 in range(maxiter):grad = num_grad(x, h)if np.linalg.norm(grad) < epsilon:return xdk = -np.dot((np.linalg.inv(Bk)), grad)ak = linesearch(x, dk)x = x + dk*akyk = num_grad(x, h) -gradsk = ak*dkif np.dot(yk.reshape(1, grad.shape[0]), sk) > 0:'''第⼀种分步计算实现t0 = np.dot(Bk, sk)t1 = np.dot(t0.reshape(sk.shape[0], 1), sk.reshape(1, sk.shape[0]))temp0 = np.dot(t1, Bk)temp1 = np.dot(np.dot(sk.reshape(1, sk.shape[0]), Bk), sk)tmp0 = np.dot(yk.reshape(yk.shape[0], 1), yk.reshape(1, yk.shape[0]))tmp1 = np.dot(yk.reshape(1, yk.shape[0]), sk)Bk = Bk - temp0 / temp1 + tmp0 / tmp1'''#第⼆种直接写公式实现Bk = Bk - np.dot(np.dot(np.dot(Bk, sk).reshape(sk.shape[0], 1), sk.reshape(1, sk.shape[0])), Bk)/np.dot(np.dot(sk.reshape(1, sk.shape[0]), Bk), sk) + np.dot(yk.reshape(yk.shape[0], 1), yk.reshape(1, yk.shape[0])) / np.dot(yk.reshape(1, yreturn x#x0 = np.array([0.999960983973235, 0.999921911551354]) #初始解x0 = np.array([0.7, 0.9]) #初始解x = steepest(x0) #调⽤最速下降法print("最速下降法最后的解向量：",x)print("最速下降法最后的解：",f(x))print('')x = newTonFuction(x0) #调⽤⽜顿法print("⽜顿法最后的解向量：", x)print("⽜顿法最后的解：", f(x))print('')x = BFGS(x0) #调⽤拟⽜顿法print("拟⽜顿法最后的解向量：", x)print("拟⽜顿法最后的解：", f(x))print('')结果如下拟⽜顿法感觉弄⿇烦了，暂时也没想法改，先就这样吧。
数学与计算科学学院实验报告实验项目名称使用非精确线搜索Armijo算法确定步长的最速下降法所属课程名称最优化方法实验类型算法编程实验日期班级学号姓名成绩)](-)([11-)(-)( )2.3(||-||21)-()-(21)(-)( 0)( )(,*2*12**T *****x f x f x f x f x x x x Q x x x f x f q Qx x f x q Qx x f k k Q ⎪⎭⎫ ⎝⎛+≤===+=∇+=∇+κκ可以改写成所以则处且在由于对于二次函数.,( .,1 , ,1,,,)2.3(算法收敛很慢接近病态）较大时而当求出最优解算法只需一次迭代即可的所有特征值相等时即当特别最速下降收敛很快接近于当有关的条件数矩阵最速下降的收敛速度与看到由收敛速度估计式Q Q Q κκκκ=结论：最速下降法的收敛速度比较慢，通常将其用在某些算法的初始阶段求较好的初始点或作为某些算法的间插步.【实验环境】Win 7； Matlab7.0二、实验内容： 【实验方案】1、求梯度；2、向梯度相反的方向移动x ，其中 为步长。
如果步长足够小，则可以保证每一次迭代都在减小，但可能导致收敛太慢，如果步长太大，则不能保证每一次迭代都减少，也不能保证收敛。
3、循环迭代步骤2，直到x 的值变化到使得在两次迭代之间的差值足够小，比如0.00000001，也就是说，直到两次迭代计算出来的基本没有变化，则说明此时已经达到局部最小值了。
4、此时，输出x ，这个x 就是使得函数最小时的x 的取值 。
【实验过程】梯度下降法的计算过程就是沿梯度下降的方向求解极小值（也可以沿梯度上升方向求解极大值）。
其迭代公式为,其中代表梯度负方向，表示梯度方向上的搜索步长。
梯度方向我们可以通过对函数求导得到，步长的确定比较麻烦，太大了的话可能会发散，太小收敛速度又太慢。
一般确定步长的方法是由线性搜索算法来确定，即把下一个点的坐标ak+1看做是的函数，然后求满足f(ak+1)的最小值的 即可。
数学与计算科学学院
实验报告
实验项目名称使用非精确线搜索Armijo算法确定步长的最速下降法
所属课程名称最优化方法
实验类型算法编程
实验日期
班级
学号
姓名
成绩
，其中为步长。
如果步长足够小，则可以保证每一次迭代都在减
的值变化到使得在两次迭代之间的差值足够小，比如直到两次迭代计算出来的基本没有变化，则说明此时已经达
就是使得函数最小时的
其迭代公式为,其中代表梯度负方向，表示梯度方向上的搜索步
其最小值在处，函数值为。
但是此函数具有狭窄弯曲的山谷，最小
附录1：源程序
附录2：实验报告填写说明
1．实验项目名称：要求与实验教学大纲一致。
2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。
3．实验原理：简要说明本实验项目所涉及的理论知识。
4．实验环境：实验用的软、硬件环境。
5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。
概括整个实验过程。
对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。
对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设
计思路和设计方法，再配以相应的文字说明。
对于创新性实验，还应注明其创新点、特色。
6．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。
7．实验结论（结果）：根据实验过程中得到的结果，做出结论。
8．实验小结：本次实验心得体会、思考和建议。
9．指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。
