Convex Optimization

The stochastic multi-gradient algorithm for multi-objective optimization and its application to supervised machine learning

  • Suyun Liu
  • Luis Nunes Vicente
    • Categories Convex Optimization, Multi-Criteria Optimization, Stochastic Programming Tags , , ,

    Optimization of conflicting functions is of paramount importance in decision making, and real world applications frequently involve data that is uncertain or unknown, resulting in multi-objective optimization (MOO) problems of stochastic type. We study the stochastic multi-gradient (SMG) method, seen as an extension of the classical stochastic gradient method for single-objective optimization. At each iteration … Read more

    Optimal K-Thresholding Algorithms for Sparse Optimization Problems

  • Yun-Bin Zhao
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Data-Mining Tags , , , , ,

    The simulations indicate that the existing hard thresholding technique independent of the residual function may cause a dramatic increase or numerical oscillation of the residual. This inherit drawback of the hard thresholding renders the traditional thresholding algorithms unstable and thus generally inefficient for solving practical sparse optimization problems. How to overcome this weakness and develop … Read more

    Acceleration of SVRG and Katyusha X by Inexact Preconditioning

  • Fei Feng
  • Yanli Liu
  • Wotao Yin
    • Categories Convex Optimization, Stochastic Programming Tags , ,

    Empirical risk minimization is an important class of optimization problems with many popular machine learning applications, and stochastic variance reduction methods are popular choices for solving them. Among these methods, SVRG and Katyusha X (a Nesterov accelerated SVRG) achieve fast convergence without substantial memory requirement. In this paper, we propose to accelerate these two algorithms … Read more

    On the Relation between the Extended Supporting Hyperplane Algorithm and Kelley’s Cutting Plane Algorithm

  • Ambros Gleixner
  • Felipe Serrano
  • Robert Schwarz
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization Tags , ,

    Recently, Kronqvist et al.rediscovered the supporting hyperplane algorithm of Veinott and demonstrated its computational benefits for solving convex mixed-integer nonlinear programs. In this paper we derive the algorithm from a geometric point of view. This enables us to show that the supporting hyperplane algorithm is equivalent to Kelley’s cutting plane algorithm applied to a particular … Read more

    Variable smoothing for convex optimization problems using stochastic gradients

  • Axel Böhm
  • Radu Ioan Bot
    • Categories Convex Optimization, Stochastic Programming Tags , , ,

    We aim to solve a structured convex optimization problem, where a nonsmooth function is composed with a linear operator. When opting for full splitting schemes, usually, primal-dual type methods are employed as they are effective and also well studied. However, under the additional assumption of Lipschitz continuity of the nonsmooth function which is composed with … Read more

    Equivalences among the chi measure, Hoffman constant, and Renegar’s distance to ill-posedness

  • Javier F. Peña
  • Juan C. Vera
  • Luis F. Zuluaga
    • Categories Convex Optimization, Linear Programming, Polyhedra Tags , , , ,

    We show the equivalence among the following three condition measures of a full column rank matrix $A$: the chi measure, the signed Hoffman constant, and the signed distance to ill-posedness. The latter two measures are constructed via suitable collections of matrices obtained by flipping the signs of some rows of $A$. Our results provide a … Read more

    General Convergence Rates Follow From Specialized Rates Assuming Growth Bounds

  • Benjamin Grimmer
    • Categories Convex Optimization Tags , ,

    Often in the analysis of first-order methods, assuming the existence of a quadratic growth bound (a generalization of strong convexity) facilitates much stronger convergence analysis. Hence the analysis is done twice, once for the general case and once for the growth bounded case. We give a meta-theorem for deriving general convergence rates from those assuming … Read more

    Indefinite linearized augmented Lagrangian method for convex programming with linear inequality constraints

  • Bingsheng He
  • Shengjie Xu
  • Jing Yuan
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    The augmented Lagrangian method (ALM) is a benchmark for tackling the convex optimization problem with linear constraints; ALM and its variants for linearly equality-constrained convex minimization models have been well studied in the literatures. However, much less attention has been paid to ALM for efficiently solving the linearly inequality-constrained convex minimization model. In this paper, … Read more

    An Inexact Primal-Dual Smoothing Framework for Large-Scale Non-Bilinear Saddle Point Problems

  • William Haskell
  • Le Thi Khanh Hien
  • Renbo Zhao
    • Categories Convex Optimization Tags , , , ,

    We develop an inexact primal-dual first-order smoothing framework to solve a class of non-bilinear saddle point problems with primal strong convexity. Compared with existing methods, our framework yields a significant improvement over the primal oracle complexity, while it has competitive dual oracle complexity. In addition, we consider the situation where the primal-dual coupling term has … Read more

    New characterizations of Hoffman constants for systems of linear constraints

  • Javier F. Peña
  • Juan C. Vera
  • Luis F. Zuluaga
    • Categories Convex Optimization, Polyhedra Tags , ,

    We give a characterization of the Hoffman constant of a system of linear constraints in $\R^n$ relative to a reference polyhedron $R\subseteq\R^n$. The reference polyhedron $R$ represents constraints that are easy to satisfy such as box constraints. In the special case $R = \R^n$, we obtain a novel characterization of the classical Hoffman constant. More … Read more