Penaltybarrier multiplier methods for convex progr

Penalty/BarrierMultiplierMethodsforConvexProgrammingProblemsAharonBen-Tal1andMichaelZibulevsky2FacultyofIndustrialEngineeringandManagementTechnion|IsraelInstituteofTechnologyHaifa32000,IsraelRevisedversion|March1995AbstractWestudyaclassofmethodsforsolvingconvexprograms,whicharebasedonnonquadraticAugmentedLagrangiansforwhichthepenaltyparametersarefunc-tionsofthemultipliers.Thisgivesrisetolagrangianswhicharenonlinearinthemultipliers.Eachaugmentedlagrangianisspeciedbyachoiceofapenaltyfunction’andapenalty-updatingfunction.Therequirementson’aremild,andallowfortheinclusionofmostofthepreviouslysuggestedaugmentedlagrangians.Moreim-portantly,anewtypeofpenalty/barrierfunction(havingalogarithmicbranchgluedtoaquadraticbranch)isintroducedandusedtoconstructanecientalgorithm.Convergenceofthealgorithmsisprovedforthecaseofbeingasublinearfunc-tionofthedualmultipliers.Thealgorithmsaretestedonlarge-scalequadraticallyconstrainedproblemsarisinginstructuraloptimization.1ResearchsupportedbyagrantfromtheIsrael-U.S.A.BinationalScienceFoundation(BSF).2ResearchsupportedbyTheCenterforAbsorptioninScience,MinistryofImmigrantAbsorp-tion,StateofIsrael1IntroductionMethodsofmultipliersforconstrainedconvexprograms,involvingnonquadraticaugmentedLagrangiansaregettingrenewedattention.Newtheoreticalresultsaregivenforashiftedlogarithmicmultipliermethodin[12]and[13].Amoregeneralschemeisstudiedin[9].Implementationsreportinggoodnumericalresultsaregivenin[3]and[7].Fortheexponentialmethodofmultipliersnewconvergenceresults,includingrateofconvergence(forthelinearprogrammingcase)areobtainedin[18].HereweintroduceaclassofmethodscalledPenaltyBarrierMultiplier(PBM)methods,whicharebasedonnonquadraticaugmentedlagrangians.AmemberinthePBMclassisspeciedbyapenalty/barrierfunction’andapenaltyupdatingfunction,responsibleforupdatingthepenaltyparametersineachiteration.Therequirementson’arerathermild,andallowfortheinclusionasspecialcases,theexponentialandtheshiftedlogarithmicfunctions.Moreimportantly,inx4wesug-gestanewtypeofpenalty/barrierfunctionmadeofalogarithmicbranchgluedsmoothlytoaquadraticbranch.APBMalgorithmbasedonthislog-quadraticaugmentedlagrangianprovedtobeveryecientandcapableofsolvinglarge-scaleproblemstoahighdegreeofaccuracy(seex7,x8).Therequirementonthepenaltyupdatingfunctionisthatitisasublinearfunctionofthemultipliers.Thisre-quirementwasinspiredbyasuggestioninthepaperbyTsengandBertsekas[18].Wepointoutthatanaugmentedlagrangianresultingfromsuchachoiceofisanonlinearfunctionofthemultipliers.Inx4weshowthatthePBMmethodisassociatedwitha\proximalpointalgorithm,whichsimultaneouslysolvesthedualconvexprogrammingproblem.Thedistance-likefunctionappearingintheproxi-maltermisrelatedtotheconjugatefunctionof’.Convergencepropertiesoftheproximalpointalgorithmisstudiedinx5,andtheresultsobtainedthereareinstru-mentalinprovingthatthePBMalgorithmproducesasequenceofpointswhichareasymptoticallyprimalfeasible.FullconvergenceanalysisofthePBMmethodiscon-tainedinx6.Itisshown(seeTheorem1)thattheprimal-dualsequencesgeneratedbythealgorithmarebounded,andeachoftheirlimitpointsisapairofsolutionsfortheprimalanddualproblems.Inx7wediscussimplementationissuesofthePBMmethodandinx8weapplythealgorithmtolarge-scalequadraticallycon-strainedconvexproblemswhichariseintwotypesofstructuraloptimization|(1)TrussTopologyDesignand(2)ShapeDesign.Fortherstapplication,thelargestproblemsolvedhas462variablesand16290quadraticconstraints.Forthesecondapplication,thelargestproblemsolvedhas6498variablesand3136quadraticcon-straints.Thecomputationalresults3demonstratethatthePBMmethodsolvessuchproblemsinalmostaxednumberofNewtonsteps(typically30)independentlyoftheproblemsdimensions.3AdditionalcomputationalresultsfortheTrussTopologyDesignproblemwerereportedinanearlierversionofthispaper,see[3].12ProblemFormulationandAssumptionsWestudytheordinaryconvexprogrammingproblem(inthesenseofRockafellar[14,p.277])(P)f=infff(x):gi(x)0;i=1;:::;mgwherethefunctionsf,gi:::;gm:IRn!Rareclosedproperconvexfunctions.WeletSdenotethefeasiblesetofPandSthesetofoptimalsolutions.Itisassumedthroughoutthepaperthat(A1)Sisnonemptyandcompact.Associatedwithproblem(P)isitsLagrangianL(x;u):=f(x)+mXi=1uigi(x);itsdualfunctionG(u):=inffL(x;u):x2IRngandthedualconcaveproblem(D)G=supfG(u):u0g.OursecondworkingassumptionisSlater’scondition:(A2)exists^x2domfsuchthatgi(^x)0;i=1;:::;m:Followingthisassumption,itiswellknownthattheoptimalsolutionsetofthedualproblem(D)isnonemptyandcompact,andthatf=G.Moreover,foreach0G,thelevelsetfu2IRm:u0;G(u)0giscompact.Notethatwedonotassumedierentiabilityofthefunctionsf;g1;:::;gm.3ThePenalty/BarrierMultiplier(PBM)MethodWetransformtheconstraintsofproblem(P)usingareal-valuedfunction’havingthefollowingproperties(’0)’isastrictlyincreasingtwicedierentiablestrictlyconvexfunctionwithdom’=(1;b);0b12(’1)’(0)=0(’2)’0(0)=1(’3)limt!b’0(t)=1(’4)limt!1’0(t)=0(’5)’00(t)1Mforallt2[0;b],forsomeM0.Wenextshowthatproperties(’1){(’4)implyanimportantpropertyoftherecessionfunction’1of’.Recall[14,x8]that’1(s):=lim!1’(t+s)’(t