worst-case complexity analysis

Stochastic Three Points Method with an Inexact Oracle and Its Application to Steady-State Optimization

  • Geovani Nunes Grapiglia
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    We consider unconstrained derivative-free optimization problems in which only inexact function evaluations are available. Specifically, we study the setting where the oracle returns function values with partially controllable inexactness, with the error bounded linearly by a user-specified accuracy parameter, but with an unknown proportionality constant. This framework captures optimization problems arising from approximate simulations or … Read more

    Convergence Analysis of an Inexact Feasible Interior Point Method for Convex Quadratic Programming

  • Jacek Gondzio
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    In this paper we will discuss two variants of an inexact feasible interior point algorithm for convex quadratic programming. We will consider two different neighbourhoods: a (small) one induced by the use of the Euclidean norm which yields a short-step algorithm and a symmetric one induced by the use of the infinity norm which yields … Read more

    Local superlinear convergence of polynomial-time interior-point methods for hyperbolic cone optimization problems

  • Yurii Nesterov
  • Levent Tunçel
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    In this paper, we establish the local superlinear convergence property of some polynomial-time interior-point methods for an important family of conic optimization problems. The main structural property used in our analysis is the logarithmic homogeneity of self-concordant barrier function, which must have {\em negative curvature}. We propose a new path-following predictor-corrector scheme, which work only … Read more