最优化Armijo算法确定步长的最速下降法

格式：doc
大小：504.50 KB
文档页数：9

下载文档原格式

/ 9

armijo搜索准则

armijo搜索准则
Armijo搜索准则是一种经常用于计算机科学中的最优化算法。

它是由斯宾塞阿米霍（SpencerArmijo）于1960年提出的，目的是有助于解决最优化问题。

它的特点是可以衡量每一步的步长，从而有效地控制结果的变化，让搜索过程更快找到全局最优点。

Armijo搜索准则以一个固定的常量值作为步长，将搜索空间从大面积进行缩小，而不是直接从搜索点开始。

这样可以有效地避免因为步长太大而导致的搜索空间过大的问题。

搜索的目标是在每一步的搜索空间内，找到最优点。

在应用Armijo搜索准则时，一般会设定一个很小的步长，以保证搜索空间的大小，以免出现搜索越界的情况。

为了获得更好的结果，还需要对搜索空间作出更精确的设定，以控制搜索范围，减少容易陷入局部最优点的情况。

此外，Armijo搜索准则还有一个很重要的特点，就是可以有效地指导迭代过程，也可以辅助进行一些限制条件的搜索，从而更轻松实现搜索的平衡。

比如，在求解路径问题时，既需要考虑最终的路径长短，又要保持路径的可行性，这时Armijo搜索准则可以有效地辅助实现路径平衡。

此外，Armijo搜索准则也可以用于其它优化问题，例如求解最小二乘问题、全局最优点的搜索等等。

它的优势在于可以减少搜索的空间，从而加快搜索过程，也能够有效控制搜索的精度，使获取的结果更加准确可靠。

因此，Armijo搜索准则在计算机科学中的最优化算法中有着重要的作用。

它不仅能够加快搜索速度，还能够有效控制搜索结果的精确程度，让你从其它繁琐的算法中脱颖而出，实现更好的结果。

梯度方法

长取常值αk ≡ α,且
2 α ∈ (0, M ),
在算法1中ϵ = 0. 则由算法1生成的点列{xk}满足
∥xk+1 − x∗∥ ≤ qk∥x1 − x∗∥,
其中x∗是f 的唯一极小点,
{
}
q = max |1 − αm|, |1 − αM | < 1.
最速下降方法
最优化方法 16
证明
由∇f (xk) = ∇f (xk) − ∇f (x∗) = Gk(xk − x∗)其中 ∫1
f (xk+1) ≤ f (xk) − 1 ∥∇f (xk)∥2. 2M
最速下降方法
最优化方法 23
应用引理1,由此不等式可得 f (xk+1) − f (x∗) ≤ [f (xk) − f (x∗)] − m (1 + m )[f (xk) − f (x∗)]
2M M ≤ ρ[f (xk) − f (x∗)].
k→∞
最速下降方法
最优化方法 11
证明
对第k步,用中值定理得存在θ ∈ [0, 1], f (xk+1) = f (xk + αdk) = f (xk) + α⟨∇f (x¯), dk⟩,
其中x¯ = xk + θαdk. 于是
f (xk+1) = f (xk) + α⟨∇f (xk), dk⟩ + α⟨∇f (x¯) − ∇f (xk), dk⟩ ≤ f (xk) + α⟨∇f (xk), dk⟩ + α∥∇f (x¯) − ∇f (xk)∥∥dk∥ ≤ f (xk) − α∥∇f (xk)∥2 + αM ∥xk − x¯∥∥∇f (xk)∥ ≤ f (xk) − α∥∇f (xk)∥2 + M α2∥∇f (xk)∥2 = f (xk) − α(1 − M α)∥∇f (xk)∥2. (1)

梯度下降优化算法

梯度下降优化算法综述,梯度下降法梯度下降法是什么？梯度下降法（英语：Gradientdescent）是一个一阶最优化算法，通常也称为最陡下降法。

要使用梯度下降法找到一个函数的局部极小值，必须向函数上当前点对应梯度（或者是近似梯度）的反方向的规定步长距离点进行迭代搜索。

