Show simple item record

dc.contributor.authorGoldstein, Allen A.
dc.date1989-08
dc.date.accessioned2013-03-07T21:53:34Z
dc.date.available2013-03-07T21:53:34Z
dc.date.issued1989-08
dc.identifier.urihttp://hdl.handle.net/10945/30043
dc.descriptionApproved for public release; distribution is unlimited.en_US
dc.description.abstractThe analytic center of a polytope can be calculated in polynomial time by Newton's method. This note was motivated by papers of Renegar and Shub(88) and by Ye(89). We apply Smale's(86) estimates at one point for Newton's method to the problem of finding the analytic center of a polytope. The method converges globally in the appropriate norm. The ideas are then applied to obtain a possible benchmark for path following methods. When Smale's method is tractable its power stems not only from the fact that the information is concentrated at one point. There are 2 norms to estimate, not 3 as in the Kantorovich estimate. Moreover no estimate of the inverse of the derivative operator by itself is needed. The need for the norm of the inverse by itself often makes for coarse estimates. (kr)en_US
dc.description.sponsorshipThis report was prepared in conjunction with research conducted for the Naval Postgraduate School and funded by the Naval Postgraduate School. Reproduction of all or part of this report is authorized.en_US
dc.description.urihttp://archive.org/details/oncalculatingana00gold
dc.language.isoen_US
dc.publisherMonterey, California. Naval Postgraduate Schoolen_US
dc.rightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted.en_US
dc.subject.lcshCOMPUTATIONSen_US
dc.titleOn calculating analytic centersen_US
dc.typeReporten_US
dc.contributor.corporateNaval Postgraduate School (U.S.)
dc.subject.authorPolynomial algorithmsen_US
dc.subject.authorNewton's methoden_US
dc.subject.authorAnalytic Centeren_US
dc.subject.authorPolynomial algorithmsen_US
dc.subject.authorNewton's methoden_US
dc.subject.authorAnalytic centeren_US
dc.identifier.npsreportNPS-53-89-015


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record