Convex and Nonsmooth Optimization

Manifold Identification for Ultimately Communication-Efficient Distributed Optimization

  • Wei-Lin Chiang
  • Yu-Sheng Li
  • Ching-pei Lee
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Parallel Algorithms Tags , , ,

    This work proposes a progressive manifold identification approach for distributed optimization with sound theoretical justifications to greatly reduce both the rounds of communication and the bytes communicated per round for partly-smooth regularized problems such as the $\ell_1$- and group-LASSO-regularized ones. Our two-stage method first uses an inexact proximal quasi-Newton method to iteratively identify a sequence … Read more

    An inexact version of the symmetric proximal ADMM for solving separable convex optimization

  • Vando A. Adona
  • Max L. N. Gonçalves
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    In this paper, we propose and analyze an inexact version of the symmetric proximal alternating direction method of multipliers (ADMM) for solving linearly constrained optimization problems. Basically, the method allows its first subproblem to be solved inexactly in such way that a relative approximate criterion is satisfied. In terms of the iteration number $k$, we … Read more

    An Alternative Perspective on Copositive and Convex Relaxations of Nonconvex Quadratic Programs

  • E. Alper Yildirim
    • Categories Convex Optimization, Global Optimization Tags , , ,

    We study convex relaxations of nonconvex quadratic programs. We identify a family of so-called feasibility preserving convex relaxations, which includes the well-known copositive and doubly nonnegative relaxations, with the property that the convex relaxation is feasible if and only if the nonconvex quadratic program is feasible. We observe that each convex relaxation in this family … Read more

    Two novel gradient methods with optimal step sizes

  • Oscar S. Dalmau
  • Rafael Herrera
  • Harry Oviedo
    • Categories Convex Optimization, Nonlinear Optimization Tags , , ,

    In this work we introduce two new Barzilai and Borwein-like steps sizes for the classical gradient method for strictly convex quadratic optimization problems. The proposed step sizes employ second-order information in order to obtain faster gradient-type methods. Both step sizes are derived from two unconstrained optimization models that involve approximate information of the Hessian of … Read more

    Gradient Sampling Methods with Inexact Subproblem Solves and Gradient Aggregation

  • Frank E. Curtis
  • Minhan Li
    • Categories Nonsmooth Optimization Tags , , , ,

    Gradient sampling (GS) has proved to be an effective methodology for the minimization of objective functions that may be nonconvex and/or nonsmooth. The most computationally expensive component of a contemporary GS method is the need to solve a convex quadratic subproblem in each iteration. In this paper, a strategy is proposed that allows the use … Read more

    The Equivalence of Fourier-based and Wasserstein Metrics on Imaging Problems

  • Gennaro Auricchio
  • Stefano Gualandi
  • Giuseppe Toscani
  • Andrea Codegoni
  • Marco Veneroni
    • Categories Convex and Nonsmooth Optimization, Linear Programming, Network Optimization

    We investigate properties of some extensions of a class of Fourier-based probability metrics, originally introduced to study convergence to equilibrium for the solution to the spatially homogeneous Boltzmann equation. At difference with the original one, the new Fourier-based metrics are well-defined also for probability distributions with different centers of mass, and for discrete probability measures … Read more

    Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step

  • Jalal Fadili
  • Antonio Silveti-Falls
  • Cesare Molinari
    • Categories Convex and Nonsmooth Optimization, Semi-definite Programming, Stochastic Programming

    In this paper we propose and analyze inexact and stochastic versions of the CGALP algorithm developed in the authors’ previous paper, which we denote ICGALP, that allows for errors in the computation of several important quantities. In particular this allows one to compute some gradients, proximal terms, and/or linear minimization oracles in an inexact fashion … Read more

    Decomposition Algorithms for Some Deterministic and Two-Stage Stochastic Single-Leader Multi-Follower Games

  • Pedro Borges de Melo
  • Claudia Sagastizábal
  • Mikhail V. Solodov
    • Categories Complementarity and Variational Inequalities, Nonsmooth Optimization, Stochastic Programming Tags , , , , ,

    We consider a certain class of hierarchical decision problems that can be viewed as single-leader multi-follower games, and be represented by a virtual market coordinator trying to set a price system for traded goods, according to some criterion that balances supply and demand. The objective function of the market coordinator involves the decisions of many … Read more

    On Inexact Accelerated Proximal Gradient Methods with Relative Error Rules

  • Yunier Bello-Cruz
  • Max L. N. Gonçalves
  • Nathan Krislock
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , ,

    One of the most popular and important first-order iterations that provides optimal complexity of the classical proximal gradient method (PGM) is the “Fast Iterative Shrinkage/Thresholding Algorithm” (FISTA). In this paper, two inexact versions of FISTA for minimizing the sum of two convex functions are studied. The proposed schemes inexactly solve their subproblems by using relative … Read more

    Towards practical generic conic optimization

  • Chris Coey
  • Juan Pablo Vielma
  • Lea Kapelevich
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , ,

    Many convex optimization problems can be represented through conic extended formulations with auxiliary variables and constraints using only the small number of standard cones recognized by advanced conic solvers such as MOSEK 9. Such extended formulations are often significantly larger and more complex than equivalent conic natural formulations, which can use a much broader class … Read more