100 Pages
English

Solving systems of positive polynomial equations [Elektronische Ressource] / Stefan Kiefer

Gain access to the library to view online
Learn more

Description

¨ ¨TECHNISCHE UNIVERSITAT MUNCHENLehrstuhl fu¨r Informatik VIISolving Systems ofPositive Polynomial EquationsStefan KieferVollst¨andiger Abdruck der von der Fakult¨at fur¨ Informatik der Technischen Universita¨tMunc¨ hen zur Erlangung des akademischen Grades einesDoktors der Naturwissenschaften (Dr. rer. nat.)genehmigten Dissertation.Vorsitzender: Univ.-Prof. Dr. H. SeidlPruf¨ er der Dissertation: 1. Univ.-Prof. Dr. F.J. Esparza Estaun2. Univ.-Prof. Dr. H.-J. BungartzDie Dissertation wurde am 25.06.2009 bei der Technischen Universit¨at Munc¨ hen eingereichtund durch die Fakult¨at fur¨ Informatik am 02.10.2009 angenommen.AbstractIn this thesis, we consider equation systems of the formX = f (X ,...,X )1 1 1 n...X = f (X ,...,X )n n 1 nwhere f (X ,...,X ) is, for all i ∈ {1,...,n}, an expression built up from real-valuedi 1 nvariablesX ,...,X ,nonnegativerealconstants,andtheoperatorsmultiplication,addition,1 nminimum and maximum. We call such an equation system positive and denote it in vectorform by X =f(X). The least solution is called μ, i.e., μ is the least fixed point of f.Positive equation systems appear naturally in the analysis of stochastic models likestochastic context-free grammars (with numerous applications to natural language process-ingandcomputationalbiology), probabilisticprogramswithprocedures,web-surfingmodelswith back buttons, branching processes, and termination games.

Subjects

Informations

Published by
Published 01 January 2009
Reads 20
Language English

TECHNISCHEUNIVERSITA¨TMU¨NCHEN
Lehrstuhlfu¨rInformatikVII

SolvingSystemsof
PositivePolynomialEquations

StefanKiefer

Vollsta¨ndigerAbdruckdervonderFakulta¨tf¨urInformatikderTechnischenUniversita¨t
M¨unchenzurErlangungdesakademischenGradeseines

DoktorsderNaturwissenschaften(Dr.rer.nat.)

genehmigtenDissertation.

Vorsitzender:Univ.-Prof.Dr.H.Seidl

Pr¨uferderDissertation:1.Univ.-Prof.Dr.F.J.EsparzaEstaun
2.Univ.-Prof.Dr.H.-J.Bungartz

DiundeDidursscerhtaditieonFawkulurtdea¨taf¨mur2I5nf.0o6r.m20a0ti9kbaeim0der2.1T0.ec20hni09scahenngenoUnimvmersen.ita¨tM¨uncheneingereicht

Abstract

Inthisthesis,weconsiderequationsystemsoftheform
X1=f1(X1,...,Xn)
...Xn=fn(X1,...,Xn)
wherefi(X1,...,Xn)is,foralli2{1,...,n},anexpressionbuiltupfromreal-valued
variablesX1,...,Xn,nonnegativerealconstants,andtheoperatorsmultiplication,addition,
minimumandmaximum.Wecallsuchanequationsystempositiveanddenoteitinvector
formbyX=f(X).Theleastsolutioniscalledµ,i.e.,µistheleastxedpointoff.
Positiveequationsystemsappearnaturallyintheanalysisofstochasticmodelslike
stochasticcontext-freegrammars(withnumerousapplicationstonaturallanguageprocess-
ingandcomputationalbiology),probabilisticprogramswithprocedures,web-surngmodels
withbackbuttons,branchingprocesses,andterminationgames.Thesolutionµofapos-
itiveequationsystemX=f(X)isofcentralinterestforthesemodels.Ecientmethods
tocomputeµarethemainsubjectofthisthesis.
Forpositiveequationsystemswithoutminimumormaximumoperator,Newton’smethod
forapproximatingazeroofadierentiablefunctioncanbeappliedtoapproximateµ.In
therstpartofthethesis,westudyindetailtheconvergencespeedofNewton’smethod
forsuchequationsystemsandshow,inparticular,thatNewton’smethodconvergesatleast
linearlytoµ.Wealsogiveconcreteboundsontheconvergencerate.
Tocomputetheleastxedpointofgeneralpositiveequationsystemswithminimum
andmaximumoperators,Newton’smethodcannotbedirectlyused.Inthesecondpart,we
suggesttwoalgorithmsthatcombineNewton’smethodwithlinearprogramming.Weshow
thatthesemethodsconvergelinearlytoµandgiveboundsontheconvergencerate.We
alsoshowthatoneofthosemethodscanbeusedtocomputenear-optimalstrategiesforthe
gameassociatedwithpositiveequationsystems.

