Convex Optimization

Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods

  • François Glineur
  • Julien M. Hendrickx
  • Adrien B. Taylor
    • Categories Convex Optimization Tags , , ,

    We show that the exact worst-case performance of fixed-step first-order methods for unconstrained optimization of smooth (possibly strongly) convex functions can be obtained by solving convex programs. Finding the worst-case performance of a black-box first-order method is formulated as an optimization problem over a set of smooth (strongly) convex functions and initial conditions. We develop … Read more

    A corrected semi-proximal ADMM for multi-block convex optimization and its application to DNN-SDPs

  • Shaohua Pan
  • Li Shen
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper we propose a corrected semi-proximal ADMM (alternating direction method of multipliers) for the general $p$-block $(p\!\ge 3)$ convex optimization problems with linear constraints, aiming to resolve the dilemma that almost all the existing modified versions of the directly extended ADMM, although with convergent guarantee, often perform substantially worse than the directly extended … Read more

    A note on the ergodic convergence of symmetric alternating proximal gradient method

  • Bin Gao
    • Categories Convex Optimization, Global Optimization

    We consider the alternating proximal gradient method (APGM) proposed to solve a convex minimization model with linear constraints and separable objective function which is the sum of two functions without coupled variables. Inspired by Peaceman-Rachford splitting method (PRSM), a nature idea is to extend APGM to the symmetric alternating proximal gradient method (SAPGM), which can … Read more

    ADMM for Convex Quadratic Programs: Linear Convergence and Infeasibility Detection

  • Stefano Di Cairano
  • Arvind U. Raghunathan
    • Categories Convex Optimization, Quadratic Programming Tags , , ,

    In this paper, we analyze the convergence of Alternating Direction Method of Multipliers (ADMM) on convex quadratic programs (QPs) with linear equality and bound constraints. The ADMM formulation alternates between an equality constrained QP and a projection on the bounds. Under the assumptions of: (i) positive definiteness of the Hessian of the objective projected on … Read more

    Looking for strong polynomiality in Linear Programming : Arguments, conjectures, experiments, findings, and conclusion.

  • Peter A. Bruijs
    • Categories Convex Optimization, Linear Programming

    Until now it has been an open question whether the Linear Programming (LP) problem can be solved in strong polynomial time. The simplex algorithm with its combinatorial nature does not even offer a polynomial bound, whereas the complexity of the polynomial algorithms by Khachiyan and Karmarkar is based on the number of variables n, and … Read more

    An optimal subgradient algorithm for large-scale bound-constrained convex optimization

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

    This paper shows that the OSGA algorithm — which uses first-order information to solve convex optimization problems with optimal complexity — can be used to efficiently solve arbitrary bound-constrained convex optimization problems. This is done by constructing an explicit method as well as an inexact scheme for solving the bound-constrained rational subproblem required by OSGA. … Read more

    An optimal subgradient algorithm for large-scale convex optimization in simple domains

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

    This paper shows that the optimal subgradient algorithm, OSGA, proposed in \cite{NeuO} can be used for solving structured large-scale convex constrained optimization problems. Only first-order information is required, and the optimal complexity bounds for both smooth and nonsmooth problems are attained. More specifically, we consider two classes of problems: (i) a convex objective with a … Read more

    Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss

  • Lin Xiao
  • Yuchen Zhang
    • Categories Convex Optimization, Statistics Tags , , , ,

    We consider distributed convex optimization problems originated from sample average approximation of stochastic optimization, or empirical risk minimization in machine learning. We assume that each machine in the distributed computing system has access to a local empirical loss function, constructed with i.i.d. data sampled from a common distribution. We propose a communication-efficient distributed algorithm to … Read more

    Global convergence of the Heavy-ball method for convex optimization

  • Hamid Reza Feyzmahdavian
  • Euhanna Ghadimi
  • Mikael Johansson
    • Categories Convex Optimization, Unconstrained Optimization Tags , , , , ,

    This paper establishes global convergence and provides global bounds of the convergence rate of the Heavy-ball method for convex optimization problems. When the objective function has Lipschitz-continuous gradient, we show that the Cesa ́ro average of the iterates converges to the optimum at a rate of $O(1/k)$ where k is the number of iterations. When … Read more

    Activity Identification and Local Linear Convergence of Douglas-Rachford/ADMM under Partial Smoothness

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

    Proximal splitting algorithms are becoming popular to solve convex optimization problems in variational image processing. Within this class, Douglas-Rachford (DR) and ADMM are designed to minimize the sum of two proper lower semicontinuous convex functions whose proximity operators are easy to compute. The goal of this work is to understand the local convergence behaviour of … Read more