一种求解正交约束问题的投影梯度方法_童谣

《一种求解正交约束问题的投影梯度方法_童谣》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第28卷第2期湖南理工学院学报(自然科学版)Vol.28No.22015年6月JournalofHunanInstituteofScienceandTechnology(NaturalSciences)Jun.2015一种求解正交约束问题的投影梯度方法12童谣,丁卫平(1.福州大学数学与计算机科学学院,福州350108;2.湖南理工学院数学学院,湖南岳阳414006)摘要:正交约束优化问题在特征值问题、稀疏主成分分析等方面有广泛的应用.由于正交约束的非凸性,精确求解该类问题具有一定的困难.本文

2、提出了一种求解正交约束优化问题的投影梯度算法.该算法采用施密特标准正交化方法处理2正交约束,其时间复杂度为O(rn),比传统SVD分解复杂度低,且实现简单.数值实验验证了算法的有效性.关键词:正交约束优化;投影梯度算法;邻近点算法;施密特标准正交化中图分类号:O224文献标识码:A文章编号:1672-5298(2015)02-0005-05AProjectionGradientMethodforOrthogonalityConstrainedOptimizationProblems12TONGY

3、ao,DINGWei-ping(1.CollegeofMathematicsandComputerScience,FuzhouUniversity,Fuzhou350108,China;2.CollegeofMathematics,HunanInstituteofScienceandTechnology,Yueyang414006,China)Abstract:Theorthogonalityconstrainedproblemshaswideapplicationsineigenvaluepr

4、oblems,sparseprincipalcomponentanalysis,etc.However,itischallengingtosolveorthogonalityconstrainedproblemsduetothenon-convexityoftheequalityconstraint.ThispaperproposesaprojectiongradientmethodusingGram-Schmidtprocesstodealwiththeorthogonalityconstra

5、int.2ThetimecomplexityisboundedbyO(rn),whichislowerthantheclassicalSVD.Someprimarynumericalresultsverifiedthevalidityoftheproposedmethod.Keywords:orthogonalconstrainedoptimization;projectiongradientmethod;proximalpointalgorithm;gram-schmidtprocess引言[

6、1,2]正交约束优化模型在科学与工程计算相关领域有广泛应用,譬如:线性和非线性特征值问题,组[3,4][5,6][7][8][10,11]合优化问题,稀疏主成分分析问题,人脸识别,基因表达数据分析,保角几何,1-比特压缩[12~14][15~18]传感,p-调和流,等等,都离不开正交约束优化模型.一般地,正交约束优化问题有如下形式:TminFX(),s..tXQXI.(1)nrXnr其中FX()是的可微函数,Q是对称正定阵,I是rr单位阵,nr≥.由于Q是对称正定的,可T设QL

7、L.令YLX,则(1)可转化为:TminFX(),s..tYYI&YLX.(2)nrX线性约束优化问题的求解技术已经比较成熟,为了简化问题(2)的形式,我们主要考虑求解如下正交约束优化问题:TminF()X,st..XXI.(3)nrX由于正交约束的非凸性,精确求解问题(1)或(3)具有一定的挑战.目前为止,还没有有效的算法可以保证获取这类问题的全局最优解(除了某些特殊情况,如:寻找极端特征值).由于保持正交约束可行性的计算代价太大,为了避免直接处理非线性约束,人们提出了很

8、多方法,将带约束的优化问题转化成无约束[21,22][19,20]的优化问题求解.这些方法中,最常用的有罚函数方法和增广拉格朗日方法.收稿日期:2015-04-06作者简介:童谣(1991−),女,安徽铜陵人,福州大学数学与计算机科学学院硕士研究生.主要研究方向:优化理论、算法及其应用6湖南理工学院学报(自然科学版)第28卷罚函数方法将正交约束违背作为惩罚项添加到目标函数中,把约束优化问题(3)转化为如下无约束优化问题:T2minF()XX

9、

10、XI

11、

12、,(4)nrFX4其中0为罚