University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports of the Computer Science Department
    • View Item
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports of the Computer Science Department
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

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

    Thumbnail
    View/Open
    inexact_barrier_submitted1.pdf (266.5Kb)
    No. of downloads: 676

    Date
    2008-04
    Author
    Schurr, Simon P.
    O'Leary, Dianne P.
    Tits, Andre L.
    Metadata
    Show full item record
    Abstract
    We 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.
    URI
    http://hdl.handle.net/1903/7982
    Collections
    • Technical Reports from UMIACS
    • Technical Reports of the Computer Science Department

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility