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.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.relation.ispartofseriesUM Computer Science Departmenten
dc.titleA polynomial-time interior-point method for conic optimization, with inexact barrier evaluationsen
dc.typeTechnical Reporten

Files in this item


This item appears in the following Collection(s)

Show simple item record