Convex Optimization

Hypotheses testing on the optimal values of several risk-neutral or risk-averse convex stochastic programs and application to hypotheses testing on several risk measure values

  • Vincent Guigues
    • Categories Convex Optimization, Stochastic Programming

    Given an arbitrary number of risk-averse or risk-neutral convex stochastic programs, we study hypotheses testing problems aiming at comparing the optimal values of these stochastic programs on the basis of samples of the underlying random vectors. We propose non-asymptotic tests based on confidence intervals on the optimal values of the stochastic programs obtained using the … Read more

    Local Linear Convergence of Forward–Backward under Partial Smoothness

  • Jalal Fadili
  • Jingwei Liang
  • Gabriel Peyré
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , ,

    In this paper, we consider the Forward–Backward proximal splitting algorithm to minimize the sum of two proper closed convex functions, one of which having a Lipschitz–continuous gradient and the other being partly smooth relatively to an active manifold $\mathcal{M}$. We propose a unified framework in which we show that the Forward–Backward (i) correctly identifies the … Read more

    Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions

  • Damek Davis
  • Wotao Yin
    • Categories Convex Optimization Tags , , , , ,

    Splitting schemes are a class of powerful algorithms that solve complicated monotone inclusion and convex optimization problems that are built from many simpler pieces. They give rise to algorithms in which the simple pieces of the decomposition are processed individually. This leads to easily implementable and highly parallelizable algorithms, which often obtain nearly state-of-the-art performance. … Read more

    A Class of Randomized Primal-Dual Algorithms for Distributed Optimization

  • Jean-Christophe Pesquet
  • Audrey Repetti
    • Categories Convex Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , , , ,

    Based on a preconditioned version of the randomized block-coordinate forward-backward algorithm recently proposed in [Combettes,Pesquet,2014], several variants of block-coordinate primal-dual algorithms are designed in order to solve a wide array of monotone inclusion problems. These methods rely on a sweep of blocks of variables which are activated at each iteration according to a random rule, … Read more

    Playing with Duality: An Overview of Recent Primal-Dual Approaches for Solving Large-Scale Optimization Problems

  • Nikos Komodakis
  • Jean-Christophe Pesquet
    • Categories Applications - Science and Engineering, Convex Optimization, Integer Programming Tags , , , , , , , ,

    Optimization methods are at the core of many problems in signal/image processing, computer vision, and machine learning. For a long time, it has been recognized that looking at the dual of an optimization problem may drastically simplify its solution. Deriving efficient strategies which jointly brings into play the primal and the dual problems is however … Read more

    Gradient Sliding for Composite Optimization

  • Guanghui Lan
    • Categories Convex Optimization Tags , , , ,

    We consider in this paper a class of composite optimization problems whose objective function is given by the summation of a general smooth and nonsmooth component, together with a relatively simple nonsmooth term. We present a new class of first-order methods, namely the gradient sliding algorithms, which can skip the computation of the gradient for … Read more

    A proximal multiplier method for separable convex minimization

  • Paulo Roberto Oliveira
  • Erik Alex Papa Quiroz
  • Orlando Sarmiento
    • Categories Convex Optimization, Nonlinear Optimization, Nonsmooth Optimization

    In this paper, we propose an inexact proximal multiplier method using proximal distances for solving convex minimization problems with a separable structure. The proposed method unified the work of Chen and Teboulle (PCPM method), Kyono and Fukushima (NPCPMM) and Auslender and Teboulle (EPDM) and extends the convergence properties for a class of phi-divergence distances. We … Read more

    Calmness of linear programs under perturbations of all data: characterization and modulus

  • M.J. Cánovas
  • Abderrahim Hantoute
  • J. Parra
  • F.J. Toledo
    • Categories Complementarity and Variational Inequalities, Convex Optimization, Linear Programming Tags , , ,

    This paper provides operative point-based formulas (only involving the nominal data, and not data in a neighborhood) for computing or estimating the calmness modulus of the optimal set (argmin) mapping in linear optimization under uniqueness of nominal optimal solutions. Our analysis is developed in two different parametric settings. First, in the framework of canonical perturbations … Read more

    Application of the Strictly Contractive Peaceman-Rachford Splitting Method to Multi-block Separable Convex Programming

  • Bingsheng He
  • Xiao-Ming Yuan
  • Han Liu
  • Junwei Lu
    • Categories Convex Optimization Tags , , , , ,

    Recently, a strictly contractive Peaceman- Rachford splitting method (SC-PRSM) was proposed to solve a convex minimization model with linear constraints and a separable objective function which is the sum of two functions without coupled variables. We show by an example that the SC-PRSM cannot be directly extended to the case where the objective function is … Read more

    Coordinate shadows of semi-definite and Euclidean distance matrices

  • Dmitriy Drusvyatskiy
  • Gabor Pataki
  • Henry Wolkowicz
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , , ,

    We consider the projected semi-definite and Euclidean distance cones onto a subset of the matrix entries. These two sets are precisely the input data defining feasible semi-definite and Euclidean distance completion problems. We characterize when these sets are closed, and use the boundary structure of these two sets to elucidate the Krislock-Wolkowicz facial reduction algorithm. … Read more