Convex Optimization

Understanding the Convergence of the Alternating Direction Method of Multipliers: Theoretical and Computational Perspectives

  • Jonathan Eckstein
  • Wang Yao
    • Categories Convex Optimization Tags ,

    The alternating direction of multipliers (ADMM) is a form of augmented Lagrangian algorithm that has experienced a renaissance in recent years due to its applicability to optimization problems arising from “big data” and image processing applications, and the relative ease with which it may be implemented in parallel and distributed computational environments. While it is … Read more

    ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates

  • Zhimin Peng
  • Yangyang Xu
  • Ming Yan
  • Wotao Yin
    • Categories Convex Optimization, Nonsmooth Optimization, Parallel Algorithms Tags , , , , ,

    We propose ARock, an asynchronous parallel algorithmic framework for finding a fixed point to a nonexpansive operator. In the framework, a set of agents (machines, processors, or cores) update a sequence of randomly selected coordinates of the unknown variable in an asynchronous parallel fashion. As special cases of ARock, novel algorithms for linear systems, convex … Read more

    A Bundle Method for Exploiting Additive Structure in Difficult Optimization Problems

  • Welington de Oliveira
  • Jonathan Eckstein
    • Categories Convex Optimization, Nonsmooth Optimization

    This paper describes a bundle method for (approximately) minimizing complicated nonsmooth convex functions with additive structure, with the primary goal of computing bounds on the solution values of difficult optimization problems such as stochastic integer programs. The method combines features that have appeared in previously proposed bundle methods, but not in the particular configuration we … 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

    $\varepsilon- Subdifferential of Set-valued Map and Its Application

  • Yu Li
    • Categories Convex Optimization

    In this paper, firstly, the concept of $\varepsilon-$strictly efficient subdifferential for set-valued map is introduced in Hausdorff locally convex topological vector spaces. Secondly, a characterization of this subdifferential by scalarization and the generalized $\varepsilon-$ Moreau-Rockafellar type theorem for set-valued maps are established. Finally, the necessary optimality condition of the constraint set-valued optimization problem for $\varepsilon-$ … Read more

    Solving nonsmooth convex optimization with complexity (\eps^{-1/2})$

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

    This paper describes an algorithm for solving structured nonsmooth convex optimization problems using OSGA, a first-order method with the complexity $O(\eps^{-2})$ for Lipschitz continuous nonsmooth problems and $O(\eps^{-1/2})$ for smooth problems with Lipschitz continuous gradient. If the nonsmoothness of the problem is manifested in a structured way, we reformulate the problem in a form that … 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

    Some Applications of Polynomial Optimization in Operations Research and Real-Time Decision Making

  • Amir Ali Ahmadi
  • Anirudha Majumdar
    • Categories Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We demonstrate applications of algebraic techniques that optimize and certify polynomial inequalities to problems of interest in the operations research and transportation engineering communities. Three problems are considered: (i) wireless coverage of targeted geographical regions with guaranteed signal quality and minimum transmission power, (ii) computing real-time certificates of collision avoidance for a simple model of … Read more

    Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functions

  • Amir Beck
  • Shimrit Shtern
    • Categories Convex Optimization

    We consider the problem of minimizing a function, which is the sum of a linear function and a composition of a strongly convex function with a linear transformation, over a compact polyhedral set. Jaggi and Lacoste-Julien [14] showed that the conditional gradient method with away steps employed on the aforementioned problem without the additional linear … Read more

    Distributed Gradient Methods with Variable Number of Working Nodes

  • Dragana Bajović
  • Dušan Jakovetić
  • Nataša Krejić
  • Nataša Krklec Jerinkić
    • Categories Convex Optimization, Network Optimization Tags , , , ,

    We consider distributed optimization where $N$ nodes in a connected network minimize the sum of their local costs subject to a common constraint set. We propose a distributed projected gradient method where each node, at each iteration $k$, performs an update (is active) with probability $p_k$, and stays idle (is inactive) with probability $1-p_k$. Whenever … Read more