Convex and Nonsmooth Optimization

A BFGS-SQP Method for Nonsmooth, Nonconvex, Constrained Optimization and its Evaluation using Relative Minimization Profiles

  • Frank E. Curtis
  • Tim Mitchell
  • Michael L. Overton
    • Categories Control Applications, Nonsmooth Optimization, Optimization Software Benchmark

    We propose an algorithm for solving nonsmooth, nonconvex, constrained optimization problems as well as a new set of visualization tools for comparing the performance of optimization algorithms. Our algorithm is a sequential quadratic optimization method that employs Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton Hessian approximations and an exact penalty function whose parameter is controlled using a steering strategy. … Read more

    Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming

  • Minghui Liu
  • Gabor Pataki
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming

    We describe simple and exact duals, and certificates of infeasibility and weak infeasibility in conic linear programming which do not rely on any constraint qualification, and retain most of the simplicity of the Lagrange dual. In particular, some of our infeasibility certificates generalize the row echelon form of a linear system of equations, and the … Read more

    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 semi-proximal-based strictly contractive Peaceman-Rachford splitting method

  • Yan Gu
  • Deren Han
  • Bo Jiang
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    The Peaceman-Rachford splitting method is very efficient for minimizing sum of two functions each depends on its variable, and the constraint is a linear equality. However, its convergence was not guaranteed without extra requirements. Very recently, He et al. (SIAM J. Optim. 24: 1011 – 1040, 2014) proved the convergence of a strictly contractive Peaceman-Rachford … Read more

    Existence Results for Particular Instances of the Vector Quasi-Equilibrium Problem on Hadamard Manifolds

  • Glaydston Bento
  • João Xavier da Cruz Neto
    • Categories Generalized Convexity/Monoticity

    We show the validity of select existence results for a vector optimization problem, and a variational inequality. More generally, we consider generalized vector quasi-variational inequalities, as well as, fixed point problems on genuine Hadamard manifolds. ArticleDownload View PDF

    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

    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

    Probabilistic optimization via approximate p-efficient points and bundle methods

  • V. Berge
  • Welington de Oliveira
  • Claudia Sagastizábal
  • Wim van Ackooij
    • Categories Convex and Nonsmooth Optimization, Stochastic Programming

    For problems when decisions are taken prior to observing the realization of underlying random events, probabilistic constraints are an important modelling tool if reliability is a concern. A key concept to numerically dealing with probabilistic constraints is that of p-efficient points. By adopting a dual point of view, we develop a solution framework that includes … 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