二阶锥规划及其互补问题的光滑算法研究
|
摘要
本文研究二阶锥规划及其互补问题的光滑化算法,为了加快算法的收敛速度,我们提出了新的互补函数,新函数是通过对称扰动CHKS互补函数得到的,在文中证明了新函数具有光滑互补函数的性质,基于此函数给出了二阶锥规划的光滑牛顿算法。该方法所采用的系统等价于二阶锥规划的最优性条件,对初始点的选取没有任何限制,且具有二次收敛速度。
受二阶锥规划等价于求解非线性方程组启发,本文在新的互补函数的基础上,建立了与二阶锥互补问题等价的非线性方程组,使其不仅仅等价于光滑互补函数,并给出了相应的价值函数,使用光滑牛顿法求解时,要求F是连续的P0函数,Φ( z具有强制性,这样保证了水平集有界,从而证明了该算法具有收敛性。数值实验表明该算法是有效的。
In this paper, we study the smoothing methods for second-order cone programming (SOCP) and second-order cone complementarity problem(SOCCP). In order to improving convergence rate, a new smoothing function for the second-order cone programming is given by smoothing the symmetric perturbed CHKS function. Based on this new function, a smoothing Newton method is presented for solving the second-order cone programming. The proposed algorithm solves only one system of equations which is equivalent to the optimization conditions. This algorithm does not have restrictions regarding its starting point and it has quadratic convergence rate.
Based on the new function, SOCP is equivalent to solving nonlinear equations which is extended to SOCCP, so that it is not only equivalent to a smooth complementary function, but transformed into equivalent nonlinear equations, with the assumption that F is P0 function andΦ( z) is coercive function, we prove that the sequence generated by the algorithm remains in some level set and it has a quadratic convergence rate. Numerical results suggest the effectiveness of our algorithm.
受二阶锥规划等价于求解非线性方程组启发,本文在新的互补函数的基础上,建立了与二阶锥互补问题等价的非线性方程组,使其不仅仅等价于光滑互补函数,并给出了相应的价值函数,使用光滑牛顿法求解时,要求F是连续的P0函数,Φ( z具有强制性,这样保证了水平集有界,从而证明了该算法具有收敛性。数值实验表明该算法是有效的。
In this paper, we study the smoothing methods for second-order cone programming (SOCP) and second-order cone complementarity problem(SOCCP). In order to improving convergence rate, a new smoothing function for the second-order cone programming is given by smoothing the symmetric perturbed CHKS function. Based on this new function, a smoothing Newton method is presented for solving the second-order cone programming. The proposed algorithm solves only one system of equations which is equivalent to the optimization conditions. This algorithm does not have restrictions regarding its starting point and it has quadratic convergence rate.
Based on the new function, SOCP is equivalent to solving nonlinear equations which is extended to SOCCP, so that it is not only equivalent to a smooth complementary function, but transformed into equivalent nonlinear equations, with the assumption that F is P0 function andΦ( z) is coercive function, we prove that the sequence generated by the algorithm remains in some level set and it has a quadratic convergence rate. Numerical results suggest the effectiveness of our algorithm.
引文
[1]F.AlizadehDG.Second-orderconeprogramming[J].MathProgram.2003,Ser(B95):3-51.
[2]Y.nesterovAN.InteriorPointPolynomialMethodsinConvexProgramming:TheoryandApplications[J].SIAM.1994.
[3]WitzgallC.Optimallocationofacentralfacility,mathematicalmodelsandconcepts:NationalBureauofStandards[Z].Washington:1964.
[4]J.FaruatAK.Analysisonsymmetriccones[M].1994.
[5]孔令臣.对称锥互补问题的互补函数价值函数研究[D].2007.
[6]F.AlizadehSS.Optimizationwithsemidefinite,quadraticandlinearconstraints[J].TechnicalReport.1997:23-97.
[7]FaybusovichL.Linearsysteminjordanalgebrasandprimal-dualinterior-pointalgorithms[J].JornalofComputationalandApplitiedMathematics.1997,86(1):149-175.
[8]PatakiG.ConeLP,sandSemidefiniteProgrammsandasimplex-typeMethod[Z].1996.
[9]A.NemiroveskiKS.ExtensionofKarmarkar’salgorithmontoconvexquadraticallyconstrainedquadraticprogramming[J].MathProgramming.1996(72):273-289.
[10]Y.E.NesterovMJT.Self-scaledbarriersandinterior-pointmethodsforconvexprogramming[Z].19971-42.
[11]Y.E.NesterovMJT.Primal-dualinteriorpointmethodsforself-scaledcones[J].SIAMJ.Optim.1998(8):324-364.
[12]F.AlizadehJPH.Primal-dualinterior-pointmethodsforsemidefiniteprogramming:Convergencerates,stabilityandnumericalresults[J].SIAMJ.Optim.1998,8(3):746-768.
[13]KanzowCPH.Jacobiansmoothingmethodsfornonlinearcomplementarityproblems[J].SIAMJournalonOptimization.1999(9):342-373.
[14]L.QiAnewlookatsmoothingNewtonmethodsfornonlinearcomplementarityproblemsandboxconstrainedvariationalinequalities[J].MathematicalProgramming.2000(87):1-35.
[15]ChenXQLSD.GlobalandsuperlinearofthesmoothingNewtonmethodsanditsapplicationtogeneralboxconstrainedvariationalinequalities[J].MathematicsofComputation.1998(222):519-540.
[16]XiaoniChiSL.Aone-stepsmoothingNewtonmethodforsecond-orderconeprogramming[J].JournalofComputationalandAppliedMathematics.2007.
[17]CottleRW.Noteonafundamentaltheoreminquadraticprogramming[J].JournaloftheSocictyofIndustrialandAppliedMathematics.1964,12:663-665.
[18]R.W.CottleGBD.Complementarypivottheoryinmathematicalprogramming[M].AmericanMathematicalSociety,1968:115-136.
[19]R.W.CotteGBD.AgeneralizationoftheLinearcomplementarityproblem[J].JournalofCombinationalTheory.1970(8):79-90.
[20]G.B.dantzigRWC.Positive(semi-)definiteprogramming[M].North-Holland,1967:55-73.
[21]R.W.cottleJ-PR.TheLinearComplementarityProblem[M].Boston:AcademicPress,1992.
[22]P.T.harkerJ-P.Finite-dimensionalvariationalinequalityandnonlinearcomplementarityproblems:Asurveyoftheory,algorithmsandapplications[J].MathematicalProgramming.1990(48):161-220.
[23]X.D.chen.ComplementarityfunctionsandnumericalexperimentsonsmoothingNewtonmethodsforsecond-order-conecomplementarityproblems[J].ComputationalOptimizationandApplicationd.2003,25:39-56.
[24]ChenJ-.Theconvexandmonotonefunctionsassociatedwithsecond-ordercone[J].Optimization.2006(55):363-385.
[25]J.S.chenSP.Adescentmethodforsolvingreformulationofthesecond-orderconecomplementarityproblem[J].ComputationalandAppliedMathematics.2007.
[26]ChenJ-.Anewmeritfunctionanditsrelatedpropertiesforthesecond-orderconecomplementarityproblem[J].PacificJournalofOptimization.2006(2):167-179.
[27]ChenJ-.Twoclassesofmeritfunctionsforthesecond-orderconecomplementarityproblem[J].MathematicalMethodsofOperationsResearch.2006(64):495-519.
[28]J.-S.chenXCPT.Analysisofnonsmoothvector-valuedfunctionsassociatedwithsecond-ordercones[J].MathematicalProgramming.2004(101):95-117.
[29]J.-S.chenPT.Anunconstrainedsmoothminimizationreformulationofthesecond-orderconecomplementarityproblem[J].MathematicalProgramming.2005,Ser.B(July14).
[30]M.FukushimaZQLP.Smoothingfunctionsforsecond-orderconecomplementarityproblems[J].SIAMJournalonOptimization.2001(12):436-460.
[31]S.HayashiNYMF.Acombinedsmoothingandregularizationmethodformonotonesecond-orderconecomplementarityproblems[J].SIAMJournalonOptimization.2005(15):593-615.
[32]S.HayashiTYNY.Amatrixsplittingmethodforsymmetricaffinesecond-orderconecomplementarityproblems[J].JournalofCompitationalandAppliedMathematics.2005(175):335-353.
[33]Y.-J.KuoHDM.Interiorpointmethodsforsecond-roderconeprogrammingandORapplications[J].ComputationalOptimizationandApplications.2004(28):255-285.
[34]M.MalikAndS.R.mohan.OnQandR0Propertiesofaquadreticrepresentationinlinearcommplementarityproblemsoverthesecond-ordercone[J].LinearAlgebraanditsApplications.2005,397:85-97.
[35]J.-S.PangDSJS.SemismoothhomeomorphismsandstrongandstabilityofsemidefiniteandLorentzcomplementarityproblems[J].MathematicsofOperationsResearch.2003(28):39-63.
[36]D.SunJS.StrongsemismoothnessoftheFischer-BurmeisterSDCandSOCcomplementarityfunctions[J].MathematicalProgramming.2005,Ser.A(103):575-581.
[37]Y.XiaJMP.Acontinuationmethodforthelinearsecond-orderconecomplementarityproblem[J].ComputationalScienceandItsApplications.2005,3483:290-300.
[38]AlizadehFGD.Second-orderconeprogramming[J].MathProgram.2003(95):3-51.
[39]QiLCX.Agloballyconvergentsuccessiveapproximationmethodfornonsmoothequations[J].SIAMJournalonControlandOptimization.1995(38):402-418.
[40]TsengP.Analysisofnon-iteriorcontinuationmethodbasedonChen-Mangasariansmoothingfunctionsforcomplementarityproblem[M].Boston:KluwerAcademicPublishers,1998.
[41]ChenXYY.Onhomotopy-smoothingmethodsforbox-constrainedvariationalinequalities[J].SIAMJournalonControlandOptimization.1999(37):589-616.
[42]HQ.AregularizedsmoothingNewtonbox-constrainedvariationalinequalityproblemswithP0-functions[J].SIAMJournalonOptimization.2000(10):315-330.
[43]YangYF.SmoothingtrustregionmethodsfornonlinearcomplementarityproblemswithP0-functions[J].AnnalsofOperationsResearch.22004(3):106-127.
[44]HCF.OptimizationandNonsmoothAnalysis[M].NewYork:JohnWiley&Sons,1983:224-256.
[45]LQ.C-differentiablity,C-differentialoperatorsandgeneralizedNewtonmethods[M].Sydney,Australia:TheUniversityofNewSouthWales,1996.
[46]RM.SemismoothandSemiconvexfunctionsinconstrainedoptimization[J].SIAMJournalonControlandOptimization.1997(15):957-972.
[47]L.QiJS.Anon-smoothversionofNewtonmethod[J].MathematicalProgramming.1993(58):353-367.
[48]AF.AspecialNewton-typeoptimizationmethods[J].Optimization.1992(24):269-284.
[49]AF.SolutionofthemonotonecomplementarityproblemwithlocallyLipschitzianfunctions[J].MathProgram.1997,76(5):513-532.
[50]迟晓妮.二次锥规划的内点算法及光滑牛顿法[D].2005.
[51]LiuYongjinZLWY.ConvergencePropertiesofaSmoothingMethodforLinearSecond-orderConeProgramming[J].ADVANCESINMATHIEMATICS.2007,36(4):491-512.
[52]QiL.Convergenceanalysisofsomealgorithmsforsolvingnonsmoothequations[J].Math.1993,Oper(18):227-244.
[53]S.HayashiNYMF.RobustNashequilibriaandsecond-orderconecomplementarityproblems[J].JournalofNonlinearandConvexAnalysis.2005,6(2):283-296.
[54]Y.KannoJACM.Three-dimensionalquasi-staticfrictionalcontactbyusingsecond-orderconelinearcomplementarityproblem:BGEResearchReport[Z].DepartmentofUrbanandEnvironmentalEngineering:KyotoUniversity,2004.
[55]M.Malik.Conecomplementarityproblemswithfinitesolutionsets[J].OperationsResearchLetters.2006(34):121-126.
[56]M.S.GowdaR.someP-propertiesforlineartransformationsonEuclideanJordanalgebras[J].LinearAlgebraanditsApplications.2004(393):203-232.
[57]J.Tao.SomeP-propertiesfornonlineartransformationsonEuclideanJordanalgebras[J].MathematicsofOperationsResearch.2005,30(4):985-1004.
[58]J.Sun.QuadraticconvergenceofasquaredsmoothingNewtonmethodfornonsmoothmatrixequationsanditsapplicationsinsemidefiniteoptimizationproblem:DepartmentofDecisionSciences[Z].NationalUniversityofSingapore:2002.
[59]M.Kojima.AUnifiedApproachtoInterior-PointAlgorithmforLinearComplementarityProblems[C].BerlinGermany:SpingerVerlag,1991.
[60]高雷阜.最优化理论与方法[J].2005.
[61]秦林霞,修乃华.对称锥互补问题的可解性研究[D].2008.
[62]张艳梅,张圣贵.二阶锥规划若干求解方法研究[D].2008.
[63]田悦,张立卫.一类二阶锥规划反问题的光滑函数法[D].2008.
[64]刘勇进,张立卫.线性二阶锥规划的一个光滑化方法及其收敛性[J].2007.
[65]俞昊东,濮定国.解非线性互补问题的非单调信赖域方法[D].2008.
[66]陈为民,杨余飞.求解非线性互补问题的光滑化方法[D].2004.
[2]Y.nesterovAN.InteriorPointPolynomialMethodsinConvexProgramming:TheoryandApplications[J].SIAM.1994.
[3]WitzgallC.Optimallocationofacentralfacility,mathematicalmodelsandconcepts:NationalBureauofStandards[Z].Washington:1964.
[4]J.FaruatAK.Analysisonsymmetriccones[M].1994.
[5]孔令臣.对称锥互补问题的互补函数价值函数研究[D].2007.
[6]F.AlizadehSS.Optimizationwithsemidefinite,quadraticandlinearconstraints[J].TechnicalReport.1997:23-97.
[7]FaybusovichL.Linearsysteminjordanalgebrasandprimal-dualinterior-pointalgorithms[J].JornalofComputationalandApplitiedMathematics.1997,86(1):149-175.
[8]PatakiG.ConeLP,sandSemidefiniteProgrammsandasimplex-typeMethod[Z].1996.
[9]A.NemiroveskiKS.ExtensionofKarmarkar’salgorithmontoconvexquadraticallyconstrainedquadraticprogramming[J].MathProgramming.1996(72):273-289.
[10]Y.E.NesterovMJT.Self-scaledbarriersandinterior-pointmethodsforconvexprogramming[Z].19971-42.
[11]Y.E.NesterovMJT.Primal-dualinteriorpointmethodsforself-scaledcones[J].SIAMJ.Optim.1998(8):324-364.
[12]F.AlizadehJPH.Primal-dualinterior-pointmethodsforsemidefiniteprogramming:Convergencerates,stabilityandnumericalresults[J].SIAMJ.Optim.1998,8(3):746-768.
[13]KanzowCPH.Jacobiansmoothingmethodsfornonlinearcomplementarityproblems[J].SIAMJournalonOptimization.1999(9):342-373.
[14]L.QiAnewlookatsmoothingNewtonmethodsfornonlinearcomplementarityproblemsandboxconstrainedvariationalinequalities[J].MathematicalProgramming.2000(87):1-35.
[15]ChenXQLSD.GlobalandsuperlinearofthesmoothingNewtonmethodsanditsapplicationtogeneralboxconstrainedvariationalinequalities[J].MathematicsofComputation.1998(222):519-540.
[16]XiaoniChiSL.Aone-stepsmoothingNewtonmethodforsecond-orderconeprogramming[J].JournalofComputationalandAppliedMathematics.2007.
[17]CottleRW.Noteonafundamentaltheoreminquadraticprogramming[J].JournaloftheSocictyofIndustrialandAppliedMathematics.1964,12:663-665.
[18]R.W.CottleGBD.Complementarypivottheoryinmathematicalprogramming[M].AmericanMathematicalSociety,1968:115-136.
[19]R.W.CotteGBD.AgeneralizationoftheLinearcomplementarityproblem[J].JournalofCombinationalTheory.1970(8):79-90.
[20]G.B.dantzigRWC.Positive(semi-)definiteprogramming[M].North-Holland,1967:55-73.
[21]R.W.cottleJ-PR.TheLinearComplementarityProblem[M].Boston:AcademicPress,1992.
[22]P.T.harkerJ-P.Finite-dimensionalvariationalinequalityandnonlinearcomplementarityproblems:Asurveyoftheory,algorithmsandapplications[J].MathematicalProgramming.1990(48):161-220.
[23]X.D.chen.ComplementarityfunctionsandnumericalexperimentsonsmoothingNewtonmethodsforsecond-order-conecomplementarityproblems[J].ComputationalOptimizationandApplicationd.2003,25:39-56.
[24]ChenJ-.Theconvexandmonotonefunctionsassociatedwithsecond-ordercone[J].Optimization.2006(55):363-385.
[25]J.S.chenSP.Adescentmethodforsolvingreformulationofthesecond-orderconecomplementarityproblem[J].ComputationalandAppliedMathematics.2007.
[26]ChenJ-.Anewmeritfunctionanditsrelatedpropertiesforthesecond-orderconecomplementarityproblem[J].PacificJournalofOptimization.2006(2):167-179.
[27]ChenJ-.Twoclassesofmeritfunctionsforthesecond-orderconecomplementarityproblem[J].MathematicalMethodsofOperationsResearch.2006(64):495-519.
[28]J.-S.chenXCPT.Analysisofnonsmoothvector-valuedfunctionsassociatedwithsecond-ordercones[J].MathematicalProgramming.2004(101):95-117.
[29]J.-S.chenPT.Anunconstrainedsmoothminimizationreformulationofthesecond-orderconecomplementarityproblem[J].MathematicalProgramming.2005,Ser.B(July14).
[30]M.FukushimaZQLP.Smoothingfunctionsforsecond-orderconecomplementarityproblems[J].SIAMJournalonOptimization.2001(12):436-460.
[31]S.HayashiNYMF.Acombinedsmoothingandregularizationmethodformonotonesecond-orderconecomplementarityproblems[J].SIAMJournalonOptimization.2005(15):593-615.
[32]S.HayashiTYNY.Amatrixsplittingmethodforsymmetricaffinesecond-orderconecomplementarityproblems[J].JournalofCompitationalandAppliedMathematics.2005(175):335-353.
[33]Y.-J.KuoHDM.Interiorpointmethodsforsecond-roderconeprogrammingandORapplications[J].ComputationalOptimizationandApplications.2004(28):255-285.
[34]M.MalikAndS.R.mohan.OnQandR0Propertiesofaquadreticrepresentationinlinearcommplementarityproblemsoverthesecond-ordercone[J].LinearAlgebraanditsApplications.2005,397:85-97.
[35]J.-S.PangDSJS.SemismoothhomeomorphismsandstrongandstabilityofsemidefiniteandLorentzcomplementarityproblems[J].MathematicsofOperationsResearch.2003(28):39-63.
[36]D.SunJS.StrongsemismoothnessoftheFischer-BurmeisterSDCandSOCcomplementarityfunctions[J].MathematicalProgramming.2005,Ser.A(103):575-581.
[37]Y.XiaJMP.Acontinuationmethodforthelinearsecond-orderconecomplementarityproblem[J].ComputationalScienceandItsApplications.2005,3483:290-300.
[38]AlizadehFGD.Second-orderconeprogramming[J].MathProgram.2003(95):3-51.
[39]QiLCX.Agloballyconvergentsuccessiveapproximationmethodfornonsmoothequations[J].SIAMJournalonControlandOptimization.1995(38):402-418.
[40]TsengP.Analysisofnon-iteriorcontinuationmethodbasedonChen-Mangasariansmoothingfunctionsforcomplementarityproblem[M].Boston:KluwerAcademicPublishers,1998.
[41]ChenXYY.Onhomotopy-smoothingmethodsforbox-constrainedvariationalinequalities[J].SIAMJournalonControlandOptimization.1999(37):589-616.
[42]HQ.AregularizedsmoothingNewtonbox-constrainedvariationalinequalityproblemswithP0-functions[J].SIAMJournalonOptimization.2000(10):315-330.
[43]YangYF.SmoothingtrustregionmethodsfornonlinearcomplementarityproblemswithP0-functions[J].AnnalsofOperationsResearch.22004(3):106-127.
[44]HCF.OptimizationandNonsmoothAnalysis[M].NewYork:JohnWiley&Sons,1983:224-256.
[45]LQ.C-differentiablity,C-differentialoperatorsandgeneralizedNewtonmethods[M].Sydney,Australia:TheUniversityofNewSouthWales,1996.
[46]RM.SemismoothandSemiconvexfunctionsinconstrainedoptimization[J].SIAMJournalonControlandOptimization.1997(15):957-972.
[47]L.QiJS.Anon-smoothversionofNewtonmethod[J].MathematicalProgramming.1993(58):353-367.
[48]AF.AspecialNewton-typeoptimizationmethods[J].Optimization.1992(24):269-284.
[49]AF.SolutionofthemonotonecomplementarityproblemwithlocallyLipschitzianfunctions[J].MathProgram.1997,76(5):513-532.
[50]迟晓妮.二次锥规划的内点算法及光滑牛顿法[D].2005.
[51]LiuYongjinZLWY.ConvergencePropertiesofaSmoothingMethodforLinearSecond-orderConeProgramming[J].ADVANCESINMATHIEMATICS.2007,36(4):491-512.
[52]QiL.Convergenceanalysisofsomealgorithmsforsolvingnonsmoothequations[J].Math.1993,Oper(18):227-244.
[53]S.HayashiNYMF.RobustNashequilibriaandsecond-orderconecomplementarityproblems[J].JournalofNonlinearandConvexAnalysis.2005,6(2):283-296.
[54]Y.KannoJACM.Three-dimensionalquasi-staticfrictionalcontactbyusingsecond-orderconelinearcomplementarityproblem:BGEResearchReport[Z].DepartmentofUrbanandEnvironmentalEngineering:KyotoUniversity,2004.
[55]M.Malik.Conecomplementarityproblemswithfinitesolutionsets[J].OperationsResearchLetters.2006(34):121-126.
[56]M.S.GowdaR.someP-propertiesforlineartransformationsonEuclideanJordanalgebras[J].LinearAlgebraanditsApplications.2004(393):203-232.
[57]J.Tao.SomeP-propertiesfornonlineartransformationsonEuclideanJordanalgebras[J].MathematicsofOperationsResearch.2005,30(4):985-1004.
[58]J.Sun.QuadraticconvergenceofasquaredsmoothingNewtonmethodfornonsmoothmatrixequationsanditsapplicationsinsemidefiniteoptimizationproblem:DepartmentofDecisionSciences[Z].NationalUniversityofSingapore:2002.
[59]M.Kojima.AUnifiedApproachtoInterior-PointAlgorithmforLinearComplementarityProblems[C].BerlinGermany:SpingerVerlag,1991.
[60]高雷阜.最优化理论与方法[J].2005.
[61]秦林霞,修乃华.对称锥互补问题的可解性研究[D].2008.
[62]张艳梅,张圣贵.二阶锥规划若干求解方法研究[D].2008.
[63]田悦,张立卫.一类二阶锥规划反问题的光滑函数法[D].2008.
[64]刘勇进,张立卫.线性二阶锥规划的一个光滑化方法及其收敛性[J].2007.
[65]俞昊东,濮定国.解非线性互补问题的非单调信赖域方法[D].2008.
[66]陈为民,杨余飞.求解非线性互补问题的光滑化方法[D].2004.