Acknowledgments

Thisthesiswouldnothavebeenpossiblewithouttheguidance,generosityandgoodwill
ofmanypeople.Ifeelgratefulandindebtedtohavereceivedalltheirhelp.
Thisapplies,rstandforemost,tomysupervisorProf.JavierEsparza,whohasalways
hadtimeforme.Countlessfruitfuldiscussionswithhim,hisintelligentinsights,andhis
continuousinvaluablesupporthavemadethisthesispossible.Hisinspiringpersonalitywill
havealong-lastinginuenceonmyfuturelife.
LargepartsofthisthesisresultfromjointworkwithmycolleagueandfriendMichael
Luttenberger,whoseingenuityandhardworkwereindispensablefortheresultsonNewton’s
method.IwouldliketoexpressmygratitudetoProf.HelmutSeidl,whosuggestedthe
extensionstominimumandmaximumoperators,andtoThomasGawlitzaforaveryfriendly,
intenseandfruitfulcollaboration.SpecialthanksgotoProf.Hans-JoachimBungartzfor
beingarefereeofthisthesisandtoProf.VolkerDiekertforhissupportinStuttgart.
IwanttothanktheUniversita¨tStuttgart,theTechnischeUniversita¨tM¨unchen,andthe
DeutscheForschungsgemeinschaft(DFG),whichallprovidedessentialnancialandorgani-
zationalsupport.
MycolleaguesmademytimeinStuttgartandMunichapleasure.Thegreatatmosphere
inourgroupwas,inparticular,duetoMichaelLuttenberger,StefanSchwoon,andDe-
jvuthSuwimonteerabuth,whowerealwaysreadyforbothworkandamusement.Ithank
themandmanyotherformerandpresentcolleaguesforcontributingtotheperfectworking
environmentinProf.Esparza’sgroup.
Myparentswereandarethesourceofencouragement,loveandsupportthroughoutthe
years.Thankyouforeverything.

Contents

Outline

1

0Introduction3
0.1SystemsofPositivePolynomials..........................3
0.2SystemsofPositiveMin-MaxPolynomials....................11

1SystemsofPositivePolynomials16
1.1Preliminaries....................................16
1.1.1Notation...................................16
1.1.2SystemsofPositivePolynomials.....................17
1.1.3ConvergenceSpeed.............................19
1.1.4StochasticModels.............................19
1.2Newton’sMethodandanOverviewofOurResults...............21
1.3FundamentalPropertiesofNewton’sMethod..................22
1.3.1Eectiveness................................22
1.3.2Monotonicity................................28
1.3.3ExponentialConvergenceOrderintheNonsingularCase........28
1.3.4ReductiontotheQuadraticCase.....................30
1.4StronglyConnectedSPPs.............................32
1.4.1ConeVectors................................32
1.4.2ConvergenceSpeedinTermsofConeVectors..............34
1.4.3ConvergenceSpeedIndependentfromConeVectors..........37
1.4.4UpperBoundsontheLeastFixedPointViaNewtonApproximants.42
1.5GeneralSPPs....................................45
1.5.1ConvergenceSpeedoftheDecomposedNewtonMethod(DNM)...45
1.5.2ConvergenceSpeedofNewton’sMethod.................48
1.6UpperBoundsontheConvergence........................49
1.7Conclusions.....................................50

ii

Contents

2SystemsofPositiveMin-Max-Polynomials52
2.1PreliminariesandaFundamentalTheorem...................52
2.1.1PowerSeriesandSomeConvexityPropertiesofSPPs.........52
2.1.2Min-Max-SPPs...............................55
2.2AClassofApplications:ExtinctionGames...................57
2.3The-Method...................................59
2.4The-Method...................................65
2.5Comparisons....................................74
2.6Conclusions.....................................76

3GeneralizingNewton’sMethod:AnEpilogue

77

AProofsofChapter182
A.1ProofofLemma1.49................................82

