Separable convex optimization problems with linear

arXiv:0707.2265v1[cs.IT]16Jul2007SEPARABLECONVEXOPTIMIZATIONPROBLEMSWITHLINEARASCENDINGCONSTRAINTS∗ARUNPADAKANDLAANDRAJESHSUNDARESAN†SubmittedtotheSIAMJournalonOptimization,Jul.2007.Abstract.Separableconvexoptimizationproblemswithlinearascendinginequalityandequalityconstraintsareaddressedinthispaper.Underanorderingconditionontheslopesofthefunctionsattheorigin,analgorithmthatdeterminestheoptimumpointinafinitenumberofstepsisdescribed.Theoptimumvalueisshowntobemonotonewithrespecttoapartialorderontheconstraintparameters.Moreover,theoptimumvalueisconvexwithrespecttotheseparameters.Examplesmotivatedbyoptimizationsforcommunicationsystemsareusedtoillustratethealgorithm.Keywords.ascendingconstraints,convexoptimization,linearconstraints,separableproblem.AMSsubjectclassifications.90C25,52A411.Problemdescription.Letgm,m=1,2,···,Lbefunctionsthatsatisfythefollowing:•gm:(am,bm)→Rwheream∈[−∞,0)andbm∈(0,+∞]andtherefoream0bm;•gmisstrictlyconvexinitsdomain(am,bm);•gmiscontinuouslydifferentiableinitsdomain(am,bm);•Theslopesofthefunctionsat0,i.e.,thevaluesofthestrictlyincreasingfunctionhm:=g′mat0,areinincreasingorderwithrespecttotheindexm:h1(0)≤h2(0)≤···≤hL(0);(1.1)•Thereisapointinthedomain(am,bm)wheretheslopeofgmequalsh1(0),theslopeofthefirstfunctionat0.(Thismaybeequivalentlystatedash1(0)≥hm(am+),given(1.1)andthathmiscontinuousandstrictlyincreasing).Inthispaper,weminimizetheseparableobjectivefunctionG:RL→RgivenbyG(y):=LXm=1gm(ym),(1.2)wherey=(y1,···,yL),subjecttothefollowinglinearinequalityandequalitycon-straints:ym∈[0,βm],m=1,2,···,L,(1.3)lXm=1ym≥lXm=1αm,l=1,2,···,L−1,(1.4)LXm=1ym=KXm=1αm.(1.5)∗ThisworkwassupportedbytheUniversityGrantsCommissionunderGrantPart(2B)UGC-CAS-(Ph.IV)andbytheDepartmentofScienceandTechnologyunderGrantDSTO748.†DepartmentofElectricalCommunicationEngineering,IndianInstituteofScience,Bangalore560012,India.E-mail:[e-mail]traints,weassumeβm∈(0,bm]form=1,2,···,L,αm≥0form=1,2,···,K,whereK≥L,andnaturally,KXm=1αm≤LXm=1βm.(1.6)WealsoassumeKXm=Lαm0.(1.7)Theinequalitiesin(1.3)imposepositivityandupperboundconstraints.Notethatifβm=bm,theupperboundconstraintisirrelevantbecausethedomainofgmis(am,bm).Theinequalitiesin(1.4)imposeasequenceofascendingconstraintswithincreasingheightsPlm=1αmindexedbyl.Assumption(1.6)isnecessaryfortheconstraintsettobenonempty.Without(1.7),itiseasytoseethatyL=0,andtheproblemreducestoasimilaronewithfewervariables.Whatwehavedescribedisaseparableconvexoptimizationproblemwithlinearinequalityandequalityconstraints.Arichdualitytheoryexistsforsuchproblems.SeeBertsekas[1,Sec.5.1.6].Here,weprovideanalgorithmthatputsoutavectorthatminimizes(1.2)andterminatesinatmostLsteps.Section2containsadescriptionofthealgorithmandSection4theproofofitsoptimality.WhilewemaytakeK=Lwithoutlossofgenerality,allowingK≥Lsimplifiestheexpositionofouralgorithm.Problemsoftheabovekindariseintheoptimizationofmulti-terminalcommuni-cationsystemswherepowerutilized,measuredinJoulespersecond,isminimized,orthroughputachieved,measuredinbitspersecond,ismaximized,subjecttomeetingcertainqualityofserviceandfeasibilityconstraints.SeeViswanath&Anantharam[2]fordetailsandSection3forspecificexamples.Viswanath&Anantharam[2]providetwoalgorithmsfortheirpowerminimizationandthroughputmaximizationproblems.OurworkunitestheirsolutionsandgoesfurthertominimizeanyGthatsatisfiestheconstraintsmentionedabove.UnderafurtherconditiononthefunctionswhichwillbestatedinSection2,wearguethatouralgorithmprovidesthesolutiontotheaboveoptimizationproblemwiththeadditionalorderingconstrainty1≥y2≥···≥yL.2.TheMainResults.Webeginwithsomeremarksonnotation.•Forintegersi,jsatisfyingi≤j,weletJi,jKdenotetheset{i,i+1,···,j}.•LetEm:=hm((am,bm)),therangeofhm.Thustheconditionh1(0)hm(am+),m∈J1,LKinSection1maybewrittenash1(0)∈∩Lm=1Em.(2.1)•Denotebyh−1m:Em→(am,bm)theinverseofthecontinuousandstrictlyincreasingfunctionhm.Theinverseisalsocontinuousandstrictlyincreasinginitsdomain.•Forconvenience,definethefunctionsHm:Em→(am,βm]tobeHm:=h−1m∧βm.(2.2)Hmisclearlyincreasing.1Assignmentstothevariableymwillbeviaeval-uationofHmsothattheupperboundconstraintin(1.3)isautomaticallysatisfied.1Wesayfisincreasingifabimpliesf(a)≥f(b).Ifthereisstrictinequality,wesayfisstrictlyincreasing.Similarlyweusepositivefor≥0andstrictlypositivefor0.CONVEXOPTIMIZATIONWITHASCENDINGCONSTRAINTS3•For1≤i≤lL,letθlidenotetheleastθ≥h1(0)thatsatisfiestheequationlXm=iHm(θ)=lXm=iαm,(2.3)providedthesetofsuchθisnonempty.Otherwisewesayθlidoesnotexist.ThedomainofPlm=iHmis∩lm=iEm.ThefunctionPlm=iHmisincreasing,andmoreover,strictlyincreasinguntilallfunctionsinthesumsaturate.Sothereisnosolutionto(2.3)whenforexamplePlm=iαmPlm=iβm.Ingeneral,ifwecandemonstratetheexistenceofθandθ,bothintheset∩lm=iEm,thatsatisfylXm=iHm(θ)≤lXm=iαm≤lXm=iHmθ
,(2.4)thentheexistenceofθli∈∩lm=iEmisassured,thankstothecontinuityofPlm=iHm.Indeed,wemayalwaystakeθ=h1(0).Thisisbecauseourassumptions(2.1),(1.1),andtheincreasingpropertyofHm,m∈J1,LKimplylXm=iHm(h1(0))≤lXm=iHm(hm(0))=lXm=ih−1m(hm(0))∧βm
=0≤lXm=iαm.Thec