Show simple item record

A polynomial-time interior-point method for conic optimization, with inexact barrier evaluations

dc.contributor.authorSchurr, Simon P.
dc.contributor.authorO'Leary, Dianne P.
dc.contributor.authorTits, Andre L.
dc.date.accessioned2008-05-09T16:45:34Z
dc.date.available2008-05-09T16:45:34Z
dc.date.issued2008-04
dc.identifier.urihttp://hdl.handle.net/1903/7982
dc.description.abstractWe consider a primal-dual short-step interior-point method for conic convex optimization problems for which exact evaluation of the gradient and Hessian of the primal and dual barrier functions is either impossible or prohibitively expensive. As our main contribution, we show that if approximate gradients and Hessians of the primal barrier function can be computed, and the relative errors in such quantities are not too large, then the method has polynomial worst-case iteration complexity. (In particular, polynomial iteration complexity ensues when the gradient and Hessian are evaluated exactly.) In addition, the algorithm requires no evaluation---or even approximate evaluation---of quantities related to the barrier function for the dual cone, even for problems in which the underlying cone is not self-dual.en
dc.format.extent272981 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_USen
dc.relation.ispartofseriesUM Computer Science Departmenten
dc.relation.ispartofseriesCS-TR-4912en
dc.relation.ispartofseriesUMIACSen
dc.relation.ispartofseriesUMIACS-TR-2008-10en
dc.titleA polynomial-time interior-point method for conic optimization, with inexact barrier evaluationsen
dc.typeTechnical Reporten


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record