非线性优化对偶原理及灵敏度分析

NonlinearOptimization:DualityINSEAD,S[e-mail]c2006Jean-PhilippeVert,([e-mail])–p.1/67OutlineTheLagrangedualfunctionWeakandstrongdualityGeometricinterpretationSaddle-pointinterpretationOptimalityconditionsPerturbationandsensitivityanalysisNonlinearoptimizationc2006Jean-PhilippeVert,([e-mail])–p.2/67TheLagrangedualfunctionNonlinearoptimizationc2006Jean-PhilippeVert,([e-mail])–p.3/67SettingWeconsideranequalityandinequalityconstrainedoptimizationproblem:minimizef(x)subjecttohi(x)=0,i=1,...,m,gj(x)≤0,j=1,...,r,makingnoassumptionoff,gandh.Wedenotebyf∗theoptimalvalueofthedecisionfunctionundertheconstraints,i.e.,f∗=f(x∗)iftheminimumisreachedataglobalminimumx∗.Nonlinearoptimizationc2006Jean-PhilippeVert,([e-mail])–p.4/67LagrangedualfunctionRemembertheLagrangianofthisproblemisthefunctionL:Rn×Rm×Rr→Rdefinedby:L(x,λ,μ)=f(x)+mXi=1λihi(x)+rXj=1μjgj(x).WedefinetheLagrangedualfunctiong:Rm×Rr→Ras:q(λ,μ)=infx∈RnL(x,λ,μ)=infx∈Rnf(x)+mXi=1λihi(x)+rXj=1μjgj(x).Nonlinearoptimizationc2006Jean-PhilippeVert,([e-mail])–p.5/67PropertiesofthedualfunctionWhenLinunboundedbelowinx,thedualfunctionq(λ,μ)takesonthevalue−∞.Ithastwoimportantproperties:1.qisconcavein(λ,μ),eveniftheoriginalproblemisnotconvex.2.Thedualfunctionyieldslowerboundsontheoptimalvaluef∗oftheoriginalproblemwhenμisnonnegative:q(λ,μ)≤f∗,∀λ∈Rm,∀μ∈Rr,μ≥0.Nonlinearoptimizationc2006Jean-PhilippeVert,([e-mail])–p.6/67Proof1.Foreachx,thefunction(λ,μ)7→L(x,λ,μ)islinear,andthereforebothconvexandconcavein(λ,μ).Thepointwiseminimumofconcavefunctionsisconcave,thereforeqisconcave.2.Let¯xbeanyfeasiblepoint,i.e.,h(¯x)=0andg(¯x)≤0.Thenwehave,foranyλandμ≥0:mXi=1λihi(¯x)+rXi=1μihi(¯x)≤0,=⇒L(¯x,λ,μ)=f(¯x)+mXi=1λihi(¯x)+rXi=1μihi(¯x)≤f(¯x),=⇒q(λ,μ)=infxL(x,λ,μ)≤L(¯x,λ,μ)≤f(¯x),∀¯x.Nonlinearoptimizationc2006Jean-PhilippeVert,([e-mail])–p.7/67ProofcomplementWeusedthefactthatthepoinwisemaximum(resp.minimum)ofconvex(resp.concave)functionsisitselfconvex(concave).Toprovethis,supposethatforeachy∈Athefunctionf(x,y)isconvexinx,andletthefunction:g(x)=supy∈Af(x,y).Thenthedomainofgisconvexasanintersectionofconvexdomains,andforanyθ∈[0,1]andx1,x2inthedomainofg:g(θx1+(1−θ)x2)=supy∈Af(θx1+(1−θ)x2,y)≤supy∈A(θf(x1,y)+(1−θ)f(x2,y))≤supy∈A(θf(x1,y))+supy∈A((1−θ)f(x2,y))=θg(x1)+(1−θ)g(x2).Nonlinearoptimizationc2006Jean-PhilippeVert,([e-mail])–p.8/67IllustrationNonlinearoptimizationc2006Jean-PhilippeVert,([e-mail])–p.9/67Example1Least-squaressolutionoflinearequations:minimizexxsubjecttoAx=b,whereA∈Rp×n.Therearepequalityconstraints,theLagrangianwithdomainRn×Rpis:L(x,λ)=xx+λ(Ax−b).TominimizeLoverxforλfixed,wesetthegradientequaltozero:∇xL(x,λ)=2x+Aλ=0=⇒x=−12Aλ.Nonlinearoptimizationc2006Jean-PhilippeVert,([e-mail])–p.10/67Example1(cont.)PlugitinLtoobtainthedualfunction:q(λ)=L−12Aλ,λ=−14λAAλ−bλqisaconcavefunctionofλ,andthefollowinglowerboundholds:f∗≥−14λAAλ−bλ,∀λ∈Rp.Nonlinearoptimizationc2006Jean-PhilippeVert,([e-mail])–p.11/67Example2StandardformLP:minimizecxsubjecttoAx=b,x≥0.whereA∈Rp×n.Therearepequalityandninequalityconstraints,theLagrangianwithdomainRn×Rp×Rnis:L(x,λ,μ)=cx+λ(Ax−b)−μx=−λb+c+Aλ−μx.Nonlinearoptimizationc2006Jean-PhilippeVert,([e-mail])–p.12/67Example2(cont.)Lislinearinx,anditsminimumcanonlybe0or−∞:g(λ,μ)=infx∈RnL(x,λ,μ)=(−λbifAλ−μ+c=0−∞otherwise.gislinearonanaffinesubspaceandthereforeconcave.Thelowerboundisnon-trivialwhenλandμsatisfyμ≥0andAλ−μ+c=0,givingthefollowingbound:f∗≥−λbifAλ+c≥0.Nonlinearoptimizationc2006Jean-PhilippeVert,([e-mail])–p.13/67Example3InequalityformLP:minimizecxsubjecttoAx≤b,whereA∈Rp×n.Therearepinequalityconstraints,theLagrangianwithdomainRn×Rpis:L(x,μ)=cx+μ(Ax−b)=−μb+Aμ+cx.Nonlinearoptimizationc2006Jean-PhilippeVert,([e-mail])–p.14/67Example3(cont.)Lislinearinx,anditsminimumcanonlybe0or−∞:g(λ,μ)=infx∈RnL(x,λ,μ)=(−μbifAμ+c=0−∞otherwise.gislinearonanaffinesubspaceandthereforeconcave.Thelowerboundisnon-trivialwhenμsatisfiesμ≥0andAμ+c=0,givingthefollowingbound:f∗≥−μbifAμ+c=0andμ≥0.Nonlinearoptimizationc2006Jean-PhilippeVert,([e-mail])–p.15/67Example4Two-waypartitioning:minimizexWxsubjecttox2i=1,i=1,...,n.Thisisanonconvexproblem,thefeasiblesetcontains2ndiscretepoints(xi=±1).Interpretation:partition(1,...,n)intwosets,Wijisthecostofassigningi,jtothesameset,−Wijthecostofassigningthemtodifferentsets.LagrangianwithdomainRn×Rn:L(x,λ)=xWx+nXi=1λix2i−1
=x(W+diag(λ))x−1λ.Nonlinearoptimizationc2006Jean-PhilippeVert,([e-mail])–p.16/67Example4(cont.)ForMsymmetric,theminimumofxMxis0ifalleigenvaluesofMarenonnegative,−∞otherwise.Wethereforegetthefollowingdualfunction:q(λ)=(−1λifW+diag(λ)0,−∞otherwise.Thelowerboundisnon-trivialforλsuchthatW+diag(λ)0.Thi