Yurii Nesterov

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

    Generalized power method for sparse principal component analysis

  • Michel Journee
  • Yurii Nesterov
  • Peter Richtarik
  • Rodolphe Sepulchre
    • Categories Applications - Science and Engineering, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    In this paper we develop a new approach to sparse principal component analysis (sparse PCA). We propose two single-unit and two block optimization formulations of the sparse PCA problem, aimed at extracting a single sparse dominant principal component of a data matrix, or more components at once, respectively. While the initial formulations involve nonconvex functions, … Read more

    Primal-dual interior-point methods with asymmetric barrier

  • Yurii Nesterov
    • Categories Applications - Science and Engineering Tags , ,

    In this paper we develop several polynomial-time interior-point methods (IPM) for solving nonlinear primal-dual conic optimization problem. We assume that the barriers for the primal and the dual cone are not conjugate. This broken symmetry does not allow to apply the standard primal-dual IPM. However, we show that in this situation it is also possible … Read more

    Gradient methods for minimizing composite objective function

  • Yurii Nesterov
    • Categories Convex and Nonsmooth Optimization Tags , , , , , ,

    In this paper we analyze several new methods for solving optimization problems with the objective function formed as a sum of two convex terms: one is smooth and given by a black-box oracle, and another is general but simple and its structure is known. Despite to the bad properties of the sum, such problems, both … Read more

    Gradient methods for minimizing composite objective function

  • Yurii Nesterov
    • Categories Convex and Nonsmooth Optimization Tags , , , , , ,

    In this paper we analyze several new methods for solving optimization problems with the objective function formed as a sum of two convex terms: one is smooth and given by a black-box oracle, and another is general but simple and its structure is known. Despite to the bad properties of the sum, such problems, both … Read more

    Cubic regularization of Newton’s method for convex problems with constraints

  • Yurii Nesterov
    • Categories Constrained Nonlinear Optimization Tags , , ,

    In this paper we derive the efficiency estimates of the regularized Newton’s method as applied to constrained convex minimization problems and to variational inequalities. We study a one-step Newton’s method and its multistep accelerated version, which converges on smooth convex problems as $O({1 \over k^3})$, where $k$ is the iteration counter. We derive also the … Read more

    Nonsymmetric potential-reduction methods for general cones

  • Yurii Nesterov
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    In this paper we propose two new nonsymmetric primal-dual potential-reduction methods for conic problems. Both methods are based on {\em primal-dual lifting}. This procedure allows to construct a strictly feasible primal-dual pair linked by an exact {\em scaling} relation even if the cones are not symmetric. It is important that all necessary elements of our … Read more

    Constructing self-concordant barriers for convex cones

  • Yurii Nesterov
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper we develop a technique for constructing self-concordant barriers for convex cones. We start from a simple proof for a variant of standard result on transformation of a $\nu$-self-concordant barrier for a set into a self-concordant barrier for its conic hull with parameter $(3.08 \sqrt{\nu} + 3.57)^2$. Further, we develop a convenient composition … Read more

    Towards nonsymmetric conic optimization

  • Yurii Nesterov
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    In this paper we propose a new interior-point method, which is based on an extension of the ideas of self-scaled optimization to the general cones. We suggest using the primal correction process to find a {\em scaling point}. This point is used to compute a strictly feasible primal-dual pair by simple projection. Then, we define … Read more

    On the Riemannian Geometry Defined by Self-Concordant Barriers and Interior-Point Methods

  • Yurii Nesterov
  • Michael J. Todd
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    We consider the Riemannian geometry defined on a convex set by the Hessian of a self-concordant barrier function, and its associated geodesic curves. These provide guidance for the construction of efficient interior-point methods for optimizing a linear function over the intersection of the set with an affine manifold. We show that algorithms that follow the … Read more