搜索
NONLINEARPROGRAMMINGH.W.KUHNANDA.W.TUCKERPRINCETONUNIVERSITYANDSTANFORDUNIVERSITY1.IntroductionLinearprogrammingdealswithproblemssuchas(see[4],[5]):tomaximizealinearfunctiong(x)_cixiofnrealvariablesxi,...,x,,(formingavectorx)con-strainedbym+nlinearinequalities,fh(X)=_bh-Ia'hiXi_-°,Xi_°,h=1,...,m;i=1,...,n.Thisproblemcanbetransformedasfollowsintoanequivalentsaddlevalue(min-imax)problembyanadaptationofthecalculusmethodcustomarilyappliedtocon-strainingequations[3,pp.199-201].FormtheLagrangianfunction4)(x,u)g(x)+Uhfh(x)-Then,aparticularvectorx°maximnizesg(x)subjecttothem+nconstraintsif,andonlyif,thereissomevectoru°withnonnegativecomponentssuchthat4(x,u°)4(x°,u°)4)(xO,u)forallnonnegativex,u.Suchasaddlepoint(xO,u°)providesasolutionforarelatedzerosumtwopersongame[8],[9],[12].Thebilinearsymmetryof+(x,u)inxanduyieldsthecharac-teristicdualityoflinearprogramming(seesection5,below).Thispaperformulatesnecessaryandsufficientconditionsforasaddlevalueofanydifferentiablefunction4)(x,u)ofnonnegativearguments(insection2)andappliesthem,throughaLagrangian4(x,u),toamaximumforadifferentiablefunctiong(x)constrainedbyinequalitiesinvolvingdifferentiablefunctionsfa(x)mildlyqualified(insection3).Then,itisshown(insection4)thattheaboveequiva-lencebetweenaninequalityconstrainedmaximumforg(x)andasaddlevaluefortheLagrangian+(x,u)holdswheng(x)andthefa(x)aremerelyrequiredtobeconcave(differentiable)functionsfornonnegativex.(Afunctionisconcaveiflinearinterpolationbetweenitsvaluesatanytwopointsofdefinitionyieldsavaluenotgreaterthanitsactualvalueatthepointofinterpolation;suchafunctionisthenegativeofaconvexfunction-whichwouldappearinacorrespondingminimumproblem.)Forexample,g(x)andthef,,(x)canbequadraticpolynomialsinwhichthepurequadratictermsarenegativesemidefinite(asdescribedinsection5).Intermsofactivityanalysis[11],xcanbeinterpretedasanactivityvector,g(x)astheresultingoutputofadesiredcommodity,andthefh(x)asunusedbalancesofprimarycommodities.ThentheLagrangemultipliersucanbeinterpretedasapricevector[13,chap.8]correspondingtoaunitpriceforthedesiredcommodity,andtheLagrangianfunction4)(x,u)asthecombinedworthoftheoutputofthede-siredcommodityandtheunusedbalancesoftheprimarycommodities.TheseThisworkwasdoneundercontractswiththeOfficeofNavalResearch.48I482SECONDBERKELEYSYMPOSIUM:KUHNANDTUCKERpriceinterpretationsseemtorelatecloselytothepricetheoryinthecontemporarypaperofK.J.Arrow[1].Avectormaximum-ofT.C.Koopmans'efficientpointtype[11]-forseveralconcavefunctionsgi(x),...,g,(x)canbetransfonnedintoascalarmaximumforg(x)_V2k(x)bysuitablechoiceofpositiveconstantsv:(asdescribedinsection6).Thesepositiveconstantscanbeinterpretedaspricestobeassigned(forefficientproduction)toseveraldesiredcommoditieswithoutputsgk(X)producedbytheactivityvectorx.Likewise,amaximumformin[gi(x),...,g,(x)]canbetransformedintoamaximumforg(x)-vZgk(x)bysuitablechoiceofnonnegativeconstantsvkwithunitsum(asdescribedinsection7).Suchamaximumofaminimumcomponent,example,istheobjectiveofthefirstplayerinazerosumtwopersongame[12].Modificationsresultingfromchangesinthem+nbasicconstraintsarealsoconsidered(insection8).Throughoutthispaperitisassumedthatthefunctionsoccurringaredifferen-tiable.Butitseemstobeaninterestingconsequenceofthedirectionalderivativepropertiesofgeneralconvex(orconcave)functions[2,pp.18-21]thattheequiva-lencebetweenaninequalityconstrainedmaximumforg(x)andasaddlevaluefortheLagrangian+(x,u)stillholdswhentheassumptionofdifferentiabilityisdropped.Thenproofswouldinvolvetheproperties(oflinearsum,intersection,andpolar)ofgeneralclosedconvexconesratherthanthoseofthepolyhedralconvexcones[71,[14]thatoccurimplicitlyinthispaperthroughhomogeneouslineardifferentialinequalities.However,toassurefinitedirectionalderivativesatboundarypointsoftheorthantofnpnnegativex,oneneedssomemildrequire-ment.Forthispurpose,itiscertainlysufficienttoassumethatthefunctionsareconvex(orconcave)insomeopenregioncontainingtheorthantofnonnegativex.NOTATION.Vectors,denotedusuallybylowercaseromanletters,willbetreatedasonecolumnmatrices,unlesstransposedbyanaccent'intoonerowmatrices.Vectorinequalitiesorequationsstandforsystemsofsuchinequalitiesorequations,oneforeachcomponent.Thusx0meansthatallthecomponentsofthevectorxarenonnegative.Rectangularmatricesandmappingoperatorswillbedenotedbycapitalletters.2.NecessaryandsufficientconditionsforasaddlevalueLet+5(x,u)beadifferentiablefunctionofann-vectorxwithcomponentsxi0andanm-vectoruwithcomponentsuh_0.Takingpartialderivatives,evaluatedataparticularpointx°,u°,let-lj-al0lh~Here00isann-vectorand00anm-vector.SADDLEVALUEPROBLEM.Tofindnonnegativevectorsx°andu°suchthatq(x,u°)_4W(x,u°)_44x0,u)forallx_0,u0.LEMMA1.Theconditions(1)4°O_Ob'x=°'x=ONONLINEARPROGRAMMING483(2)qb:_0,4Vuo=o,uo0arenecessarythatx°,u°provideasolutionforthesaddlevalueproblem.PROOF.Thecomponentsof4),and4)0mustvanishexceptpossiblywhenthecorrespondingcomponentsofx°andu°vanish,inwhichcasetheymustbenon-positiveandnonnegative,respectively.Hence(1)and(2)musthold.LEMMA2.Conditions(1),(2)and(3)4)(x,uO)4(x°,u°)+4)?'(x-xo)(4))(x°