convex optimization

An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization

  • Arda Aytekin
  • Hamid Reza Feyzmahdavian
  • Mikael Johansson
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    Mini-batch optimization has proven to be a powerful paradigm for large-scale learning. However, the state of the art parallel mini-batch algorithms assume synchronous operation or cyclic update orders. When worker nodes are heterogeneous (due to different computational capabilities or different communication delays), synchronous and cyclic operations are inefficient since they will leave workers idle waiting … Read more

    On the Step Size of Symmetric Alternating Directions Method of Multipliers

  • Bingsheng He
  • Feng Ma
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , ,

    The alternating direction method of multipliers (ADMM) is an application of the Douglas-Rachford splitting method; and the symmetric version of ADMM which updates the Lagrange multiplier twice at each iteration is an application of the Peaceman-Rachford splitting method. Sometimes the symmetric ADMM works empirically; but theoretically its convergence is not guaranteed. It was recently found … Read more

    Global Convergence of Unmodified 3-Block ADMM for a Class of Convex Minimization Problems

  • Tianyi Lin
  • Shiqian Ma
  • Shuzhong Zhang
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    The alternating direction method of multipliers (ADMM) has been successfully applied to solve structured convex optimization problems due to its superior practical performance. The convergence properties of the 2-block ADMM have been studied extensively in the literature. Specifically, it has been proven that the 2-block ADMM globally converges for any penalty parameter $\gamma>0$. In this … Read more

    First-Order Algorithms for Convex Optimization with Nonseparate Objective and Coupled Constraints

  • Xiang Gao
  • Shuzhong Zhang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    In this paper we consider a block-structured convex optimization model, where in the objective the block-variables are nonseparable and they are further linearly coupled in the constraint. For the 2-block case, we propose a number of first-order algorithms to solve this model. First, the alternating direction method of multipliers (ADMM) is extended, assuming that it … Read more

    Distributionally robust expectation inequalities for structured distributions

  • Paul J. Goulart
  • Bart Paul Gerard Van Parys
  • Manfred Morari
    • Categories Convex Optimization, Semi-definite Programming, Stochastic Programming Tags , , ,

    Quantifying the risk of unfortunate events occurring, despite limited distributional information, is a basic problem underlying many practical questions. Indeed, quantifying constraint violation probabilities in distributionally robust programming or judging the risk of financial positions can both be seen to involve risk quantification, notwithstanding distributional ambiguity. In this work we discuss worst-case probability and conditional … Read more

    An O(1/k) Convergence Rate for the Variable Stepsize Bregman Operator Splitting Algorithm

  • William W. Hager
  • Maryam Yashtini
  • Hongchao Zhang
    • Categories Nonsmooth Optimization Tags , , , , ,

    An earlier paper proved the convergence of a variable stepsize Bregman operator splitting algorithm (BOSVS) for minimizing $\phi(Bu)+H(u)$ where $H$ and $\phi$ are convex functions, and $\phi$ is possibly nonsmooth. The algorithm was shown to be relatively efficient when applied to partially parallel magnetic resonance image reconstruction problems. In this paper, the convergence rate of … Read more

    Convergence rates for forward-backward dynamical systems associated with strongly monotone inclusions

  • Radu Ioan Bot
  • Ernö Robert Csetnek
    • Categories Convex Optimization, Nonsmooth Optimization, Systems governed by Differential Equations Optimization Tags , , , ,

    We investigate the convergence rates of the trajectories generated by implicit first and second order dynamical systems associated to the determination of the zeros of the sum of a maximally monotone operator and a monotone and Lipschitz continuous one in a real Hilbert space. We show that these trajectories strongly converge with exponential rate to … Read more

    An optimal subgradient algorithm with subspace search for costly convex optimization problems

  • Masoud Ahookhosh
  • Arnold Neumaier
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , , , ,

    This paper presents an acceleration of the optimal subgradient algorithm OSGA \cite{NeuO} for solving convex optimization problems, where the objective function involves costly affine and cheap nonlinear terms. We combine OSGA with a multidimensional subspace search technique, which leads to low-dimensional problem that can be solved efficiently. Numerical results concerning some applications are reported. A … Read more

    A forward-backward-forward differential equation and its asymptotic properties

  • Sebastian Banert
  • Radu Ioan Bot
    • Categories Convex Optimization, Dynamic Programming, Nonsmooth Optimization Tags , , , ,

    In this paper, we approach the problem of finding the zeros of the sum of a maximally monotone operator and a monotone and Lipschitz continuous one in a real Hilbert space via an implicit forward-backward-forward dynamical system with nonconstant relaxation parameters and stepsizes of the resolvents. Besides proving existence and uniqueness of strong global solutions … Read more

    A polynomial-time descent method for separable convex optimization problems with linear constraints

  • Sergei Chubanov
    • Categories Convex and Nonsmooth Optimization Tags ,

    We propose a polynomial algorithm for a separable convex optimization problem with linear constraints. We do not make any additional assumptions about the structure of the objective function except for polynomial computability. That is, the objective function can be non-differentiable. The running time of our algorithm is polynomial in the the size of the input … Read more