序列二次规划

二次规划QuadraticProgramming二次规划Questions什么是二次规划？如何求解？二次规划Definition二次规划（*）二次规划二次规划Remark二次规划等式约束二次规划问题的解法：♥直接消去法(DirectEliminationMethod)♥Lagrange乘子法直接消去法(DirectEliminationMethod)直接消去法直接消去法直接消去法(**)直接消去法直接消去法直接消去法Remark直接消去法Example直接消去法Solution直接消去法直接消去法直接消去法RemarkLagrange乘子法Lagrange乘子法Lagrange乘子法Lagrange乘子法Lagrange乘子法把c和b代入前面的最优解然后利用HR即可得。Lagrange乘子法ExampleLagrange乘子法SolutionLagrange乘子法Lagrange乘子法起作用集方法（ActiveSetMethod)起作用集方法正定二次规划（*）定理起作用集方法Theorem起作用集方法Theorem(***)起作用集方法Proof起作用集方法（a）起作用集方法(b)满足（a)的肯定满足（b），且为满足（b）的的一部分，但满足（b）的解是唯一的，所以问题（b）的解就是问题（a)的解。*x*x起作用集方法Remark起作用集方法Questions起作用集方法起作用集方法(****)起作用集方法起作用集方法(*****)起作用集方法起作用集方法起作用集方法起作用集方法Questions如何得到(*******)？起作用集方法Answer起作用集方法Questions起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法AlgorithmAlgorithmAlgorithmAlgorithm起作用集方法起作用集方法起作用集方法起作用集方法Example起作用集方法Solution起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法起作用集方法序列二次规划法（SequentialQuadraticProgramming)（约束拟牛顿法约束变尺度法）序列二次规划法序列二次规划法序列二次规划法序列二次规划法牛顿法求方程组的解牛顿法求方程组的解牛顿法求方程组的解牛顿法求方程组的解牛顿法求方程组的解牛顿法求方程组的解牛顿法求方程组的解牛顿法求方程组的解牛顿法求方程组的解牛顿法求方程组的解牛顿法求方程组的解牛顿法求方程组的解牛顿法求方程组的解序列二次规划法序列二次规划法序列二次规划法Remark序列二次规划法Remark序列二次规划法Example序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法用信赖域方法求解二次规划子问题：序列二次规划法序列二次规划法序列二次规划法(**)序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法序列二次规划法(1)GeneralProblem(GP)序列二次规划法Inconstrainedoptimization,thegeneralaimistotransformtheproblemintoaneasiersub-problemthatcanthenbesolvedandusedasthebasisofaniterativeprocess.序列二次规划法Acharacteristicofalargeclassofearlymethodsisthetranslationoftheconstrainedproblemtoabasicunconstrainedproblembyusingapenaltyfunctionforconstraintsthatarenearorbeyondtheconstraintboundary.Inthiswaytheconstrainedproblemissolvedusingasequenceofparameterizedunconstrainedoptimizations,whichinthelimit(ofthesequence)convergetotheconstrainedproblem.序列二次规划法ThesemethodsarenowconsideredrelativelyinefficientandhavebeenreplacedbymethodsthathavefocusedonthesolutionoftheKuhn-Tucker(KT)equations.TheKTequationsarenecessaryconditionsforoptimalityforaconstrainedoptimizationproblem.序列二次规划法Iftheproblemisaso-calledconvexprogrammingproblem,thentheKTequationsarebothnecessaryandsufficientforaglobalsolutionpoint.序列二次规划法ReferringtoGP(1),theKuhn-Tuckerequationscanbestatedas(2)序列二次规划法Thefirstequationdescribesacancelingofthegradientsbetweentheobjectivefunctionandtheactiveconstraintsatthesolutionpoint.Forthegradientstobecanceled,Lagrangemultipliersarenecessarytobalancethedeviationsinmagnitudeoftheobjectivefunctionandconstraintgradients.序列二次规划法Becauseonlyactiveconstraintsareincludedinthiscancelingoperation,constraintsthatarenotactivemustnotbeincludedinthisoperationandsoaregivenLagrangemultipliersequaltozero.ThisisstatedimplicitlyinthelasttwoequationsofEq.(2).序列二次规划法ThesolutionoftheKTequationsformstheBasistomanynonlinearprogrammingalgorithms.ThesealgorithmsattempttocomputetheLagrangemultipliersdirectly.Constrainedquasi-Newtonmethodsguaranteesuper-linearconvergencebyaccumulatingsecondorderinformationregardingtheKTequationsusingaquasi-Newtonupdatingprocedure.序列二次规划法ThesemethodsarecommonlyreferredtoasSequentialQuadraticProgramming(SQP)methods,sinceaQPsub-problemissolvedateachmajoriteration(alsoknownasIterativeQuadraticProgramming,RecursiveQuadraticProgramming,andConstrainedVariableMetricmethods).序列二次规划法SequentialQuadraticProgramming(SQP)AQuadraticProgramming(QP)SubproblemSQPImplementation序列二次规划法SequentialQuadraticProgramming(SQP)AQuadraticProgramming(QP)SubproblemSQPImplementation序列二次规划法SequentialQuadraticProgramming(SQP)SQPmethodsrepresentthestateoftheartinnonlinearprogrammingmethods.Schittkowski,forexample,hasimplementedandtestedaversionthatoutperformseveryothertestedmethodintermsofefficiency,accuracy,andpercentageofsuccessfulsolutions,overalargenumberoftestproblems.序列二次规划法BasedontheworkofBiggs,Han,andPowell,themethodallowsyoutocloselymimicNewton'smethodforconstrainedoptimizationjustasisdoneforunconstrainedoptimization.Ateachmajoriteration,anapproximationismadeoftheHessianoftheLagrangianfunctionusingaquasi-Newtonupdatingmethod.序列二次规划法ThisisthenusedtogenerateaQPsub-problemwhosesolutionisusedtoformasearchdirectionforalinesearchprocedure.Thegeneralmethod,however,isstatedhere.序列二次规划法GiventheproblemdescriptioninGP(1)theprincipalideaistheformulationofaQPsub-problembasedonaquadraticapproximationoftheLagrangianfunction.序列二次规划法HereyousimplifyEq.(1)byassumingthatboundconstraintshavebeenexpressedasinequalityconstraints.YouobtaintheQPsub-problembylinearizingthenonlinearconstraints.序列二次规划法SequentialQuadraticProgramming(SQP)AQuadraticProgramming(QP)SubproblemSQPImplementation序列二次规划法序列二次规划法Thissub-problemcanbesolvedusinganyQPalgorithm.Thesolutionisusedtoformanewiterate.序列二次规划法Thesteplengthparameterkisdeterminedbyanappropriatelinesearchproceduresothatasufficientdecreaseinameritfunctionisobtained.序列二次规划法ThematrixkHisapositivedefiniteapproximationoftheHessianmatrixoftheLagrangianfunction.kHcanbeupdatedbyanyofthequasi-Newtonmethods,althoughtheBFGSmethodappearstobethemostpopular.序列二次规划法Anonlinearlyconstrainedproblemcanoftenbesolvedinfewerit