资源描述:
《一类约束最小二乘问题的算法》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、-南京航空航天大学硕士学位论文摘要最小二乘问题在物理、统计、控制论和经济等研究领域中有着广泛的应用,是最优化问题理论和算法的重要组成部分.然而在许多实际问题中,目标函数中的变量的各分量之间可能不完全独立,它们的数值常受到某些物理或数学条件的约束,经常会遇到约束最小二乘问题.因此,研究这类问题的计算方法是非常有意义的.本文研究了凸多面体上的最小二乘问题的数值解法.首先利用Kuhn-Tucker条件将具有非负约束变量的凸多面体上的最小二乘问题转化成为线性互补问题.在此基础上,设计了求解此类约束最小二乘问题的辅助算法,证明了算法的收敛性,并说明了子问题的解法.其次,针对一
2、般凸多面体上的最小二乘问题,本文推导了它的对偶问题,证明了相应的弱对偶定理和强对偶定理,利用对偶问题同样将其转化为了线性互补问题.据此,本文设计了两种求解一般凸多面体上的最小二乘问题的投影算法,证明了算法的收敛性和收敛速率.最后,数值实验表明本文所提出的算法是可行的.关键词:约束最小二乘问题,互补问题,K-T条件,辅助方法,不动点算法,对偶问题,投影法I---一类约束最小二乘问题的算法AbstractTheleast-squaresproblemhasawiderangeofapplicationsinphysics,statisticscyberneticsand
3、economicsandisanimportantcomponentoftheoptimizationtheoryandthealgorithm.Butinmanypracticalproblems,eachcomponentofthevariablewhichintheobjectivefunctionsisprobablynotabsoluteindependence.Soweoftenmetconstrainedleastsquaresproblems.Asaresult,it’sverysignificanttostudythealgorithmofthis
4、kindofproblem.Inthisthesis,westudytheleastsquaresproblemwhichisdefinedonaPolyhedron.First,wetransformtheleastsquaresproblemdefinedonthePolyhedronwhichhasnon-negativeconstraintsintoalinearcomplementarityproblemaccordingtotheKuhn-Tuckerconditions.Onthisbasis,wedesigntheauxiliaryalgorithm
5、tosolvethiskindofconstrainedleastsquaresproblem.Thenwealsoprovetheconvergenceofthealgorithmandillustratethesolutionofthechildproblem.Second,fortheleastsquaresproblemdefinedonthegeneralPolyhedron,wederiveitsdualproblem,provethecorrespondingweakdualitytheoremandthestrongdualitytheoremand
6、thentransformittothelinearcomplememtarityproblembyusingdualproblem.Accordingly,wedesigntwoprojectionalgorithmstosolvetheleastsquaresproblemonthegeneralconvexpolyhedronandprovetheconvergenceandtheconvergencerateofthealgorithm.Finally,thenumericalexperimentsshowthattheproposedalgotithmis
7、feasible.Keywords:constrainedleast-squaresproblem,complementarityproblem,Kuhn-Tuckerconditions,fixedpointmethod,auxiliarymethod,projectionalgorithmII---一类约束最小二乘问题的算法图表清单图4.1算法2.1.1求解时目标函数q(x)值迭代曲线图(算例4.1).............................................……20图4.2算法3.2.1求解时目标函数q(x)值迭代曲线图(算例