introduction to non-linear optimization

《introduction to non-linear optimization》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Introductiontonon-linearoptimizationRossA.LippertD.E.ShawResearchFebruary25,2008R.A.LippertNon-linearoptimizationOptimizationproblemsproblem:Letf:Rn!(1;1],ndminff(x)gx2Rnndxs.t.f(x)=minff(x)gx2RnQuitegeneral,butsomecases,likefconvex,arefairlysolvable.Today’sproblem:Howaboutf:Rn!R,smooth?

2、ndxs.t.rf(x)=0Wehaveareasonableshotatthisiffistwicedifferentiable.R.A.LippertNon-linearoptimizationTwopillarsofsmoothmultivariateoptimizationn-Doptimizationlinearsolve/quadraticopt.1DoptimizationR.A.LippertNon-linearoptimizationThesimplestexamplewecangetQuadraticoptimization:f(x)=cxtb+1xtAx

3、.2verycommon(actuallyuniversal,morelater)Findingrf(x)=0rf(x)=bAx=0x=A1bAhastobeinvertible(really,binrangeofA).Isthisallweneed?R.A.LippertNon-linearoptimizationMax,min,saddle,orwhat?RequireAbepositivedenite,why?302.5−0.52−11.5−1.51−20.5−2.50−3110.510.510.50.50000−0.5−0.5−0.5−0.5−1−1−1−1110.

4、50.800.6−0.50.4−10.2−1.5−20110.510.510.50.50000−0.5−0.5−0.5−0.5−1−1−1−1R.A.LippertNon-linearoptimizationUniversalityoflinearalgebrainoptimizationt1tf(x)=cxb+xAx2Linearsolve:x=A1b.Evenfornon-linearproblems:ifoptimalxnearourxt1tf(x)f(x)+(xx)rf(x)+(xx)rrf(x)(xx)+


21
x=xx(rrf(x)

5、)rf(x)Optimization$LinearsolveR.A.LippertNon-linearoptimizationLinearsolvex=A1bButreallywejustwanttosolveAx=bDon’tformA1ifyoucanavoidit.(Don’tformAifyoucanavoidthat!)ForageneralA,therearethreeimportantspecialcases,01a100diagonal:A=@0a0Athusx=1b2iaii00a3orthogonalAtA=I,thusA1=Atandx=Atb01a11

6、00Ptriangular:A=@aa0A,x=1bax2122iaiiijiR.A.LippertNon-linearoptimizationDirectmeth

7、odsAissymmetricpositivedenite.Eigenvaluefactorization:A=QDQt;whereQisorthogonalandDisdiagonal.Then
x=QD1Qtb:MoreexpensivethanChoeskyDirectmethodsareusuallyquiteexpensive(O(n3)work).R.A.LippertNon-linearoptimizationIterativemethodba