如果相反地向梯度正方向迭代进行搜索，则会接近函数的局部极大值点；这个过程则被称为梯度上升法。

梯度下降一般归功于柯西，他在1847年首次提出它。

Hadamard在1907年独立提出了类似的方法。

HaskellCurry在1944年首先研究了它对非线性优化问题的收敛性，随着该方法在接下来的几十年中得到越来越多的研究和使用，通常也称为最速下降。

梯度下降适用于任意维数的空间，甚至是无限维的空间。

在后一种情况下，搜索空间通常是一个函数空间，并且计算要最小化的函数的Fréchet导数以确定下降方向。

梯度下降适用于任意数量的维度（至少是有限数量）可以看作是柯西-施瓦茨不等式的结果。

那篇文章证明了任意维度的两个向量的内（点）积的大小在它们共线时最大化。

在梯度下降的情况下，当自变量调整的向量与偏导数的梯度向量成正比时。

修改为了打破梯度下降的锯齿形模式，动量或重球方法使用动量项，类似于重球在被最小化的函数值的表面上滑动，或牛顿动力学中的质量运动在保守力场中通过粘性介质。

具有动量的梯度下降记住每次迭代时的解更新，并将下一次更新确定为梯度和前一次更新的线性组合。

对于无约束二次极小化，重球法的理论收敛速度界与最优共轭梯度法的理论收敛速度界渐近相同。

该技术用于随机梯度下降，并作为用于训练人工神经网络的反向传播算法的扩展。

梯度下降算法是指什么神经网络梯度下降法是什么?梯度下降法是一个最优化算法，通常也称为最速下降法。

最速下降法是求解无约束优化问题最简单和最古老的方法之一，虽然现已不具有实用性，但是许多有效算法都是以它为基础进行改进和修正而得到的。

最速下降法是用负梯度方向为搜索方向的，最速下降法越接近目标值，步长越小，前进越慢。

最速下降法解二次矩阵方程

面，ＪＨｉｈｍ和Ｈ．ＫｍｌＮ．．ｇａＭ．ｉ６根据式（）的广义１特征对满足Ｈｏｒ件，出解的表达式．［］ａ条给文５给
０中，给出了新的算法和它的全局收敛性定理．并
１Ｎｗｏ法解二次方程ｅｔｎ算
磊
３０１）５０４
４０８；．１０２２福建工程学院数理系，福建福州
摘
要：分析了牛顿法解二次方程的优点和缺点．结合优化理论中最速下降法思想，给
ቤተ መጻሕፍቲ ባይዱ
出一种新的算法解二次矩阵方程，列出几个数值例子说明算法是可行的．并关键词：最速下降；ｗｔｎ算法；阵方程；Ｎｅｏ矩全局收敛中图分类号：０４０１０２；０５文献标识码：Ａ
ｓｅｐｓｓｅｅｈｏｓａｌｄｉｐｉｚｔｎｔｏｖｈｕｄｒｔｃｍａｒｘｅｕｔｎ，ａｄａｎｗｌｏｉｈｍｔｅｅｔｄｅｃｎｔｍｔｄｗａｐｐｉｎｏｔｍｉａｉｏｓｌｅｔｅｑａａｉｔｉｑａｉｅｏｏｎｅａｇｒｔｗａｖｎ．Ｓｅｅａｕｅｉａｘｍｐｅｒｒｓｎｔｄｔｌｓｒｔｈｅｓｂｌｙｏｕｒａｇｒｔｍ．ｓｇｉｅｖｒｌｎｍｒｃｌｅａｌｓｗｅｅｐｅｅｅｏｉｕｔａｅｔｅｆａｉｉｔｆｏｌｏｉｈｌｉＫｅｒｓ：ｔｅｅｔｄｓｅｔｙｗｏｄｓｅｐｓｅｃｎ；Ｎｅｏｌｏｉｈｍ；ｍａｒｘｅｕｔｏｗｔｎａｇｒｔｔｉｑａｉｎ；ｇｏｂｌｃｎｅｇｅｅｌａｏｖｒｎｃ

