资源描述：
《Exam Logistics》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、QualifyingExamSyllabusProposalEdwardD.KimDraftofNovember9,2007ExamCommitteeExamLogisticsProf.NinaAmenta(Dept.ofComputerScience)Date:Prof.EricBabson(Dept.ofMathematics)Feb/Mar2008Prof.Jes´usDeLoera(Dept.ofMathematics)Prof.FranciscoSantos(UniversityofCantabria)Time:Prof
2、.RomanVershynin(Dept.ofMathematics)TobedeterminedProf.RogerWetsa(Dept.ofMathematics)Location:aCommitteeChairpersonTobedeterminedThesisProposalPresentation:GraphsofConvexPolytopes1IntroductionConvexpolytopesarethesetsoffeasiblesolutionstolinearprograms.Thecombinatorics
3、andgeometryofpolytopesareessentialtounderstandingtheefficiencyofalgorithmsthatsolvetheseclassicaloptimizationproblems.Inparticular,thegraph(or1-skeleton)ofapolytopeisintimatelyconnectedtoDantzig’ssimplexfamilyofmethodsforsolvinglinearprograms.Whentheiterativemethodisimp
4、lementedonacomputer,ambiguitiesintheprocedureareresolvedbythespecificationofapivotrule.Boundingthediametersofthegraphsofpolytopesisparticularlyinterestingsincethediameterofitsgraphisalowerboundonthenumberofiterationsrequiredforthesimplexmethodusinganypivotrule.Letnbeafi
5、xedpositiveinteger.AhalfspaceHisasetoftheformH:={x∈Rn
6、hα,xi≤a}forsomea∈Randanon-zerovectorα∈Rn.Theboundary∂HofahalfspaceHformsahyperplane,whichcanbedescribedasfollows:∂H:={x∈Rn
7、hα,xi=a}ApolytopePinRnistheboundedintersectionoffinitely-manyhalfspaces.ForasubsetK⊆Rn,wedefi
8、netheconvexhullconvKtobethesmallestconvexsetcontainingK.Then,wecangiveanequivalentdefinitionforapolytope:AsubsetP⊆Rnisapolytopeif1andonlyifitistheconvexhullofafinitesetK⊂R.ThedimensiondofPisthedimensiond≤nofitsaffinehull.ThefacesofapolytopePareofspecialinterest.Thesesubse
9、tsoftheboundaryofParethepossiblesetsofoptimalsolutionsforalinearprogram.Wedefineafaceasfollows:LetHbeahalfspacethatcontainsP.Then,thefaceFofPassociatedtoHistheintersectionF:=P∩∂HofPwiththeassociatedhyperplane∂H.ThedimensiondimFofafaceFisthedimensionofitsaffinehull.Faceso
10、fdimensiond−1arecalledfacets.Thefacesofdimension0,whicharesinglepoints,arecalledvertices.Thefacesofdimension1,whicharealways
