資源描述：
《Exam Logistics》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
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、andgeometryofpolytopesareessentialtounderstandingthee?ciencyofalgorithmsthatsolvetheseclassicaloptimizationproblems.Inparticular,thegraph(or1-skeleton)ofapolytopeisintimatelyconnectedtoDantzig’ssimplexfamilyofmethodsforsolvinglinearprograms.Whentheiterativemethodisimp
4、lementedonacomputer,ambiguitiesintheprocedureareresolvedbythespeci?cationofapivotrule.Boundingthediametersofthegraphsofpolytopesisparticularlyinterestingsincethediameterofitsgraphisalowerboundonthenumberofiterationsrequiredforthesimplexmethodusinganypivotrule.Letnbea?
5、xedpositiveinteger.AhalfspaceHisasetoftheformH:={x∈Rn
6、hα,xi≤a}forsomea∈Randanon-zerovectorα∈Rn.Theboundary?HofahalfspaceHformsahyperplane,whichcanbedescribedasfollows:?H:={x∈Rn
7、hα,xi=a}ApolytopePinRnistheboundedintersectionof?nitely-manyhalfspaces.ForasubsetK?Rn,wede?
8、netheconvexhullconvKtobethesmallestconvexsetcontainingK.Then,wecangiveanequivalentde?nitionforapolytope:AsubsetP?Rnisapolytopeif1andonlyifitistheconvexhullofa?nitesetK?R.ThedimensiondofPisthedimensiond≤nofitsa?nehull.ThefacesofapolytopePareofspecialinterest.Thesesubse
9、tsoftheboundaryofParethepossiblesetsofoptimalsolutionsforalinearprogram.Wede?neafaceasfollows:LetHbeahalfspacethatcontainsP.Then,thefaceFofPassociatedtoHistheintersectionF:=P∩?HofPwiththeassociatedhyperplane?H.ThedimensiondimFofafaceFisthedimensionofitsa?nehull.Faceso
10、fdimensiond?1arecalledfacets.Thefacesofdimension0,whicharesinglepoints,arecalledvertices.Thefacesofdimension1,whicharealways