最优化方法-迭代下降算法概述

四.算法的收敛性
X k1 X k X k X
(1) 1 ，算法具有线性收敛速度
(2) 1 2 ，算法具有超线性收敛速度
(3) 2 ，算法具有二阶收敛速度
四.算法的收敛性
定义 3.16（有限收敛性或二次收敛性）：若将某种算法应用与任意一个具有正定Hesse矩阵的
二.最优步长的性质
设无约束极小化问题为：min f(X),X E n
二、最优步长的性质
2.几何意义：
f ( X k P)PT 0 X K 1 X k P
二.最优步长的性质
由于 k 是最优步长，故是 X k1 f ( X )在过点 X k1
而与搜索方向 Pk 平行的直线L上的极小点。因
算法产生的点列通常只是其极限属于某个指定的解集，须规定一些准则，使得计算经过有限次迭代后在满足过给的准则的条件下终止。
三.计算过程的终止
终止准则
（1）梯度准则：目标函数在迭代点的梯度的模达到充分小，即 f (Xk ) （2）点距准则：两个迭代之间的距离充分
小,即
X km X k 2 或比值
迭代下降算法概述
本节主要内容
一.算法的基本格式二.最优步长的性质三.计算过程的终止四.算法的收敛
本章的目的和要求
掌握算法的基本格式熟悉最优步长的性质知道计算过程的终止准则了解算法的收敛性
一.算法的基本格式
定义 1 基本格式 2
一.算法的基本格式
1.定义（下降迭代算法）：从某个初始点出发，根据一定的算法规则，产生一个是目标函数值有所下降的新的点；再从这个新的点出发，重复上述过程，这样可以得到一个点列，在一定的条件下，这个点列将趋于极小点或我们所期1)线性收敛速度

armijo准则

armijo准则Armijo准则是一种简单但十分有效的数值计算中优化方法，被广泛用于最优化算法的收敛检验。

它最初被用于寻找函数极小值点，但现在也被用于实践中的优化问题，如计算机视觉和机器学习应用。

本文将重点介绍Armijo准则的基本原理、收敛检验的执行过程以及它的实际应用。

一、Armijo准则的基本原理Armijo准则的基本原理是：在给定一个正则因子γ > 0，一个步长η > 0，要寻找函数极小值点x*，以及一个函数f，当函数f的值在x*满足Armijo准则时，x*才被认为是函数f的极小值点。

假定现在有一维函数f，它可以在任意点上分别定义为f(x)和f(x)，Armijo准则被定义为：f(x)=f(x-η)+γ f(x-η)≤0如果此条件成立，则说明函数f在点x处贴近函数f的极小值点，这时候就可以认为函数f的极小值点已经找到了。

二、Armijo准则的收敛检验执行过程在实际应用中，Armijo准则通常采用收敛检验的方式来进行优化。

收敛检验的执行过程是，首先选取一个初始点x0，然后不断更新x，每次更新即根据Armijo准则构造一个函数f，找到函数f的极小值点x*，即为下一次迭代需要更新的点。

不断迭代，直到函数f的极小值点就是最终收敛点x*。

三、Armijo准则在实践中的应用Armijo准则在实践中有着广泛的应用。

它可以用于计算机视觉中的图像优化，如目标跟踪、图像拼接等；在机器学习领域，可以用于梯度下降法、拟牛顿法、模拟退火法等优化算法；同时，Armijo 准则还可以用于优化问题求解，如线性规划、二次规划等数值计算问题。

Armijo准则在优化中有着十分重要的作用，它不仅是优化算法的一个重要组成部分，而且可以被广泛地应用于计算机视觉以及机器学习领域的实践中，有助于提高这些领域的精准度和准确度。

不同范数下的最速下降法

不同范数下的最速下降法标题:不同范数下的最速下降法简介:本文将探讨不同范数下的最速下降法，分析其在优化问题中的应用和特点，同时避免涉及任何违反阅读体验的元素。

