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

1、 沖理 数学与计算科学学院 实验报告 实验项目名称使用非精确线搜索 Armjo算法确定步长 的最速下降法 所属课程名称最优化方法 实验类型算法编程 实验日期 班 级 学 号 姓 名 成 绩 、实验概述： 【实验目的】 1. 通过实验掌握最速下降法的Matlab算法的基本步骤; 2. 通过实验掌握Armijo算法确定步长； 3. 掌握最速下降法的思想及迭代步骤。 【实验原理】 1.最速下降法： 最古老的优化方法，十九世纪中叶由 Cauchy提出 思想：每次沿负梯度方向进行搜索 等值线（面） 负梯度方向也称为最速下降方向: 举例： 事实上，对任意p Rn且|p|j, 由Cauchy - Schwa

2、rz不等式得 (Xk)TP-|Pf(Xk)| |P|F-|f(Xk)| 当取p = Nf(Xk)时等号成立，即p= MX)是下列问题 |f(Xk)|匹 f(Xk)| 的解 mam 算法步骤: 步1给定初始点X。 Rn,精度；.0令k=0; 步2若|f(xk)肚，则得解xk,算法终止否则 计算dA f (Xk),然后转步3； 步3由线性搜索计算步长:-k; 步4 令Xk 1 二x: kdk,kuk 1,转步 2. 优点： 对于简单的二元二次函 数极小化问题， 最速下降法在有限次迭 代并没有求出其精确最 优解,但能 以较慢的速度无限接近 最优解. 最速下降法的收敛性： 全局收敛性： 由于最速下降法

3、的搜索 方向与负梯度方向一致，即二k =0,且 |W(Xk)|dk| 所以，我们很容易得到最速下 降算法的全局收敛性. 的迭 采用精确搜索，或Armijo搜索或Wolfe - Powell搜索的最速下降法产生 代序列3讣满足 lim |f (xj |=0 k_. 由例子看到，最速下降法的收敛速度至多是线性的， 收敛速度估计： 设矩阵Q对称正定,q Rn .记 max和饰分别是Q 的最大和最小特征值，瓷=如竺.考察如下二次函数极小化 min 问题： 1 tT min f (x)二 x Qx q x 2 则由采用精确搜索的最速下降法产生的点列 Xk满足 |Xk + -x* IQ 兰|Xk-x*|Q

4、(3.2) 1 *-I- 其中x是问题的惟一解，| x |Q二x Qx 2 7 对于二次函数，由于I f （x） = Qx q且在x处 、f （x ） = Qx q = 0 1* t*1*2 则 f (x)- f (x ) (x-x ) Q(x-x )| x-x |q 2 2 所以(3.2)可以改写成 f (Xk 1)- f (x ) 0 mk = 0; max_mk = 100; while mk = max_mk x = xk - rhoAmk * gk; if feval( fun, x ) = feval( fun, xk ) - sigma * rhoAmk * norm( gk )

5、八2 break; end mk = mk + 1; end return; 最速下降法实现： pla in view pla in copy fun cti on opt_x, opt_f, k = grad_desce nt( fun_obj, fun _grad, x0 ) max_iter = 5000;% max nu mber of iterati ons EPS = 1e-5;% threshold of gradie nt norm % Armijo parameters rho = 0.5; sigma = 0.2; % in itializatio n k = 0; xk

6、= x0; while k max_iter k = k + 1; gk = feval( fun _grad, xk ); % gradie nt vector dk = -1 * gk;% search directi on if norm( dk ) EPS break; end yk = feval( fun_obj, xk ); fprintf( #iter = %5d, xk = %.5f, F = %.5fn, k, xk, yk ); mk = armijo( fun_obj, xk, rho, sigma, gk ); xk = xk + rhoAmk * dk; end f

7、printf( n); if k = max_iter fprintf( P roblem Not solved!n); else fpri ntf( Problem solved!n); end % record results opt_x = xk; opt_f = feval( fun _obj, xk ); return; 附录2:实验报告填写说明 1 实验项目名称： 要求与实验教学大纲一致。 2 实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。 3 实验原理：简要说明本实验项目所涉及的理论知识。 4.实验环境：实验用的软、硬件环境。 5实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。 对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步 骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设 计思路和设计方法，再配以相应的文字说明。对于创新性实验，还应注明其创新点、特 色。 6实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实