Convex and Nonsmooth Optimization

Let’s Make Block Coordinate Descent Go Fast: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence

  • Issam Laradji
  • Mark Schmidt
  • Julie Nutini
    • Categories Convex and Nonsmooth Optimization Tags , ,

    Block coordinate descent (BCD) methods are widely-used for large-scale numerical optimization because of their cheap iteration costs, low memory requirements, amenability to parallelization, and ability to exploit problem structure. Three main algorithmic choices influence the performance of BCD methods: the block partitioning strategy, the block selection rule, and the block update rule. In this paper … Read more

    An Algorithm for Piecewise Linear Optimization of Objective Functions in Abs-normal Form

  • Andreas Griewank
  • Andrea Walther
    • Categories Nonsmooth Optimization Tags , , , , , , ,

    In the paper [11] we derived first order (KKT) and second order (SSC) optimality conditions for functions defined by evaluation programs involving smooth elementals and absolute values. For this class of problems we showed in [12] that the natural algorithm of successive piecewise linear optimization with a proximal term (SPLOP) achieves a linear or even … Read more

    Long-Step Path-Following Algorithm for Solving Symmetric Programming Problems with Nonlinear Objective Functions

  • Leonid Faybusovich
  • Cunlu Zhou
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    We describe a long-step path-following algorithm for a class of symmetric programming problems with nonlinear convex objective functions. The complexity estimates similar to the case of a linear-quadratic objective function are established. The results of numerical experiments for the class of optimization problems involving quantum entropy are presented. CitationPreprint, University of Notre Dame, December 2017ArticleDownload … Read more

    Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity

  • Benjamin Grimmer
    • Categories Convex Optimization Tags , ,

    We generalize the classic convergence rate theory for subgradient methods to apply to non-Lipschitz functions via a new measure of steepness. For the deterministic projected subgradient method, we derive a global $O(1/\sqrt{T})$ convergence rate for any function with at most exponential growth. Our approach implies generalizations of the standard convergence rates for gradient descent on … Read more

    ”Active-set complexity” of proximal gradient: How long does it take to find the sparsity pattern?

  • Warren Hare
  • Mark Schmidt
  • Julie Nutini
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , ,

    Proximal gradient methods have been found to be highly effective for solving minimization problems with non-negative constraints or L1-regularization. Under suitable nondegeneracy conditions, it is known that these algorithms identify the optimal sparsity pattern for these types of problems in a finite number of iterations. However, it is not known how many iterations this may … Read more

    Two-level value function approach to nonsmooth optimistic and pessimistic bilevel programs

  • Stephan Dempe
  • Boris S. Mordukhovich
  • Alain Zemkoho
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    The authors’ paper in Ref. [5], was the first one to provide detailed optimality conditions for pessimistic bilevel optimization. The results there were based on the concept of the two-level optimal value function introduced and analyzed in Ref. [4], for the case of optimistic bilevel programs. One of the basic assumptions in both of these … Read more

    Iteration complexity of an inexact Douglas-Rachford method and of a Douglas-Rachford-Tseng’s F-B four-operator splitting method for solving monotone inclusions

  • M. Marques Alves
  • Marina Geremia
    • Categories Convex and Nonsmooth Optimization

    In this paper, we propose and study the iteration complexity of an inexact Douglas-Rachford splitting (DRS) method and a Douglas-Rachford-Tseng’s forward-backward (F-B) splitting method for solving two-operator and four-operator monotone inclusions, respectively. The former method (although based on a slightly different mechanism of iteration) is motivated by the recent work of J. Eckstein and W. … Read more

    Linear Convergence Rate of the Generalized Alternating Direction Method of Multipliers for a Class of Convex Optimization Problems

  • Peng Jian-Wen
  • Xue-Qing Zhang
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    Rencently, the generalized aternating direction method of multipliers (GADMM) proposed by Eckstein and Bertsekas has received intensive attention from a broad spectrum of areas. In this paper, we consider the convergence rate of GADMM when applying to the convex optimization problems that the subdifferentials of the underlying functions are piecewise linear multifunctions, including LASSO, a … Read more

    Random Gradient Extrapolation for Distributed and Stochastic Optimization

  • Guanghui Lan
  • Yi Zhou
    • Categories Convex Optimization, Stochastic Programming Tags , , , ,

    In this paper, we consider a class of finite-sum convex optimization problems defined over a distributed multiagent network with $m$ agents connected to a central server. In particular, the objective function consists of the average of $m$ ($\ge 1$) smooth components associated with each network agent together with a strongly convex term. Our major contribution … Read more

    Bootstrap Robust Prescriptive Analytics

  • Dimitris Bertsimas
  • Bart Paul Gerard van Parys
    • Categories Convex Optimization, Robust Optimization, Statistics Tags , , , ,

    We address the problem of prescribing an optimal decision in a framework where its cost depends on uncertain problem parameters $Y$ that need to be learned from data. Earlier work by Bertsimas and Kallus (2014) transforms classical machine learning methods that merely predict $Y$ from supervised training data $[(x_1, y_1), \dots, (x_n, y_n)]$ into prescriptive … Read more