正文:最速下降法是一种常用的数值优化算法，用于求解无约束优化问题。

它的基本思想是在每一步迭代中，选择使目标函数下降最快的方向，并沿该方向迭代更新。

在这个过程中，范数的选择对算法的性能有重要影响。

本文将讨论不同范数下最速下降法的应用和特点。

首先，我们需要明确范数的概念。

范数是定义在向量空间上的一种度量，它衡量了向量长度的大小。

常见的范数有1范数、2范数和无穷范数。

1范数是指向量元素的绝对值之和，2范数是指向量元素绝对值的平方和的开方，无穷范数是指向量元素绝对值的最大值。

在最速下降法中，选择不同的范数会导致不同的迭代方向和步长，从而影响算法的收敛性和效率。

以最小化目标函数f(x)为例，我们可以定义不同范数下的梯度g(x)为：1范数下的梯度：g(x)=sign(x)2范数下的梯度：g(x)=2x无穷范数下的梯度：g(x)=sign(x)*max(abs(x))根据梯度的定义，我们可以根据不同范数选择相应的下降方向。

例如，在1范数下，我们选择目标函数在当前点的梯度的方向作为下降方向；在2范数下，我们选择目标函数在当前点梯度方向的两倍作为下降方向；在无穷范数下，我们选择目标函数在当前点梯度方向的符号与最大绝对值的元素相同的向量作为下降方向。

虽然不同范数下的最速下降法具有不同的性质，但它们都遵循相同的更新规则，即：x_{k+1}=x_k-α*g(x_k)其中，α是步长参数，用于控制每一步迭代的更新幅度。

步长的选择对算法的收敛性和效率有重要影响。

过大的步长可能导致迭代不稳定，而过小的步长则会增加算法的迭代次数。

为了获得较好的性能，通常需要根据具体问题调整步长。

需要注意的是，在应用最速下降法时，我们应该根据问题的特点选择合适的范数。

例如，在稀疏优化问题中，选择1范数可以促使稀疏解；而在平滑优化问题中，选择2范数可以得到较为平滑的解。

最优化理论

一维搜索:1精确一维搜索精确一维搜索可以分为三类：区间收缩法、函数逼近法（插值法）、以及求根法。

区间收缩法：用某种分割技术缩小最优解所在的区间(称为搜索区间)。

包括：黄金分割法、成功失败法、斐波那契法、对分搜索法以及三点等间隔搜索法等。

优化算法通常具有局部性质，通常的迭代需要在单峰区间进行操作以保证算法收敛。

确定初始区间的方法：进退法①已知搜索起点和初始步长；②然后从起点开始以初始步长向前试探，如果函数值变大，则改变步长方向；③如果函数值下降，则维持原来的试探方向，并将步长加倍。

1.1黄金分割法：黄金分割法是一种区间收缩方法(或分割方法)，其基本思想是通过取试探点和进行函数值比较，使包含极小点的搜索区间不断缩短以逼近极小值点。

具有对称性以及保持缩减比原则。

优点：不要求函数可微，除过第一次外，每次迭代只需计算一个函数值，计算量小，程序简单；缺点：收敛速度慢；函数逼近法（插值法）：用比较简单函数的极小值点近似代替原函数的极小值点。

从几何上看是用比较简单的曲线近似代替原的曲线，用简单曲线的极小值点代替原曲线的极小点。

1.2牛顿法：将目标函数二阶泰勒展开，略去高阶项后近似的替代目标函数，然后用二次函数的极小点作为目标函数的近似极小点。

牛顿法的优点是收敛速度快，缺点是需要计算二阶导数，要求初始点选的好，否则可能不收敛。

1.2抛物线法：抛物线法的基本思想就是用二次函数抛物线来近似的代替目标函数，并以它的极小点作为目标函数的近似极小点。

在一定条件下，抛物线法是超线性收敛的。

1.3三次插值法：三次插值法是用两点处的函数值和导数值来构造差值多项式，以该曲线的极小点来逼近目标函数的极小点。

