Simultaneous optimization via approximate majoriza

SimultaneousOptimizationviaApproximateMajorizationforConcaveProfitsorConvexCostsAshishGoel∗StanfordUniversityAdamMeyerson†UniversityofCalifornia,LosAngelesAugust9,2005AbstractFormulti-criteriaproblemsandproblemswithpoorlycharacterizedobjective,itisoftendesirabletosimultaneouslyapproximatetheoptimumsolutionforalargeclassofobjectivefunctions.Weconsidertwosuchclasses:1.Maximizingallsymmetricconcavefunctions,and2.Minimizingallsymmetricconvexfunctions.Thefirstclasscorrespondstomaximizingprofitforaresourceallocationproblem(suchasallocationofbandwidthsinacomputernetwork).Theconcavityrequirementcorrespondstothelawofdiminishingreturnsineconomics.Thesecondclasscorrespondstominimizingcostorcongestioninaloadbalancingproblem,wherethecongestion/costissomeconvexfunctionoftheloads.Informally,asimultaneousα-approximationforeitherclassisafeasiblesolutionthatiswithinafactorαoftheoptimumforallfunctionsinthatclass.Clearly,thestructureofthefeasiblesethasasignificantimpactonthebestpossibleαandthecomputationalcomplexityoffindingasolutionthatachieves(ornearlyachieves)thisα.Wedevelopaframeworkandasetoftechniquestoperformsimul-taneousoptimizationforawidevarietyofproblems.Wefirstrelatesimultaneousα-approximationforbothclassestoα-approximatemajorization.Thenweprovethatα-approximatelymajorizedsolutionsexistforlogarithmicvaluesofαfortheconcaveprofitscase.Forbothclasses,wepresentapolynomialtimealgorithmtofindthebestαifthesetofconstraintsisapolynomial-sizedlinearprogramanddiscussseveralnon-trivialapplications.Theseapplicationsincludefindinga(logn)-majorizedsolutionformulticommodityflow,andfindingapprox-imatelybestαforvariousformsofloadbalancingproblems.Ourtechniquescanalsobeappliedtoproduceapproximatelyfairversionsofthefacilitylocationandbi-criterianetworkdesignproblems.Inaddition,wedemonstrateinterestingconnectionsbetweendistributionalloadbalancing(wherethesizesofjobsaredrawnfromknownprobabilitydistributionsbuttheactualsizeisnotknownatthetimeofplacement)andapproximatemajorization.∗DepartmentofManagementScienceandEngineeringand(bycourtesy)ComputerScience,StanfordUniversity.Researchsup-portedinpartbyanNSFCAREERaward0133968,aTermanEngineeringFellowship,andanAlfredP.SloanFacultyFellowship.Email:[e-mail]†DepartmentofComputerScience,UniversityofCalifornia,LosAngeles.ResearchsupportedbyNSFgrantCCR-0122581andAROgrantDAAG55-98-1-0170.Email:[e-mail]11IntroductionSimultaneousOptimization:ConsidertheproblemofmaximizingU(x)subjecttox≥0andsomeadditionalconstraints(suchasAx≤C),wherex=hx1,x2,...,xniisann-dimensionalvectorandUisann-variatesymmetricconcavefunction.Thisgeneralscenariocapturesproblemswhereweneedtoallocateresourcestousersinordertomaximizetheoverallprofit/utility;here,xisthevectorofresourceallocationstodifferentusers.Concavityoftheobjectivefunctioncorrespondstothe“lawofdiminishingreturns”fromeconomics.Symmetrycorrespondstosayingthatallusersareequallyimportant.Noticethattheconstraintsarenotrequiredtobesymmetric,andhence,theoptimumsolutionneednotbesymmetriceventhoughtheobjectivefunctionissymmetric.WewillfurtherassumethatU(0)=0andthatUisnon-decreasingineachargument.Thesearebothnaturalrestrictionsforprofit/utilityfunctions.Wewillcallsuchfunctionscanonicalutilityfunctions.ThetwosimplestexamplesarePixiandmin{x1,x2,...,xn}.NowconsidertheproblemofminimizingC(x)subjecttox≥0andsomeadditionalconstraintswhereCisasymmetricconvexfunctionsuchthatC(0)=0andCisnon-decreasingineachargument.Wewillcallthesefunctionscanonicalcongestionfunctions.Thisgeneralscenariocapturesseveralloadbalancingproblems;herexisthevectorofloadsondifferentmachines.ConvexityofCisanaturalassumptionsincemostnaturalmeasuresofcongestionareconvex.Symmetryindicatesthatallmachinesareequallyimportant;asbefore,theconstraints,andhencetheoptimumsolutionneednotbesymmetric.SomecommoncanonicalcongestionfunctionsarePixi,max{x1,x2,...,xn},Pix2i(variance),andPixi1−xi(theM/M/1queueingdelayfunction).Theseproblemscanoftenbesolvedbyusingpiece-wiselinearapproximationsoftheconcaveorconvexfunction,andthenapplyingtechniquesforlinearobjectivefunctions.Forexample,ifthesetofconstraintsarelinear,thentheseproblemscanoftenbesolvedinpolynomialtime(forexample,usingtheellipsoidalgorithm[12]).However,weareinterestedinfindingafeasiblesolutionwhichisagoodapproximationsimultaneouslyforallcanonicalutilityfunctionsorallcanonicalcongestionfunctions–hencetheterm“simultaneousoptimization”.Clearly,theexactqualityofthesolutionachievabledependsonthesetofconstraints.Inthispaper,wedevelopageneralframeworkandasetoftechniquesthatareapplicabletoawidevarietyofconstraints.Beforeproceedingfurther,wedefinesimultaneousoptimizationmoreprecisely.Definition1.1Afeasiblevectorxisasimultaneousα-approximationforaresourceallocationproblemifU(x)≥U(y)/αforallotherfeasiblesolutionsyandallcanonicalutilityfunctionsU.Sinceconvexfunctionscanbearbitrarilysteep,ananalogousdefinitionwouldbetoostrictforresourceallocationproblems.Insteadwedefine:Definition1.2Afeasiblevectorxisasimultaneousα-approximationforaloadbalancingproblemifC(x/α)≤C(y)forallotherfeasiblesolu