上交最优化课件

《上交最优化课件》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、最优化理论与方法HouLikun上海交通大学自然科学研究院houlk@sjtu.edu.cnNovember24,2014HouLikun最优化理论与方法非线性最小二乘HouLikun最优化理论与方法目目目标标标：求解如下形式的最优化问题Xm12minf(x):=ri(x);x2Rn2i=1其中至少有一个ri(x)是非线性[仿射]函数.上面的问题称为非线性最小二乘问2题.3r1(x)66r2(x)77若记r(x)=6.7,则r:Rn7!Rm是一个非线性映射。此4..5rm(x)时非线性最小二乘问题可以写成1>minf(x):=r(x)r(x):x2Rn2HouLiku

2、n最优化理论与方法背景知识主主主要要要应应应用用用领领领域域域：数据拟合，参数估计，函数逼近，等等.一一一个个个例例例子子子:假设我们有一组数据(t1;y1);(t2;y2);:::(tm;ym).我们要用一个非线性函数(或称非线性模型)(t;x)来拟合这些数据(yi(ti;x)).为了使(t;x)能很好地拟合所给的数据，人们往往通过求解下面的极小化问题来估计非线性函数(t;x)的参数xXm12mink(ti;x)yik:x2i=1上面的问题就是一个典型的非线性最小二乘问题，对应的ri:=(ti;x)yi.HouLikun最优化理论与方法基本计算1P

3、m2nf(x):=r(x);x2R:2i=1if(x)的梯度rf(x)是Pm>rf(x)=i=1rirri(x)=J(x)r(x);其中23@r1@r1


@r1@x1@x2@xn6@r2@r2@r27J(x):=66@x1@x2


@xn774











5@rm@rm


@rm@x1@x2@xn称为映射r(x)的Jacobian.f(x)的Hessian矩阵P
r2f(x):=mrr(x)rr(x)>+r(x)r2r(x)i=1iiii=J(x)>J(x)+S(x)Pm2其中S(x)=i=1ri(x)rri(x)HouLikun最优化理论与方法Ga

4、ussian-Newton方法牛牛牛顿顿顿法法法xk+1=xk[r2f(xk)]1rf(xk)>
1>=xkJ(xk)J(xk)+S(xk)J(xk)r(xk)算法（局部）平方收敛，但当m很大时，计算Hessian矩阵的二阶项S(xk)的代价较高.Gauss-Newton方方方法法法放弃Hessianr2f(xk)矩阵中的二阶项S(xk),使用如下形式的迭代算法>
1>xk+1=xkJ(xk)J(xk)J(xk)r(xk)当J(x)列满秩序时，J(xk)>J(xk)就是一个是正定矩阵，此时若rf(xk)=J(xk)>r(xk),不为零向量，则>

5、1>J(xk)J(xk)J(xk)r(xk)就是目标函数f在点xk的一个下降方向.HouLikun最优化理论与方法Guass-Newton方法{步骤Initialization:Chooseinitialpointx02Rn,errortolerance,setk=0.whilekrf(xk)k>doSolveJ(x)>J(x)s=J(x)>r(x);kkkkanddenotethesolutionbysk;Setxk+1=xk+skSetk=k+1endQuestion:如果用CG法求解上面算法中的线性系统，我们需要生成并存储JacobianJ(xk)和矩阵J

6、(xk)>J(xk)吗?HouLikun最优化理论与方法等价性ri(x)在xk邻域内的一阶近似ri(x)ri(xk)+rri(xk)>(xxk),从而r(x)r(xk)+J(xk)>(xxk).min1kr(x)k2min1kr(x)+J(x)(xx)k2.x2x2kkk问题minkr(xk)+J(xk)(xxk)k2的是一个凸规划问题，其一阶最优性条件是J(x)>J(x)(xx)=J(x)>r(x);kkkkk>
1>从而最优解为xkJ(xk)J(xk)J(xk)r(xk),也就是Gauss-Newton算法中的后继点xk+1:Gauss

7、-Newton方法,r(x)局部线性化HouLikun最优化理论与方法收敛性分析收收收敛敛敛速速速度度度显然，Gauss-Newton方法的收敛速度取决于被忽略掉的二阶项S(x)在Hessian矩阵中的重要性.设x函数f一个满足一阶最优性条件的点，并设Gauss-Newton方法的起始点充分接近x,则如果S(x)=0,则Gauss-Newton方法产生的序列平方收敛于x.如果S(x)相对于J>(x)J(x)很小，则Gauss-Newton方法产生的序列收敛于x,收敛阶为q,1