上交最优化课件

《上交最优化课件》由会员分享，可在线阅读，更多相关《上交最优化课件（28页珍藏版）》请在金锄头文库上搜索。

1、最优化理论与方法Hou Likun上海交通大学自然科学研究院November 24, 2014Hou Likun最优化理论与方法非线性最小二乘Hou Likun最优化理论与方法目目目标标标：求解如下形式的最优化问题minxRnf (x) :=12mXi=1r2i(x),其中至少有一个ri(x)是非线性仿射函数. 上面的问题称为非线性最小二乘问题. 若记r(x) =r1(x)r2(x).rm(x), 则r : Rn7 Rm是一个非线性映射。此时非线性最小二乘问题可以写成minxRnf (x) :=12r(x)r(x).Hou Likun最优化理论与方法背景知识主主主要要要应应应用用用领领领域域域

2、：数据拟合，参数估计，函数逼近，等等. 一一一个个个例例例子子子:假设我们有一组数据(t1, y1), (t2, y2), .(tm, ym). 我们要用一个非线性函数(或称非线性模型)(t,x)来拟合这些数据(yi (ti,x). 为了使(t,x)能很好地拟合所给的数据，人们往往通过求解下面的极小化问题来估计非线性函数(t,x)的参数xminx12mXi=1k(ti,x) yik2.上面的问题就是一个典型的非线性最小二乘问题，对应的ri:= (ti,x) yi.Hou Likun最优化理论与方法基本计算f (x) :=12Pmi=1r2i(x), x Rn.f (x)的梯度f (x)是f (

3、x) =Pmi=1riri(x) = J(x)r(x),其中J(x) :=r1x1r1x2r1xnr2x1r2x2r2xnrmx1rmx2rmxn称为映射r(x)的Jacobian.f (x)的Hessian矩阵2f (x) :=Pmi=1?ri(x)ri(x)+ ri(x)2ri(x)?= J(x)J(x) + S(x)其中S(x) =Pmi=1ri(x)2ri(x)Hou Likun最优化理论与方法Gaussian-Newton方法 牛牛牛顿顿顿法法法xk+1= xk 2f (xk)1f (xk)= xk?J(xk)J(xk) + S(xk)?1J(xk)r(xk) 算法（局部）平方收敛，

4、但当m很大时，计算Hessian矩阵的二阶项S(xk)的代价较高. Gauss-Newton方方方法法法 放弃Hessian2f (xk)矩阵中的二阶项S(xk), 使用如下形式的迭代算法xk+1= xk?J(xk)J(xk)?1J(xk)r(xk) 当J(x)列满秩序时，J(xk)J(xk)就是一个是正定矩阵，此时若f (xk) = J(xk)r(xk), 不为零向量，则?J(xk)J(xk)?1J(xk)r(xk)就是目标函数f 在点xk的一个下降方向.Hou Likun最优化理论与方法Guass-Newton方法 步骤Initialization: Choose initial poin

5、t x0 Rn, error tolerance ?, setk = 0.while kf (xk)k ? doSolveJ(xk)J(xk)s = J(xk)r(xk),and denote the solution by sk;Set xk+1= xk+ skSet k = k + 1endQuestion: 如果用CG法求解上面算法中的线性系统，我们需要生成并存储JacobianJ(xk)和矩阵J(xk)J(xk)吗?Hou Likun最优化理论与方法等价性 ri(x)在xk邻域内的一阶近似ri(x) ri(xk) + ri(xk)(x xk),从而r(x) r(xk) + J(xk)(

6、x xk). minx12kr(x)k2 minx12kr(xk) + J(xk)(x xk)k2. 问题minkr(xk) + J(xk)(x xk)k2的是一个凸规划问题，其一阶最优性条件是J(xk)J(xk)(x xk) = J(xk)r(xk),从而最优解为xk?J(xk)J(xk)?1J(xk)r(xk), 也就是Gauss-Newton算法中的后继点xk+1.? Gauss-Newton方法 r(x)局部线性化Hou Likun最优化理论与方法收敛性分析 收收收敛敛敛速速速度度度 显然，Gauss-Newton方法的收敛速度取决于被忽略掉的二阶项S(x)在Hessian矩阵中的重要

7、性. 设x函数f 一个满足一阶最优性条件的点，并设Gauss-Newton方法的起始点充分接近x, 则如果S(x) = 0, 则Gauss-Newton方法产生的序列平方收敛于x.如果S(x)相对于J(x)J(x)很小，则Gauss-Newton方法产生的序列收敛于x, 收敛阶为q, 1 q (x)J(x)很大，则算法产生的序列通常不收敛.Hou Likun最优化理论与方法收敛性分析(Contd)Theorem设f (x) =12Pmi=1r2i(x)是定义在Rn上的二阶连续可微连续函数,x是f (x)的一个局部极小点, 且J(x)J(x)正定. 假设由Gauss-Newton方法产生的序列x

8、k收敛到x,若2f (x)和J(x)J(x)1在x的邻域内Lipschitz连续, 则成立kxk+1xk 6 k?J(x)J(x)?1kkS(x)kkxkxk+O(kxkxk2).Hou Likun最优化理论与方法阻尼Gauss-Newton方法 Gauss-Newton方法对初始点敏感，且不能保证迭代产生序列的函数值是严格下降的. Gauss-Newton方法产生的搜索方向sk是f (x)在点xk的下降方向;因此，可以沿sk方向做一维搜索，求得合适的步长因子，从而保证后继点xk+1满足f (xk+1) ? doSolve J(xk)J(xk)s = J(xk)r(xk) for the so

9、lution sk;Use line-search methods to find appropriate step length kthat(approximately) solves min0f (xk+ sk);Set xk+1= xk+ ksk;Set k = k + 1.endHou Likun最优化理论与方法Levenberg-Marquardt方法问问问题题题：一方面，Gauss-Newton法使用了r(x)在xk的一阶近似，它只在xk的邻域内才能给出r(x)较好的逼近.另一方面, 在Gauss-Newton法中，若矩阵J(x)J(x)的条件数很大，则?J(x)J(x)1存在非常

10、大的特征值，因此得到的后继点xk+1= xk?J(xk)J(xk)?1J(xk)r(xk)可能会远离xk, 从而与方法的初衷相违背.Levenberg-Marquardt方方方法法法 基于Gauss-Newton方法，可以用来处理因矩阵J(x)J(x)条件数较大而带来的算法不稳定性的Hou Likun最优化理论与方法Levenberg-Marquart方法(Contd) 具具具体体体做做做法法法: 注意到，Gauss-Newton方法的迭代步骤具有如下形式xk+1= argminxRnkr(xk) + J(xk)(x xk)k2.而在Levenberg-Marquardt方法中，上面的迭代法则

11、被更改为xk+1= argminxRnkr(xk) + J(xk)(x xk)k2s.t. kx xkk 6 k. Levenberg-Marquardt方法= 含信赖域约束的Guass-Newton方法. 信赖域约束的加入，限定了r(x)在xk点出一阶近似的适用范围，提高了模型的精确程度和算法的稳定性.Hou Likun最优化理论与方法最优性条件设sk最小化问题解minsRnkr(xk) + J(xk)sk2s.t. ksk 6 k的最优解，则存在k 0, 使得?J(xk)J(xk) + kI?sk= J(xk)r(xk)(1)k(kskk k) = 0(2)kskk 6 k(3).注注注：

12、在(1)式中，若J(xk)J(xk)正定，可以证明kskk是k的减函数.当k?J(xk)J(xk)?1J(xk)r(xk)k 6 k时，k= 0,sk= ?J(xk)J(x)?1J(xk)r(xk).当k?J(xk)J(xk)?1J(xk)r(xk)k k时，k 0,sk= ?J(xk)J(xk) + kI?1J(xk)r(xk).Hou Likun最优化理论与方法另另另一一一种种种视视视角角角：Levenberg-Marquart方法可以看做是介于Gauss-Newton方法和最速下降法之间的切换准则, 特别的当k= 0时，L-M方法就是Gauss-Newton法；当k很大时，通过L-M方法

13、得到的搜索方向会非常接近于最速下降方向.Hou Likun最优化理论与方法Initialization Choose x0 Rn, 0, 0 (0,) and 0,14), errortolerance ?, set k = 0:while kf (xk)k(= kJ(xk)r(xk)k) ? do(i) Obtain skby (approximately) solvingminsRnkr(xk) + J(xk)sk2s.t. ksk 6 k.(ii) Evaluate k=f (xk)f (xk+sk)f (xk)mk(sk), where mk(sk) = kr(xk) + J(xk)s