一般来说，三次插值法比抛物线法的收敛速度要快。

精确一维搜索的方法选择：1如目标函数能求二阶导数：用Newton法，收敛快。

2如目标函数能求一阶导数：1如果导数容易求出，考虑用三次插值法，收敛较快；2对分法、收敛速度慢，但可靠；3只需计算函数值的方法：1二次插值法, 收敛快，但对函数单峰依赖较强；2黄金分割法收敛速度较慢，但实用性强，可靠；4减少总体计算时间：非精确一维搜索方法更加有效。

最优化方法-Armijo非精确搜索

最优化方法-A r m i j o非精确搜索(总7页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--数学与计算科学学院实验报告实验项目名称 Armijo非精确搜索+DFP所属课程名称最优化方法实验类型算法编程实验日期班级学号姓名成绩算法的计算步骤如下：n ，允许误差（单位矩阵），计算出在出发，沿方向k d 搜索，求步长)k k d λ+ ；clc;clear;Function mk=armijo(fun,xk,rho,sigma,gk)assert(rho>0&&rho<1);assert(sigma>0&&sigma<;mk=0;max_mk=100;while mk<=max_mkx=xk-rho^mk*gk;if feval(fun,x)<=feval(fun,xk)-sigma*rho^mk*norm(gk)^2break;endmk=mk+1;endreturn;2.编写出使用拟牛顿法中的DFP算法来求解的Matlab程序（详细程序见附录源程序）。

3.运行程序，得出结果如图所示：从上述运行结果可以得出：最优解为x=,最小值约为f=0。

【实验结论】（结果）拟牛顿法是无约束最优化方法中的最有效的一类算法。

使用拟牛顿法中的DFP算法，不需要计算Hesse矩阵。

当k 0H 时，算法产生的方向均为下降方向，具有二次终止性，且对于数据的存储量相对较大。

【实验小结】（收获体会）通过这个实验，我对于拟牛顿法的了解更深更加透彻，我们学习的算法使用附录1：源程序附录2：实验报告填写说明1．实验项目名称：要求与实验教学大纲一致。

2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。

3．实验原理：简要说明本实验项目所涉及的理论知识。

4．实验环境：实验用的软、硬件环境。

5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。

求全局最优化的几种确定性算法

求全局最优化的几种确定性算法全局最优化是一个在给定约束条件下寻找函数全局最小或最大值的问题。

确定性算法是指每次运行算法都能得到相同的结果，且结果能确保接近全局最优解。

以下是几种常见的确定性算法：1. 梯度下降法（Gradient Descent）梯度下降法是一种迭代优化算法，通过沿负梯度方向逐步调整参数值，直至找到函数的最小值或最大值。

该算法对于凸函数是有效的，但可能会陷入局部最优解。

可以通过调整学习率和选择不同的初始参数值来改进算法的效果。

2. 牛顿法（Newton's Method）牛顿法利用函数的二阶导数信息来找到函数的最小值或最大值。

它基于泰勒级数展开，通过使用当前点的一阶和二阶导数来逼近函数，然后迭代地更新参数值。

牛顿法通常比梯度下降法更快地收敛到全局最优解，但它可能需要计算和存储较大的二阶导数矩阵。

3. 共轭梯度法（Conjugate Gradient）共轭梯度法是一种迭代法，用于求解线性方程组或优化问题。

它利用问题的海森矩阵或其逼近的特殊性质，在有限次迭代后得到准确解。

共轭梯度法在解决大规模问题时具有可伸缩性，且不需要存储大规模矩阵。

4. BFGS算法（Broyden–Fletcher–Goldfarb–Shanno Algorithm）BFGS算法是一种拟牛顿法，用于解决无约束非线性优化问题。

它通过近似目标函数的海森矩阵的逆矩阵来逼近最优解，从而避免了计算海森矩阵的复杂性。

BFGS算法具有快速的收敛性和较好的全局收敛性。

5. 遗传算法（Genetic Algorithms）遗传算法是一种模拟生物进化过程的优化方法，通过模拟自然界的选择、交叉和变异过程来最优解。

它将问题表示成一个个基因型，通过使用选择、交叉和变异等操作来产生新的个体，并根据适应度函数评估每个个体的好坏。

遗传算法具有全局能力，可以处理非线性、非凸函数以及离散优化问题。

6. 粒子群优化算法（Particle Swarm Optimization）粒子群优化算法是一种模拟鸟群或鱼群行为的优化算法。

本章要点最速下降法的基本思想及特点牛顿方向Newton法

min f x0 f x0
0
2
即进行线搜索
0
min{ 2 4 25 2 100 } min ( )
2
则
解得
' ( ) 8(2 4 ) 5000(2 100 ) 0
626 0 0.02003072 31252
方法分类： 1、间接法：对简单问题，求解必要条件或充分条件；零阶法：只需计算函数值 f(x) 2、迭代算法：一阶法：需计算 ▽f(x) 直接法梯度法
二阶法：需计算
▽ 2 f(x)
考虑无约束优化问题：
min f ( x) n
x R
本章主要介绍无约束最优化方法，它的应用比较广泛，理论比较成熟。另一方面，通常可以把一些约束优化问题转化为无约束问题来处理，所以它是最优化方法中的基本方法。
下面说明最速下降法收敛性的几何意义。考虑具有对称正定矩阵的函数
1 T 1 2 2 f ( x) x Qx 1 x1 2 x 2 2 2
其中 2 1 0 这个函数的等值线为
1 Q 0 0 2
f x1 , x2 c (c＞0) ，改写为：
，等值线是很扁的椭圆，此时
q
2 1 1 2 1
对于一般的初始点收敛速度可能十分缓慢，锯齿现象严重。
x2
x0
x1
（五）优缺点
1、优点：计算简单，需记忆的容量小；对初始点要求低，稳定性高；远离极小点时收敛快，常作为其它方法的第一步。 2、缺点：收敛速度较慢（线性或不高于线性）。原因是最速下降方向只有在该点附近有意义。
解：梯度 f (x)＝[2x1, 8x2 ]T 。 1. 第一次迭代： f ( x(0) )＝[2, 8 ]T ， x(1) = x(0) + t0 p(0) = x(0) － t0 f (x(0))＝ [1,1]T － t0 [2, 8 ]T 用一维搜索求t0 ，对简单f(x)，可用解析法求解：设0 (t)＝f ( x(1) )＝f ( [1,1]T － t[2, 8 ]T )＝(1－2t)2+4(1－8t)2 ’0(t)＝520t－68＝0 t0 ＝0.130769

最优化各算法介绍

最速下降法：算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点。

沿负梯度方向函数值下降很快的特点，容易使认为这一定是最理想的搜索方向，然而事实证明，梯度法的收敛速度并不快．特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢。

其原因是由于每次迭代后下一次搜索方向总是与前一次搜索方向相互垂直，如此继续下去就产生所谓的锯齿现象。

从直观上看，在远离极小点的地方每次迭代可能使目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代行进距离缩短，因而收敛速度不快.牛顿法：基本思想：利用目标函数的一个二次函数去近似一个目标函数，然后精确的求出这个二次函数的极小点，从而该极小点近似为原目标函数的一个局部极小点。

优点 1. 当目标函数是正定二次函数时，Newton 法具有二次终止性。

2. 当目标函数的梯度和Hesse 矩阵易求时，并且能对初始点给出较好估计时，建议使用牛顿法为宜。

缺点：1. Hesse 矩阵可能为奇异矩阵，处理办法有：改为梯度方向搜索。

共轭梯度法：优点：收敛速度优于最速下降法，存贮量小，计算简单.适合于优化变量数目较多的中等规模优化问题.缺点：变度量法：较好的收敛速度，不计算Hesse 矩阵1．对称秩1 修正公式的缺点（1）要求( ) ( ) ( ) ( ) ( ) 0 k k k T k y B s s − ≠0（2）不能保证B ( k ) 正定性的传递2．BFGS 算法与DFP 算法的对比对正定二次函数效果相同，对一般可微函数效果可能不同。

1） BFGS 算法的收敛性、数值计算效率优于DFP 算法；（2） BFGS 算法要解线性方程组，而DFP 算法不需要。

基本性质：有效集法：算法思想：依据凸二次规划问题的性质2，通过求解等式约束的凸二次规划问题，可能得到原凸二次规划问题的最优解。

有效集法就是通过求解一系列等式约束凸二次规划问题，获取一般凸二次规划问题解的方法。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

数学与计算科学学院实验报告

实验项目名称使用非精确线搜索Armijo算法确定步长的最速下降法所属课程名称最优化方法实验类型算法编程实验日期

班级学号姓名成绩一、实验概述：【实验目的】 1.通过实验掌握最速下降法的Matlab算法的基本步骤； 2.通过实验掌握Armijo算法确定步长； 3.掌握最速下降法的思想及迭代步骤。

【实验原理】 1.最速下降法：最古老的优化方法，十九世纪中叶由Cauchy提出思想：每次沿负梯度方向进行搜索

负梯度方向也称为最速下降方向：举例：

kx●

)(kxf

● 等值线(面)

● 1k

PxfxfxfpxfxfpxfPxfPxfpRpTkpkkkkkkTkn)(min||)(||)(- ||)(||)(-||)(||-||||||)(||-)(Schwarz-Cauchy,||||||||的解是下列问题时等号成立，即当取

不等式得由且事实上，对任意算法步骤： .2,1:,4;33),(-.,||)(||2;0.0,1k1k0转步令步由线性搜索计算步长步；然后转步计算否则算法终止，则得解若步令精度给定初始点步kkdxxxfdxxfkRx

kkkkkkkn



优点： .,最优解以较慢的速度无限接近但能优解代并没有求出其精确最最速下降法在有限次迭数极小化问题，对于简单的二元二次函

最速下降法的收敛性：全局收敛性：

.,|||| ||)(|| ,0,降算法的全局收敛性我们很容易得到最速下所以且即方向与负梯度方向一致由于最速下降法的搜索kkkdxf

0||)(||lim }{Powell-WolfeArmijo ,kkkxfx满足代序列的迭搜索的最速下降法产生搜索或或采用精确搜索 ,,至多是线性的最速下降法的收敛速度由例子看到收敛速度估计： 21

***1minmaxminmax||||,3.2 ||-||11-||-|| }{21)(min .,.,QxxxxxxxxxxqQxxxfQRqQT

QkQkkTTn是问题的惟一解其中

）（

满足速下降法产生的点列则由采用精确搜索的最

问题：化考察如下二次函数极小的最大和最小特征值分别是和记对称正定设矩阵



)](-)([11-)(-)( )2.3(||-||21)-()-(21)(-)( 0)( )(,*2*12**T*****xfxfxfxfxxxxQxxxfxfqQxxfxqQxxfkkQ可以改写成所以则处且在由于对于二次函数.,( .,1 , ,1,,,)2.3(算法收敛很慢接近病态）较大时而当求出最优解算法只需一次迭代即可的所有特征值相等时即当特别最速下降收敛很快接近于当有关的条件数矩阵最速下降的收敛速度与看到由收敛速度估计式QQQ 结论：最速下降法的收敛速度比较慢，通常将其用在某些算法的初始阶段求较好的初始点或作为某些算法的间插步.

【实验环境】 Win 7；

二、实验内容：【实验方案】 1、求梯度； 2、向梯度相反的方向移动x，其中为步长。如果步长足够小，则可以保证每一次迭代都在减小，但可能导致收敛太慢，如果步长太大，则不能保证每一次迭代都减少，也不能保证收敛。 3、循环迭代步骤2，直到x的值变化到使得在两次迭代之间的差值足够小，比如，也就是说，直到两次迭代计算出来的基本没有变化，则说明此时已经达到局部最小值了。 4、此时，输出x，这个x就是使得函数最小时的x的取值。【实验过程】梯度下降法的计算过程就是沿梯度下降的方向求解极小值（也可以沿梯度上升方向求解极大值）。

其迭代公式为 ,其中代表梯度负方向，表示梯度方向上的搜索步长。梯度方向我们可以通过对函数求导得到，步长的确定比较麻烦，太大了的话可能会发散，太小收敛速度又太慢。一般确定步长的方法是由线性搜索算法来确定，即把下一个点的坐标ak+1看做是的函数，然后求满足f(ak+1)的最小值的即可。因为一般情况下，梯度向量为0的话说明是到了一个极值点，此时梯度的幅值也为0.而采用梯度下降算法进行最优化求解时，算法迭代的终止条件是梯度向量的幅值接近0即可，可以设置个非常小的常数阈值。

【实验结论】（结果）梯度下降法处理一些复杂的非线性函数会出现问题，例如Rosenbrock函数：其最小值在处，函数值为。但是此函数具有狭窄弯曲的山谷，最小点就在这些山谷之中，并且谷底很平。优化过程是之字形的向极小值点靠近，速度非常缓慢。靠近极小值时收敛速度减慢。直线搜索时可能会产生一些问题。可能会“之字形”地下降。【实验小结】（收获体会）

这次的实验报告，使得我们对这些算法的思想更加了解，在选择线性搜索的方法时，我们

深刻体会到各类参数设置对程序效率的重要性，不同的问题要选用合适的参数来求解，这样使得问题求解及程序运行的效率最高。通过不断地翻阅课本，剖析程序，我们最后实现了对程序的修改和完善，对提供的问题作出了较好的解答。总的来说，对无约束最优化的求解，每种方法在解决不同的问题中效果不能都达到最优，所以我们在实际应用中，要根据实际情况选择合适的方法，争取最大可能的尽快的接近最优。本次实验不仅使我们基本了解了最优化的实用算法的结构及性能，而且也使得我们对matlab的一些编程技巧更加熟悉，收获很大。

三、指导教师评语及成绩：评语评语等级

优良中及格不及格 1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强 2.实验方案设计合理 3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻） 4实验结论正确.

成绩：指导教师签名：批阅日期：附录1：源程序 Armijo算法实现：

[plain] view plaincopy function mk = armijo( fun, xk, rho, sigma, gk )

assert( rho > 0 && rho < 1 ); assert( sigma > 0 && sigma < );

mk = 0; max_mk = 100; while mk <= max_mk x = xk - rho^mk * gk; if feval( fun, x ) <= feval( fun, xk ) - sigma * rho^mk * norm( gk )^2 break; end mk = mk + 1; end

return; 最速下降法实现： [plain] view plaincopy function [opt_x, opt_f, k] = grad_descent( fun_obj, fun_grad, x0 )

max_iter = 5000; % max number of iterations EPS = 1e-5; % threshold of gradient norm

% Armijo parameters rho = ; sigma = ; % initialization k = 0; xk = x0;

while k < max_iter k = k + 1; gk = feval( fun_grad, xk ); % gradient vector dk = -1 * gk; % search direction

if norm( dk ) < EPS break; end

yk = feval( fun_obj, xk ); fprintf( '#iter = %5d, xk = %.5f, F = %.5f\n', k, xk, yk );

mk = armijo( fun_obj, xk, rho, sigma, gk ); xk = xk + rho^mk * dk; end

fprintf( '----------------------\n' ); if k == max_iter fprintf( 'Problem Not solved!\n' ); else fprintf( 'Problem solved!\n' ); end

% record results opt_x = xk; opt_f = feval( fun_obj, xk );

return;

附录2：实验报告填写说明 1．实验项目名称：要求与实验教学大纲一致。 2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。 3．实验原理：简要说明本实验项目所涉及的理论知识。 4．实验环境：实验用的软、硬件环境。 5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。对于创新性实验，还应注明其创新点、特色。 6．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。 7．实验结论（结果）：根据实验过程中得到的结果，做出结论。 8．实验小结：本次实验心得体会、思考和建议。 9．指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。