Simultaneous optimization via approximate majoriza

1、SimultaneousOptimizationviaApproximateMajorizationforConcaveProfitsorConvexCostsAshishGoel∗StanfordUniversityAdamMeyerson†UniversityofCalifornia,LosAngelesAugust9,2005AbstractFormulti-criteriaproblemsandproblemswithpoorlycharacterizedobjective,itisoftendesirabletosimultaneouslyapproximatetheoptimumsolutionforalargeclassofobjectivefunctions.Weconsidertwosuchclasses:1.Maximizingallsymmetricconcavefunctions,and2.Minimizingallsymmetricconvexfunctions.Thefirstclasscorrespondstomaximizingprofitforaresou。

2、rceallocationproblem(suchasallocationofbandwidthsinacomputernetwork).Theconcavityrequirementcorrespondstothelawofdiminishingreturnsineconomics.Thesecondclasscorrespondstominimizingcostorcongestioninaloadbalancingproblem,wherethecongestion/costissomeconvexfunctionoftheloads.Informally,asimultaneousα-approximationforeitherclassisafeasiblesolutionthatiswithinafactorαoftheoptimumforallfunctionsinthatclass.Clearly,thestructureofthefeasiblesethasasignificantimpactonthebestpossibleαandthecomputationalco。

3、mplexityoffindingasolutionthatachieves(ornearlyachieves)thisα.Wedevelopaframeworkandasetoftechniquestoperformsimul-taneousoptimizationforawidevarietyofproblems.Wefirstrelatesimultaneousα-approximationforbothclassestoα-approximatemajorization.Thenweprovethatα-approximatelymajorizedsolutionsexistforlogarithmicvaluesofαfortheconcaveprofitscase.Forbothclasses,wepresentapolynomialtimealgorithmtofindthebestαifthesetofconstraintsisapolynomial-sizedlinearprogramanddiscussseveralnon-trivialapplications.These。

4、applicationsincludefindinga(logn)-majorizedsolutionformulticommodityflow,andfindingapprox-imatelybestαforvariousformsofloadbalancingproblems.Ourtechniquescanalsobeappliedtoproduceapproximatelyfairversionsofthefacilitylocationandbi-criterianetworkdesignproblems.Inaddition,wedemonstrateinterestingconnectionsbetweendistributionalloadbalancing(wherethesizesofjobsaredrawnfromknownprobabilitydistributionsbuttheactualsizeisnotknownatthetimeofplacement)andapproximatemajorization.∗DepartmentofManagementScie。

5、nceandEngineeringand(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,..。

6、.,xniisann-dimensionalvectorandUisann-variatesymmetricconcavefunction.Thisgeneralscenariocapturesproblemswhereweneedtoallocateresourcestousersinordertomaximizetheoverallprofit/utility;here,xisthevectorofresourceallocationstodifferentusers.Concavityoftheobjectivefunctioncorrespondstothe“lawofdiminishingreturns”fromeconomics.Symmetrycorrespondstosayingthatallusersareequallyimportant.Noticethattheconstraintsarenotrequiredtobesymmetric,andhence,theoptimumsolutionneednotbesymmetriceventhoughtheobjecti。

7、vefunctionissymmetric.WewillfurtherassumethatU(0)=0andthatUisnon-decreasingineachargument.Thesearebothnaturalrestrictionsforprofit/utilityfunctions.Wewillcallsuchfunctionscanonicalutilityfunctions.ThetwosimplestexamplesarePixiandmin{x1,x2,...,xn}.NowconsidertheproblemofminimizingC(x)subjecttox≥0andsomeadditionalconstraintswhereCisasymmetricconvexfunctionsuchthatC(0)=0andCisnon-decreasingineachargument.Wewillcallthesefunctionscanonicalcongestionfunctions.Thisgeneralscenariocapturesseveralloadbalan。

8、cingproblems;herexisthevectorofloadsondifferentmachines.ConvexityofCisanaturalassumptionsincemostnaturalmeasuresofcongestionareconvex.Symmetryindicatesthatallmachinesareequallyimportant;asbefore,theconstraints,andhencetheoptimumsolutionneednotbesymmetric.SomecommoncanonicalcongestionfunctionsarePixi,max{x1,x2,...,xn},Pix2i(variance),andPixi1−xi(theM/M/1queueingdelayfunction).Theseproblemscanoftenbesolvedbyusingpiece-wiselinearapproximationsoftheconcaveorconvexfunction,andthenapplyingtechniquesfo。

9、rlinearobjectivefunctions.Forexample,ifthesetofconstraintsarelinear,thentheseproblemscanoftenbesolvedinpolynomialtime(forexample,usingtheellipsoidalgorithm[12]).However,weareinterestedinfindingafeasiblesolutionwhichisagoodapproximationsimultaneouslyforallcanonicalutilityfunctionsorallcanonicalcongestionfunctions–hencetheterm“simultaneousoptimization”.Clearly,theexactqualityofthesolutionachievabledependsonthesetofconstraints.Inthispaper,wedevelopageneralframeworkandasetoftechniquesthatareapplicabl。

10、etoawidevarietyofconstraints.Beforeproceedingfurther,wedefinesimultaneousoptimizationmoreprecisely.Definition1.1Afeasiblevectorxisasimultaneousα-approximationforaresourceallocationproblemifU(x)≥U(y)/αforallotherfeasiblesolutionsyandallcanonicalutilityfunctionsU.Sinceconvexfunctionscanbearbitrarilysteep,ananalogousdefinitionwouldbetoostrictforresourceallocationproblems.Insteadwedefine:Definition1.2Afeasiblevectorxisasimultaneousα-approximationforaloadbalancingproblemifC(x/α)≤C(y)forallotherfeasiblesolu。