14、kk2if k34and kskk = kthenk+1= min(2k,)elsek+1= k;endendif k thenxk+1= xk+ sk.elsexk+1= xk.endset k = k + 1endHou Likun最优化理论与方法Theorem设下面的条件成立(i) 对于任意 x Rn, 水平集L( x) := x | f (x) 6 f ( x)都是有界闭集;(ii) f (x)取值相同的驻点的数目是有限的;(iii) 对于任意的x Rn, J(x)J(x)都是正定的;(iv) 存在M 0, 使得k 0, i I, gi(x) = 0, i E. 起起起作作作用用用集集

15、集（active set）: 给定点x Rn, x的起作用集A(x)定义为A(x) := E i I : gi(x) = 0Hou Likun最优化理论与方法约束最优化问题 一阶必要条件Definition (线性无关约束规格LICQ)给定x, 如果gi(x), i A(x)是一组线性无关的向量，则称线性无关约束规格(Linear independent constraint qualification LICQ)在x成立或称点x满足正则性条件 课本上的叫法，不规范.Theorem设x是约束最优化问题的一个局部极小点，且LICQ在x成立，则存在向量, 对于其每一个分量i,i E I, 成立下面

16、的关系式f (x) Piigi(x) = 0,(1)gi(x) = 0,for all i E,(2)gi(x) 0,for all i I,(3)i 0,for all i I,(4)igi(x) = 0,for all i E I.(5)Hou Likun最优化理论与方法约束最优化问题 一阶必要条件(Contd)f (x) Piigi(x) = 0,(1)gi(x) = 0,for all i E,(2)gi(x) 0,for all i I,(3)i 0,for all i I,(4)igi(x) = 0,for all i E I.(5) 上述条件称为Karush-Kuhn-Tucke

