哈工大-优化算法

数学模型是根据具体要求和条件，对实际问题的数学描述和概括。一方面希望建立一个尽可能完善的数学模型，以求精确的表达实际问题，得到满意的设计结果；另一方面有要求建立的数学模型尽可能简单，以方便计算求解。数学模型一般由设计变量、目标函数和约束条件三部分组成，写成向量形式为：min f(X)x6Rnstguw<Q(u=l,2,...,p)

知(X)=0(v=1,2,算法的收敛速度：对于与迭代次数无关的常数oe(04),如果存在p>l使下式成立:・||xk+l—X*||

网||Xk—X*||F当f=1时，称算法具有线性收敛性；当1V0V2时，称算法具有超线性收敛性；当。=2时，称算法具有二次收敛性常用终止准则：||Xk+1||Xk+1-Xk||<E值差准则:|f(xk|f(xk)-f(xk+1)|<£或f(xk)-f(xk+1)梯度准则:梯度定义:||Vf(Xk+l)||<Vf(x梯度定义:||Vf(Xk+l)||<Vf(xk)=s°=矩阵泰勒展开(取三项)f(X)代f(xk)+[vf(xk)]T[x-xk]+i[x-xk]Tv2f(xk)[x-xk]其中f(X)的二阶导数矩阵称为黑塞(Hessian)矩阵，记作H(Xk)：V2f(XkV2f(Xk)=H(Xk)=a2f(xk)

dxl

a2f(xk).

■a2f(xk)

dxndxL52f(Xk)

dx±dx2

d2f(Xk)

.

.d2f(Xk)dxndx711a2f(xkyOxidxnd2f(Xk)dx2dxn.

.d2f(Xk)dxn-正定二次函数的性质：等值线是一组同心椭圆,椭圆中心就是二次函数的极小点正定二次函数的性质：等值线是一组同心椭圆,椭圆中心就是二次函数的极小点负定矩阵：奇数阶子式小于0,偶数阶子式大于0确定初始区I可；若f(xi)>/(x2)> 则极小点位于点X2右侧若f(X])V/(X2)</(X3)，则极小点位于点X2左侧若f(x。>/(%2)V/(x3)>则极小点位于阮切之间

一维搜索黄金分割法：Xi=a+0.382(b—a)改止准则.jbX2=a+0.618(b-a)八 x*=—(a+b)2斐波那契法(Fibonacci)：Fn-k-1 、Xi= + 血-ak)01-k+lFn-k n 、X2= + (bk - ak)01-k+l区|DJ长度bk+i—ak+i=x2— =bk—Xx确定n值：nan-1)— 、 bnan-1)— 、 b】一Hi—-o<6b2-3庆F-FflFl-F2Fl-F2l_Fn---终止准则：k=n-1,即Fn—k+i=F2时a+ba+b22f(xi)V/(x2)a+ba+b22f(xi)V/(x2)f(Xl)>/(x2)二次插值法:2(x2一x3)4+(X3-xx2(x2一x3)4+(X3-xx)f2+(xi-x2)f3终止准则:|x2-Xp|<£

x”=min{f(X2),f(xp))终止准则:无约束最优化方法梯度法(最速下降法)：Sk=-Vf(xk)Xk+1=-Xk+akSk特点：[Vf(Xk+1)]TVf(Xk)=0,即相邻两次迭代点的梯度彼此正交，越接近极小点，阶梯越小，前进速度越慢。因此从局部看下降较快，从全局看下降较慢。基本牛顿法：Sk=-[V2f(Xk)]-1Vf(Xk)Xk+1=Xk+Sk阻尼牛顿法：Sk=-[V2f(Xk)]-1Vf(Xk)Xk+i=Xk+akSk拟牛顿法(变尺度法):

坐标变换：引入变换矩阵X—Xk=UY,并要求UTV2f(Xk)U=I,得a=uut=[v2f(xk)]-1迭代算法(Ak称为变尺度矩阵，Ek称为校正矩阵)：Sk=-AkVf(Xk)Xk+1=Xk-akAkVf(Xk)Ak+1=Ak+Ek因Ek的计算不同而有不同的算法，其中AXk=Xk+1-XkAgk=Vf(Xk+1)-Vf(Xk)RankOneCorrection:k_(AXk-AkAgk)(AXk-AkAgk)T=(AXk-AkAgk)AgkRandTwoCorrectionKDFP:Davidon-Fletcher-Powelly]]：k_AXk[AXk]TAkAgk(AkAgk)T_[AXk]TAgk-[Agk]TAkAgkRankTwoCorrectionKBFGS:Broyden-Fletcher-Goldfarb-ShannaS：k_([Agk]TAkAgk\AXk[AXk]TAXk[Agk]TAk+AkAgk[AXk]TE=P+[AXk]TAgkHAXk]TAgk-[AXk]TAgk共钥梯度法：共铜向量：假设正定对阵矩阵H,对于一组非零向量Si，S2，…,Sn,如果存在斗'HSj=O,则称该组向量是矩阵H的一组共轴向量。当H为单位矩阵时，该组向量相互正交。因此，共扼是正交的推广，正交是共辄的特例。由第苦fg+a曲=。X1=X°+aos°X2=X1+aiS1又因为[Vf(Xx)]TSo第苦fg+a曲=。[S^HS1=0结论：从任意点出发，沿这两个共扼方向进行一维搜索，经两次迭代即可达到极小点。共轴方向的性质：若S\i=1,2，…,71）是关于H共机的n个向量，则依次沿这n个方向进行一维搜索，最多n次即可达到极小点；从任意两个点X?、Xg出发沿同一方向S。进行两次一维搜索，得到两个极小点况、X*,连接此两点构成的向量S】=X：-X*与原方向s°关于二阶导数矩阵共轴基向量组合法：Isk+1=ek+^pisi [s]侦f(x)/I i=on&=一[Si]"f(x)Si[削七2昭)伊+1]=0梯度组合法：sk+1=-Vf(Xk+1)+pksk_[Vf(Xk)]TV2f(X)Vf(Xk+1)[Sk]Vf(X)[Sk+1]=0 -Vf(Xk)]Tv2f(x)—f(xk)PRP(Polyok-Ribere-Polak)algorithm:[Vf(xk+1)]T(Vf(xk+1)一Vf(xk))队= l.f(Xk)||2FR(Fletcher-Reeves)algorithm:(7f(Xk+1)=HXk+1+B "(川•:・梯度法、牛顿法、拟牛顿法、共轴梯度法的终止准则—yk+1||仃*+】)||京时，m,(xk+i)6修整鲍威尔法(PoweU)：引入相关量反射点X『2=2XjJ-x£q=f(X0f2=f(XjJ)f3(x")卜降量Am=max{f(xD-f(X~)}新方向与原方向组线性无关判别式f3<fi(fl一2f?+f3)(fl—f2—Am)2v-Ara(fl—f3)2若成立，则替换原方向