Month: November 2017

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

    An algorithm for binary chance-constrained problems using IIS

  • Gianpiero Canessa
  • Lewis Ntaimo
  • Bernardo K. Pagnoncelli
  • Julián Gallego
    • Categories 0-1 Programming, Stochastic Programming

    We propose an algorithm based on infeasible irreducible subsystems (IIS) to solve general binary chance-constrained problems. By leverag- ing on the problem structure we are able to generate good quality upper bounds to the optimal value early in the algorithm, and the discrete do- main is used to guide us eciently in the search of … 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

    Efficient Convex Optimization for Linear MPC

  • Stephen Wright
    • Categories Control Applications, Quadratic Programming Tags ,

    Model predictive control (MPC) formulations with linear dynamics and quadratic objectives can be solved efficiently by using a primal-dual interior-point framework, with complexity proportional to the length of the horizon. An alternative, which is more able to exploit the similarity of the problems that are solved at each decision point of linear MPC, is to … Read more

    On global minimizers of quadratic functions with cubic regularization

  • Andrea Cristofari
  • Stefano Lucidi
  • Tayebeh Dehghan Niri
    • Categories Unconstrained Optimization

    In this paper, we analyze some theoretical properties of the problem of minimizing a quadratic function with a cubic regularization term, arising in many methods for unconstrained and constrained optimization that have been proposed in the last years. First we show that, given any stationary point that is not a global solution, it is possible … 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

    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

    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

    Crowd-based City Logistics

  • Afonso Sampaio
  • Martin Savelsbergh
  • Lucas Veelenturf
  • Tom Van Woensel
    • Categories Applications - OR and Management Sciences, Production and Logistics, Transportation Tags , , , , ,

    Cities are drivers of economic development, providing infrastructure to support countless activities and services. Today, the world’s 750 biggest cities account for more than 57% of the global GDP and this number is expected to increase to 61% by 2030. More than half of the world’s population lives in cities, or urban areas, and this … Read more