in Convex Optimization

WorkingPaperConstraintAggregationPrincipleinConvexOptimizationYuriM.ErmolievArkadiiV.KryazhimskiiAndrzejRuszczynskiWP-95-015February1995(revisedSeptember1995)IIASAInternationalInstituteforAppliedSystemsAnalysisA-2361LaxenburgAustriaTelephone:432236807Fax:[phone]E-Mail:[e-mail]zynskiWP-95-015February1995(revisedSeptember1995)WorkingPapersareinterimreportsonworkoftheInternationalInstituteforAppliedSystemsAnalysisandhavereceivedonlylimitedreview.ViewsoropinionsexpressedhereindonotnecessarilyrepresentthoseoftheInstitute,itsNationalMemberOrganizations,orotherorganizationssupportingthework.IIASAInternationalInstituteforAppliedSystemsAnalysisA-2361LaxenburgAustriaTelephone:432236807Fax:[phone]E-Mail:[e-mail]aintaggregationtechniqueisproposedforconvexoptimizationprob-lems.Ateachiterationasetofconvexinequalitiesandlinearequationsisreplacedbyasinglesurrogateinequalityformedasalinearcombinationoftheoriginalconstraints.Aftersolvingthesimpliedsubproblem,newaggregationcoecientsarecalculatedandtheiterationcontinues.Thisgeneralaggregationprincipleisincorporatedintoanumberofspecicalgorithms.Convergenceofthenewmethodsisprovedandspeedofconver-genceanalyzed.Next,dualinterpretationofthemethodisprovidedandapplicationtodecomposableproblemsisdiscussed.Finally,numericalillustrationisgiven.Keywords:Nonsmoothoptimization,surrogateconstraints,subgradientmethods,de-composition.iiiivConstraintAggregationPrincipleinConvexOptimizationYuriM.ErmolievArkadiiV.KryazhimskiiAndrzejRuszczynski1IntroductionInthisarticleweconsidertheproblemofminimizingaconvexnon-dierentiablefunctionsubjecttoalargenumberoflinearandnonlinear(convex)constraints.Thestudyofsuchproblemsismotivatedbynewchallengesarisingintheanalysisoflargescalesystemswiththelackofsmoothbehavioralproperties.Ourobjectiveistodevelopageneralconstraintaggregationprinciplewhichcanbeusedinavarietyofmethodsforsolvingconvexoptimizationproblemsoftheformminf(x)(1:1)hj(x)0;j=1;:::;m;(1:2)x2X:(1:3)Weassumethroughoutthispaperthatthefunctionsf:IRn7!IRandhj:IRn7!IR;j=1;:::;m,areconvexandXIRnisconvexandcompact.Wealsoassumethatthefeasiblesetdenedby(1.2)-(1.3)isnon-emptywhichguaranteesthattheproblemhasanoptimalsolution.Weareespeciallyinterestedinthecasewhenthenumberofconstraintsmisverylarge,andthenumberofvariablesnislarge,too.Problemswithverymanyconstraintsariseinanaturalwayinvariousapplicationareas,likestochasticprogrammingproblemswithconstraintsthathavetoholdwithprobabilityone,inoptimalcontrolproblemswithstateconstraints,etc.(see,e.g.,[5]).Forverylargeproblemsthedirectapplicationofsuchproceduresasbundlemethods(see,e.g.,[7,6])maybecomedicult.Analternativeapproachisprovidedbynon-monotonesubgradientmethodsdatingbackto[1,14,18],whichfoundnumerousapplica-tionsandextensionstovariousclassesofproblems,suchasdiscreteoptimization,designofrobustdecompositionprocedures,generalproblemsofstochasticoptimization,min-maxandmoregeneralgame-theoreticalproblems(see[2,12,13,19]).However,treatinggeneralconvexconstraintswithinsubgradientmethodsmayalsobedicult.Thisre-quireseitherprojection(impracticalforlargemandn)oradditionalpenalty/multiplieriterations,whichforgeneralfandhjhave(sofar)onlytheoreticalimportanceinthisframework.1Wearegoingtofollowadierentpath.WeshallassumethatthestructureofXissimpleandthemaindicultycomesfromthelargenumberofconstraints(1.2).Toovercomethis,weshallreplacetheoriginalproblembyasequenceofproblemsinwhichthecomplicatingconstraints(1.2)arerepresentedbyonesurrogateinequalitymXj=1skjhj(x)0;(1:4)wheresk0areiterativelymodiedaggregationcoecients.Inthiswayasubstantialsimplicationof(1.1)-(1.3)isachieved,because(1.4)inheritslinearityordierentiabilitypropertiesof(1.2).Weshallshowhowtoupdatetheaggregationcoecientsandhowtousethesolutionofthesimpliedproblemstoarriveatthesolutionof(1.1)-(1.3).ItisworthnotingherethatourapproachisfundamentallydierentfromtheaggregationprovidedbyLagrangemultipliersandalsoworksforproblemsforwhichdualitydoesnothold.Itisalsodierentfromthemostlyheuristicaggregationmethodsdiscussedin[16].Insection2weshallconsiderthesimpliedversionoftheproblemhavingonlylin-earconstraintsandweshalldevelopacontinuoustimefeedbackruleusingconstraintaggregation.Insection3areformulationofthisprocedureispresented,whichallowsforvariousextensionsandgeneralizations.WeshallproveasimplelemmawhichisananalogoftheLyapunovfunctionapproachinthestudyofconvergenceofnon-monotonedynamic(iterative)processes.Usingthisresult,theconvergenceoftheaggregationprocedureinthesimpliedcaseisproved,undertheassumptionthattheproblemofminimizingfsubjecttothesurrogateconstraintcanbesolvedeasily.Insection4thisassumptionisrelaxed:itisshownthatitissucienttomakeastepinthedirectionofthesubgradientandprojecttheresultonthenon-stationarysurrogateconstraint.Section5generalizestheaggregationprincipletoconvexnon-linearinequalities.Twoaggregationschemesareanalyzed:directaggregation(1.4)andag