17、r条件，简称KKT条件. 满足KKT条件的点称为KKT点(课本中称为K-T 点).(2)和(3)称为可行性条件(primal feasibility)(4)称为对偶可行性条件(dual feasibility)(5)称为互补松弛条件(complementary slackness) 定义Lagrange函数L(x,) = f (x) Piigi, 则条件(1)可以写作xL(x,) = 0.Hou Likun最优化理论与方法可行序列及其极限方向Definition (可行序列(feasible sequence)给定约束最优化问题的一个可行点x, zkk=0是Rn中的一个序列。如果下列性质成立(

18、i) 对于任意k都有zk6= x,(ii) limkzk= x,(iii) 对于所有充分大的k, zk都是约束问题的可行点(即存在K 0, 当k K时, zk可行)则称zk是一个可行序列.Definition (可行序列的极限方向(limiting directions)设zkk=0是趋于x的可行序列，若存在zk的子序列znkk=0和单位向量d, 使得 limkznkxkznkxk= d, 则称d是序列zk的一个极限方向(limiting direction).Hou Likun最优化理论与方法 记所有趋近于点x的可行序列为T (x), 则我们有下面的定理Theorem设x是目标函数f 在可行

19、域上的局部极小点，则对任意T (x)中的可行序列zk，都成立f (x)d 0,其中d是序列zk的任一极限方向.注注注：基于极限序列和极限方向的概念，上面的定理给出了约束问题最优解的一个必要条件。可惜的是，这两个概念过于抽象，在实际问题中难以应用。Hou Likun最优化理论与方法极限方向的刻画：约束规格Lemma (极限方向的刻画)设x约束最优化问题的一个可行点，那么下面的叙述成立(i) 若d Rn是T (x)中某个可行序列的极限方向，则成立?gid = 0,for all i E,gid 0,for all i A(x) I.(?)(ii) 若单位向量d(即kdk = 1)满足上面的关系式(

20、?), 且LICQ在点x成立，则d一定是T (x)中某个可行序列的极限方向.Definition (极限方向张成的锥)给定x，设它的起作用集是A(x), 我们定义如下的锥F1=?d? 0,gid = 0,for all i E,gid 0,for all i A(x) I.?Hou Likun最优化理论与方法Theorem给定约束最优化问题的可行点x，则下面的两条叙述等价(i) 不存在d F1使得f (x)d 0 for i A(x) I.Hou Likun最优化理论与方法求解KKT点f (x) Piigi(x) = 0,(1)gi(x) = 0,for all i E,(2)gi(x) 0,

21、for all i I,(3)i 0,for all i I,(4)igi(x) = 0,for all i E I.(5)求求求解解解KKT点点点：通常先通过求解KKT条件的(1)和(5)得到相应的x和, 再验证所得的解是否满足可行性条件(2)(3)(4).Hou Likun最优化理论与方法验证KKT点 ExamplesExample给定约束最优化问题min(x1 2)2+ x22s.t. x1 x22 0x1+ x2 0. 验证x(1)=?00?和?11?是否为KKT点.Example给定最优化问题min(x132)2+ (x212)4s.t. 1 x1 x2 01 x1+ x2 01 + x1 x2 01 + x1+ x2 0验证x=?10?是否未为KKT 点.Hou Likun最优化理论与方法