第二章无约束优化问题的算法.doc

沈阳大学教案课程名称优化理论与方法 编写时间：20 年 月曰授课章节第二章无约束优化问题的算法目的要求常用的线性搜索法；无约束最优化方法重点难点常用的线性搜索法；无约束最优化方法第一节常用线性搜索法在算法的迭代格式x(k 1) =x(k) ＞；kd(k)中，在假设迭代点x(k)和下降搜索方向d(k)为已知的情况下，求步长 ：“，使f (x(j°) = f(x(k) •：』))：：：f (x(k))成立下面介绍几种求步长:-k的算法一、直接法(0.618法)(求步长)单谷函数(下单峰函数)：设t*为一元函数;：(t)的极小点，若ti ：讥2，当t2 ::: t 时，必有 仇) 址2)；当1 _t*时，必有 魚)八色)，则称：(t)为单谷函数(- 个谷)1搜索区间的确定：搜索区间的选取采取如下算法一进 -退算法：给定初始点t，初始步长h1) 计算(t), ：(t - h)；(2) 若，(t) • ：：(t h)，搜索成功，歩长加倍，若 ;：(t h^ ;:(t - 3h)，则△［a,b］二［a,t 3h］，否则步长继续加倍;(3) 若申(t) v®(t +h),搜索失败，后退一步长，若®(t) v®(t ——),则4 4= h［a,b］二［t - 一，t h］，否则继续加倍后退步长。

42 0.618算法的原理规定In・1=讥_ _ 212 =1 -a=b_t2 =b-a_l — Iq _li = l° - 'Io Io解得■ - 0.618由此可得 1 = a • (1 _%)(b _ a)t2 二 a ■ (b「a)3 0.618算法Stepi确定(t)的初始搜索区间［a,b］(进-退搜索法)、精度；；Step2 计算 ti =a (1 — )(b — a), 1 V(tJ ；Step3计算 t2 =a ，(b-a),笃二即住);* a + hStep4若半1 >徨，则令a =1,如果b —a| £名，取t = ，停止计算否2则令ti "2, 「1二2，转Step3,(此时a二G鮎=t2，在新的［a, b］区间计算t?);皿皿 * a + bStep5若® 1兰笃，则令b =t2，如果b — a < e ,取t = ，停止计算否则令 t2 * , 2 二 1，计算鮎二 a (1 - ■ )(b - a), 1= 0)，转 Step4注意：鮎=t2与t2 =t1在计算机语言中不是一回事，是一个赋值的过程二、精确线性搜索法(解析法)求步长?k，满足 f(x(k) Mkd(k)) = mif f(x(k) Wd(k))。

令(：)=f (x(k) : d(k)),:(：)八 f (x(k) ： d(k))Td(k) = 0设包含:(t)的极小值点t*的搜索区间为［a,b］，即t* • ［a,b］，在搜索区间内给a + b疋二点 to ::: b ：：： t2，且满足'(t 0 (tj ：：： ■(上2)，不妨取 to = a,b ■ ,t^ = b2令p(t) =a0 a1t a2t2是三点笛，魚))(i二0,1,2)的拟合抛物线，且设t3是抛物线t3的极小点，即(如图)2a2ti2 -t| (to) t； —t2 (ti) to -ti2 色)第二章第#页沈阳大学教案课程名称优化理论与方法 编写时间：20 年 月曰第二章第#页沈阳大学教案课程名称优化理论与方法 编写时间：20 年 月曰2 t1 - t2 (t0) t2 - t0 (t1 ) t0 _ t1 (t2)第二章第#页沈阳大学教案课程名称优化理论与方法 编写时间：20 年 月曰第二章第#页沈阳大学教案课程名称优化理论与方法 编写时间：20 年 月曰结束条件：(1) t3 ＜芯(3)若(t1)较大,①色)-④馆)%1)第二章第#页沈阳大学教案课程名称优化理论与方法 编写时间：20 年 月曰第二章第#页沈阳大学教案课程名称优化理论与方法 编写时间：20 年 月曰上述三条中的任意一条都可以作为终止准则。

如果不满足终止条件，取三点 t0 ：：：tj ：：：t3，或t3 ：： 1 :: t2，继续搜索三、不精确线性搜索法618法或解析法都可以取到 ：(t)精确近似极小点，每次迭代都可以保证使目标函数是下降的，但计算量大不精确线性搜索法不够精确但计算量较小为确保目标函数下降，步长不能太大，同时步长又不能太小，所以给一个限定 范围1Goldstein 准则取步长满足下式0 ：：： 八 f (x(k))Td⑹冬 f (x⑹)- f (x(k) tkd(k))岂-t^ f(x(k))Td(k) 上式等价于下述两个不等式第二章第#页沈阳大学教案课程名称优化理论与方法 编写时间：20 年 月曰年 月曰课程名称优化理论与方法 编写时间：20一…八 f (x(k))T d(k)乞 f (x(k)) 一 f (x(k) • tkd(k)) (2.6)f (x(k)) 一 f (x(k) • tkd(k))乞-；强八 f(x⑹)Td(k) (2.7)等价于(tQ「(0)」gTd(k) tk(tQ 一「(0) ；「gTd(k) tk等价于魚)—(0) "(0)tk：(tk)_ (0) = (0)tk注：对上式的理解，可以当 f(x)是一元函数时的特殊情况去理解。

夹在 两直线 「⑴=「(0)e v(o)t和 (tH :(0^ : (0)t与曲线「(t)=f(X(k) - td (k))相交两点之间的t满足条件式(2.6)和(2.7)，称其为可 接受区 间2Wolfe准则在Goldstein准则中，：(t)的极小点在可接受区间以外，为克服这一缺点， Wolfe准则提出一个式(2.7)的替补条件，即、f(x(k) tkd(k))Td(k) —Hf(X(k))Td(k) (2.9)可接受区间是切线丨的切点、直线:(t)= (0) A - (0)t与曲线的交点之间的t的取值区间说明：匚越小，线性搜索越精确，但计算量大第二节最速下降法对下降方向的确定条件：目标函数f(x)连续可微，\f(x(k)) = 0分析：f(x)在x(k)点处的一阶泰勒展开为f(x(k) td⑴)= f(x(k))十 f(x(k))Td(k)o(td纠)由函数梯度反方向是函数下降最快的方向(由二元函数可以看出) ，所以 令d(k)= _\、f(x(k))T 则f(x(k) f (x(x))^ f(x(k)^r f(x(k))^ f (x(k)) o(td(k))当t 0满足一定条件时可以保证 f(X⑹-1'f(x(x))) ::： f(X(k))。

说明：(1)(d(k 1))Td(k^0这是由于「⑴二 f (x(k) f (x(k)))，求步长 t，使 min :(t)令：(t)二 0，即(t^-^f(x(k) -C f (x(k)))T i f (x(k)^ -^f (x(k 1)门 f (x(k)^ 0即(d(k 1))Td(k) =02)最速下降法收敛速度慢这是由于(d(k 1))Td(k) =0，所以相邻两下降方向是相互垂直的，即下降是锯年 月曰课程名称优化理论与方法 编写时间：20齿形状，越接近极小点，锯齿现象越严重，影响收敛速度3)该方法易实现，简单，适用于一次逼近的算法，适用于距离极小点较远时 使用，在接近极小点时使用其它有效算法第三节共轭梯度法利用梯度设为下降方向，建立迭代公式，求最优解的方法 说明：该方法易实现，且储存需求小，适用于大规模优化问题的算法一、两变量正定二次函数的极小化问题设 f : R2 > R，且f (x) xTAx bTx c2其中A为正定矩阵下面讨论从任意初值点 x(0)出发，最多经过两步迭代可达到其极小点(最优解x(*))思路：选取与d(0) - -、f(x(0))线性无关的向量d⑴，且保证' f (x(*))Td(0) = 0和Vf(x(*))Td⑴=0 (这里 x(*)=x(2)=x⑴ +«id⑴)，推出 Vf(x(*))=0。

分析：任意初值点x(0)，令下降方向为d(0)=(x*)，迭代公式x⑴=x°g0d(0)，有线性搜索法确定：0，且满足「Co)八f(x⑴)Td(0) =0假若 x(*)=x(2) =x(1)+ctid(1)(最优解 x(*))，则必有\ f (x(*)) =Ax(*)b=0=A(x⑴：id⑴)b = 0=Ax⑴ b ：」Ad(1) =0='f (x ⑴)：嗣(1) = 0左乘 d(0)T= d(0)^^f(x(1)r :-1d(0)TAd(1^0这里要求 d(0)TAd(1) =0o第二章第#页沈阳大学教案年 月曰课程名称优化理论与方法 编写时间：20由于I f(x⑴)Td(0)=O，得i f(x⑴)与d(0)是线性无关的，所以向量 d⑴可由\f(x⑴)和d(0)线性表示(因为是二维空间)，设d⑴八f (x⑴厂td(0)左乘d(0)TA得d(0)TAd⑴=d(0)TAf(x⑴)td(0)TAd(0) =0由于A是正定矩阵，所以d (0)T Ad (0) • 0 ,即得+ d(0)T Af(x(1))td (0)T Ad (0)则 d(1) =\f(xe)-dd；AAdx：)d®d Ad可以证明d(1),d(0)是线性无关的，因为如果线性相关， d⑴可由d(0)线性表示，d⑴…d(0)(，O)，' f(x⑴)十 7；們(：0：)2(0)，得i f(x⑴)和 d(0) d(0)TAd(0)线性相关，矛盾。

由线性搜索法得，且满足f(x(*))Td⑴=0，由于d(0)T'f(x ⑴)Jd(0)TAd ⑴=0d ⑴，可得 i f(x(*))Td(0) =0，即^f(x(*))T(d(0),d(1)^0故' f(x(*)) = 0，即x(*)是最优解以下讨论的是n个变量的二次型问题的最优化的问题二、共轭方向的概念与性质1概念：共轭向量组：(1) A为n n阶正定矩阵；(2) p1, p2/ , pm为Rn中m个非零向量若p「Apj =0(j = j,i,j =1,2,…m),则称口，P2,…,Pm为A共轭向量组(或为A年 月曰课程名称优化理论与方法 编写时间：20正交向量组)注：当A=l时，共轭性即为通常的正交性2性质：定理2 .2设A为A为n n阶正定矩阵，p1, p2，…，pm为Rn中m个非零向量，且关于A两两共轭向量组，则 p,p2,…，pm线性无关证明：设存在一组数 &、二2，…，覚m，使得〉lPl *2P2 血…叱 mPm成立，用 p：A(j =1,2, ,m)左乘，得:j pTApj =0(j=1,2, ,m)，由于 A是正定的，Pj =0，即P；APj - 0，所以:-j =0 ,故P2,…,Pm线性无关。

引理2 .1( n维直交定理)设 P!, P2/ , Pm为线性无关的n维向量，若Rn , 。