搜索
1NotesforECNU2007ShortCourseOctober20070.Introduction•Purposeofthecourse:toofferthestudentsaconciseintroductiontomodernunconstrainedandconstrainedoptimizationmethods,algorithms,andcomputersoftware;functionaloptimizationandapplicationswillalsobebrieflyaddressed.•Backgroundmathematicsincludesfirst-yearcalculusandlinearalgebra,someknowledgeofcalculusofvariationsandPDEarehelpfulbutnotcritical.•FamiliaritywithMATLABisimportant.•Mostofthedistributedcoursematerial(Chapters1,2,4,5,7,9,10,12,13,14,16,andAppendixA)arefromthebookAndreasAntoniouandWu-ShengLu,PracticalOptimization:AlgorithmsandEngineeringApplications,Springer,NewYork,March2007.Thebookhasawebsite:~optimization/I.NumericalOptimizationandApplications1.1UnconstrainedOptimization(Chaps.1,2,4,5,7,9)•Basicoptimizationproblem:mimimize()fornfR∈xx•Assumption:f(x)istwicecontinuouslydifferentiable.•Anexample:solveasystemofalgebraicequationspi(x)=0fori=1,2,…,m.•Basicstructureofanumericalalgorithmforminimizingf(x)Step1:chooseaninitialpointx0,setaconvergencetoleranceε,andsetacounterk=0.Step2:determineasearchdirectiondkforreducingf(x)frompointxk.Step3:determineastepsizekαsuchthat()kkfα+xdisminimizedfor0α≥,andconstruct1kkkkα+=+xxdStep4:ifkkαεd,stopandoutputasolutionxk+1,elsesetk:=k+1andrepeatfromStep2.•Comments:(a)Steps2and3arekeystepsofanoptimizationalgorithm.(b)DifferentwaystoaccomplishStep2leadstodifferentalgorithms(c)Step3isaone-dimensionaloptimizationproblemanditisoftencalledalinesearchstep.•Notationandbasicquantities:x:vectorofnvariablesincolumnf(x):objectivefunctiong(x):gradient(vector)off(x).Apopularnotationforg(x):g(x)=()f∇xH(x):Hessian(matrix)off(x).ApopularnotationforH(x):H(x)=2()f∇xNote:H(x)isasquare,symmetricmatrixandcanbeobtainedasH(x)=(())Tf∇∇xApointxiscalledastationarypointifg(x)=0.•First-ordernecessarycondition:Ifx*isaminimumpoint(minimizer),then()f∗∇=0x.Inotherwords,ifx*isaminimumpoint,thenitmustbeastationarypoint.•Second-ordernecessarycondition:Ifx*isaminimumpoint(minimizer),thenH(x*)isapositivesemidefinitematrix,i.e.,H(x*)0;.•Second-ordersufficientcondition:If()f∗∇=0xandH(x*)isapositivedefinitematrix,i.e.,H(x*)0;,thenx*isaminimumpoint(minimizer).•One-dimensional(1-D)optimization(linesearch)♦Popular1-DmethodsforunimodalfunctionsincludeDichotomoussearch,Fibonaccisearch,Golden-sectionsearch,quadraticinterpolationmethod,andcubicinterpolationmethod.2(weillustratethebasicideasbehindtheDichotomoussearch,Golden-sectionsearch,andquadraticinterpolationmethods.)♦1-Doptimizationforgeneralsmoothfunctions:theinexactlinesearchmethodbyRogerFletcher.Matlabcodesimplementingthesesearchmethodsareavailablefordownloadat~optimization/•Determinationofasearchdirectiondk:♦Basisofthemethods:Taylorseriesoff(x)inasmallvicinitysurroundingpointxk:()321()()()()2TTkkkkffffO+=+∇⋅+⋅∇⋅+xxxxδδδδδor()31()()()()2TTkkkkffO+=+⋅+⋅⋅+xxgxHxδδδδδ♦Steepestdescentmethod:dk=()kf−∇x,i.e.,dk=–g(xk)□Remarks:(i)Theconceptofadescentalgorithm1()()for0,1,......kkffk+≤=xx(ii)Thesteepestdescentalgorithmisadescentalgorithm.(iii)Thesteepestdescentalgorithmisusuallyquiteslow.♦Newtonmethod:dk=1()()kk−−Hxgx□Remarks:(i)ifH(xk)=Hkispositivedefiniteforallxk,thentheNewtonalgorithmisadescentalgorithm.(ii)ifHkisnotpositivedefinite,thenthesearchdirectioninNewtonmethodismodifiedto1ˆkkk−=−dHgwhereˆ1kkββ+=+HIHwithaβsuchthatkβ+0;HITheNewtonmethodwithsuchmodificationsisadescentalgorithm.(iii)TypicallyNewtonalgorithmconvergesconsiderablyfasterthanthesteepestdescentalgorithmatacostofincreasedcomputationalintensity.♦Quasi-Newtonmethods:onecantakeaunifyinglookattheabovetwomethodsasdk=–Skgkwhere1forsteepestdescentforNewtonkk−⎧=⎨⎩ISH□Quasi-Newtonmethodsusegradientinformationtogeneratesuccessivelow-rankestimationoftheinverseHessianmatrix.Inthisway,quasi-NewtonalgorithmsprovideconvergentratescomparablewiththatofNewtonalgorithmwithreducedcomplexity.□Notation:11,kkkkkk++=−=−xxggδγ□RequirementsforSk:(i)Symmetricandpositivedefinite,(ii)1kkk+=Sγδ□Davidon-Fletcher-Powell(DFP)updatingformula:S0=I,and1TTkkkkkkkkTTkkkkk+=+−SSSSSδδγγδγγγ□Broyden-Fletcher-Goldfarb-Shanno(BFGS)updatingformula:S0=I,and11TTTTkkkkkkkkkkkkkTTTkkkkkk+⎛⎞+=++−⎜⎟⎝⎠SSSSSγγδδδγγδγδγδγδ31.2ConstrainedOptimization:TheKarush-Kuhn-Tucker(KKT)Conditions(Chap.10)•Theconstrainedoptimizationproblemminimize()subjectto:()0for1,2,...,()0for1,2,...,ijfaipcjq==≥=xxx•Feasibleregion:{:()0for1,2,...,,and()0for1,2,...,}ijaipcjq==≥=xxx•Apointxissaidtobefeasibleifitisinthefeasibleregion(insideorontheboundary).Wesayaninequalityconstraintcj(x)≥0isactiveatafeasiblepointx,ifcj(x)=0.Andinequalityconstraintcj(x)≥0issaidtobeinactiveatafeasiblepointxifcj(x)0.•KKTconditions(first-ordernecessaryconditionsforpointx*tobeaminimumpoint):Ifx*isalocalminimizeroftheconstrainedproblem,then(a)()0for1,2,...,iaip∗==x(b)()0for1,2,...,jcjq∗≥=x(c)thereexistLagrangemultipliersfor1andfor1ijipjqλμ∗∗≤≤≤≤suchthat11()()()pqiijiijfacλμ∗∗∗∗∗===+∑∑xxx∇∇∇(d)()0for1,2,...,jjcjqμ∗∗==x(e)0for1,2,...,jjqμ∗≥=Remarks:♦Conditions(a)and(b)aremerelytheconstraintsimposedintheproblem.