Convex and Nonsmooth Optimization

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

    Amenable cones: error bounds without constraint qualifications

  • Bruno F. Lourenço
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We provide a framework for obtaining error bounds for linear conic problems without assuming constraint qualifications or regularity conditions. The key aspects of our approach are the notions of amenable cones and facial residual functions. For amenable cones, it is shown that error bounds can be expressed as a composition of facial residual functions. The … Read more

    Analysis of the Gradient Method with an Armijo-Wolfe Line Search on a Class of Nonsmooth Convex Functions

  • Azam Asl
  • Michael L. Overton
    • Categories Convex and Nonsmooth Optimization Tags , ,

    It has long been known that the gradient (steepest descent) method may fail on nonsmooth problems, but the examples that have appeared in the literature are either devised specifically to defeat a gradient or subgradient method with an exact line search or are unstable with respect to perturbation of the initial point. We give an … 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

    Uniqueness of Market Equilibria on Networks with Transport Costs

  • Vanessa Krebs
  • Martin Schmidt
    • Categories Applications - OR and Management Sciences, Convex and Nonsmooth Optimization, Network Optimization Tags , , , ,

    We study the existence and uniqueness of equilibria for perfectly competitive markets in capacitated transport networks. The model under consideration is rather general so that it captures basic aspects of related models in, e.g., gas or electricity networks. We formulate the market equilibrium model as a mixed complementarity problem and show the equivalence to a … Read more