光滑牛顿法求解e1范数优化问题

作     者：贾洪涛 

作者单位：大连理工大学 

学位级别：硕士

导师姓名：张宏伟

授予年度：2010年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主      题：e1范数 二阶锥约束 光滑牛顿法 全局收敛性 局部二次收敛 

摘      要：在工程应用中,通常用对象的多个特征构成的高维向量来描述这个对象。在线性赋范空间中,对象间的相似性经常由差向量的l1范数来表征。比如在人脸识别系统中,人的面部特征就可以由高维向量来表示,然后构建l1范数优化模型进行求解来达到对人脸识别的目的。所以l1范数优化模型的求解也就变得十分重要。 本文研究的是一类线性约束的l1范数优化问题。通过引进二阶锥约束,可以将目标函数转化为光滑函数从而将原问题转化为二阶锥约束优化问题。为了研究方便,我们根据对偶理论构建了原问题的对偶问题,然后对对偶问题进行求解。在求解过程中,引入Fischer-Burmeister函数来等价替换KKT系统中的互补条件,将对偶问题的KKT系统转化为一个非光滑方程组进而采用带有Armijo线搜索的光滑牛顿法进行求解。我们验证了JΦ的非奇异性,得到了该算法的全局和局部二次收敛性质。最后编写MATLAB程序进行数值求解。