Convex Optimization

Iteration complexity on the Generalized Peaceman-Rachford splitting method for separable convex programming

  • Peng Jian-Wen
  • Xue-Qing Zhang
    • Categories Convex Optimization

    Recently, a generalized version of Peaceman-Rachford splitting method (GPRSM) for solving a convex minmization model with a general separable structure has been proposed by \textbf{Sun} et al and its global convergence has been proved. In this paper, we further study theoretical aspects of the generalized Peaceman-Rachford splitting method. We first establish the worst-case $\mathcal{O}(1/t)$ convergence … Read more

    Inexact cuts for Deterministic and Stochastic Dual Dynamic Programming applied to convex nonlinear optimization problems

  • Vincent Guigues
    • Categories Convex Optimization, Dynamic Programming, Stochastic Programming

    We introduce an extension of Dual Dynamic Programming (DDP) to solve convex nonlinear dynamic programming equations. We call Inexact DDP (IDDP) this extension which applies to situations where some or all primal and dual subproblems to be solved along the iterations of the method are solved with a bounded error. We show that any accumulation … Read more

    A faster dual algorithm for the Euclidean minimum covering ball problem

  • Farid Alizadeh
  • Marta Cavaleiro
    • Categories Convex Optimization Tags , , , ,

    Dearing and Zeck presented a dual algorithm for the problem of the minimum covering ball in $\mathbb{R}^n$. Each iteration of their algorithm has a computational complexity of at least $\mathcal O(n^3)$. In this paper we propose a modification to their algorithm that, together with an implementation that uses updates to the QR factorization of a … Read more

    Chambolle-Pock and Tseng’s methods: relationship and extension to the bilevel optimization

  • Yura Malitsky
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , ,

    In the first part of the paper we focus on two problems: (a) regularized least squares and (b) nonsmooth minimization over an affine subspace. For these problems we establish the connection between the primal-dual method of Chambolle-Pock and Tseng’s proximal gradient method. For problem (a) it allows us to derive a nonergodic $O(1/k^2)$ convergence rate … Read more

    On Glowinski’s Open Question of Alternating Direction Method of Multipliers

  • Tao Min
  • Xiao-Ming Yuan
    • Categories Applications - OR and Management Sciences, Convex Optimization Tags , , , ,

    The alternating direction method of multipliers (ADMM) was proposed by Glowinski and Marrocco in 1975; and it has been widely used in a broad spectrum of areas, especially in some sparsity-driven application domains. In 1982, Fortin and Glowinski suggested to enlarge the range of the step size for updating the dual variable in ADMM from … Read more

    Distributed Block-diagonal Approximation Methods for Regularized Empirical Risk Minimization

  • Kai-Wei Chang
  • Ching-pei Lee
    • Categories Convex Optimization, Nonsmooth Optimization Tags , ,

    Designing distributed algorithms for empirical risk minimization (ERM) has become an active research topic in recent years because of the practical need to deal with the huge volume of data. In this paper, we propose a general framework for training an ERM model via solving its dual problem in parallel over multiple machines. Our method … Read more

    Infeasibility detection in the alternating direction method of multipliers for convex optimization

  • Goran Banjac
  • Stephen Boyd
  • Paul J. Goulart
  • Bartolomeo Stellato
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    The alternating direction method of multipliers is a powerful operator splitting technique for solving structured optimization problems. For convex optimization problems, it is well-known that the algorithm generates iterates that converge to a solution, provided that it exists. If a solution does not exist, then the iterates diverge. Nevertheless, we show that they yield conclusive … Read more

    Regularized Nonlinear Acceleration

  • Francis Bach
  • Alexandre d'Aspremont
  • Damien Scieur
    • Categories Convex Optimization

    We describe a convergence acceleration technique for generic optimization problems. Our scheme computes estimates of the optimum from a nonlinear average of the iterates produced by any optimization method. The weights in this average are computed via a simple linear system, whose solution can be updated online. This acceleration scheme runs in parallel to the … Read more

    Sharpness, Restart and Acceleration.

  • Alexandre d'Aspremont
  • Vincent Roulet
    • Categories Convex Optimization

    The Lojasievicz inequality shows that sharpness bounds on the minimum of convex optimization problems hold almost generically. Here, we show that sharpness directly controls the performance of restart schemes. The constants quantifying sharpness are of course unobservable, but we show that optimal restart strategies are fairly robust, and searching for the best scheme only increases … Read more

    Integration Methods and Accelerated Optimization Algorithms

  • Francis Bach
  • Alexandre d'Aspremont
  • Vincent Roulet
  • Damien Scieur
    • Categories Convex Optimization

    We show that accelerated optimization methods can be seen as particular instances of multi-step integration schemes from numerical analysis, applied to the gradient flow equation. In comparison with recent advances in this vein, the differential equation considered here is the basic gradient flow and we show that multi-step schemes allow integration of this differential equation … Read more