BProofsofChapter286
B.1ProofofLemma2.28................................86
B.2ProoffortheClaimsinExample2.41......................88

Bibliography

98

Outline

Inthisthesis,weconsiderequationsystemsoftheform
X1=f1(X1,...,Xn)
...Xn=fn(X1,...,Xn)
wherefi(X1,...,Xn)is,foralli2{1,...,n},anexpressionbuiltupfromthereal-valued
variablesX1,...,Xn,nonnegativerealconstants,andtheoperatorsmultiplication,addition,
minimumandmaximum.Wecallsuchanequationsystempositiveanddenoteitinvector
formbyX=f(X).Theleastsolutioniscalledµ,i.e.,µistheleastxedpointoff.
Positiveequationsystemsappearnaturallyintheanalysisofstochasticmodelslike
stochasticcontext-freegrammars(withnumerousapplicationstonaturallanguageprocess-
ingandcomputationalbiology),probabilisticprogramswithprocedures,web-surngmodels
withbackbuttons,branchingprocesses,andterminationgames.Thesolutionµofapositive
equationsystemX=f(X)isofcentralinterestforthesemodels.Ecientmethodstocom-
puteµarethemainsubjectofthisthesis.Chapter0containsanextensiveintroduction
tothetopic.AllresultsarecontainedinChapter1andChapter2.
InChapter1,theexpressionsfiarerestrictedtobepolynomialswithnonnegative
coecients,i.e.,theoperatorsminimumandmaximumarenotallowed.Forsuchequation
systems,EtessamiandYannakakis[EY09]suggestedtouseNewton’smethod,theclassical
approximationtechniqueinnumericalanalysis.Moreprecisely,theiralgorithmdecomposes
theequationsysteminstronglyconnectedcomponents(whereeachvariabledependsdirectly
orindirectlyoneveryothervariable)andappliesNewton’smethodineachcomponent.In
Chapter1weextendandimproveEtessamiandYannakakis’results.Moreconcretely,we
:whos

•IfNewton’smethodisstartedatthevector0,itconvergesmonotonicallytoµ,no
matteriftheequationsystemisstronglyconnectedornot.
•Newton’smethodconvergestoµatleastlinearly,i.e.,thenumberofvalidbitsisat
leastalinearfunctionofthenumberofiterationsperformed.Inaddition,weshow:
–ForstronglyconnectedsystemsX=f(X),thereisa“threshold”kfsuchthat
foralli0,the(kf+i)-thNewtoniterate,hasatleastivalidbits.By“atleast
ivalidbits”wemeanthat,ineachcomponent,therelativeerroroftheNewton
iterateisatmost2i.Inaddition,wegiveconcreteupperboundsonkf.
–Forsystemsthatarenotstronglyconnected,theconvergencerate(i.e.,thenum-
berofadditionalvalidbitsperiteration)ispoorer.Weprovideboundsforthe
convergencerateandshowthattheyareessentiallytight.

2

neilOut

InChapter2,weconsidergeneralpositiveequationsystems,i.e.,weallowminimumand
maximumoperators.Suchequationsystemsariseinpopulationmodelswheretwoplayers
areallowedtoinuencecertainindividuals;oneplayer(theterminator)strivestoextinguish
thepopulation,theotherplayer(thesavior)hastheoppositeobjective.Newton’smethod,
directlyappliedtosuchequationsystems,doesnotalwaysconvergetoµ.However,itcan
beadaptedtoamethodwhichconvergeslinearlytoµ.Moreconcretely,weobtainthe
followingresults:

•WeproposetwoextensionsofNewton’smethodthatbothapproximateµforany
positiveequationsystem.Weshowthatbothofthemconvergemonotonicallyand
linearlytoµ.
•Oneoftheproposedalgorithmscomputes,asabyproduct,foreachiterate,astrategy
fortheterminatorthatguaranteestheterminatorawinningprobabilityofatleast.
Sincetheiteratesconvergetoµ,thesestrategiesarenear-optimal.

Chapter2buildsonresultsofChapter1,butChapter2canbeunderstoodwithout
studyingChapter1indetail.WeprovideconclusionsofourworkattheendofChapter1
andChapter2,respectively.
Themainthemesofthisworkarexed-pointequations,andvariantsofNewton’smethod
tosolvethem.Thisthesisendswithakindof“epilogue”inChapter3,whichsketchesa
generalizationofpositive