Month: December 2021

Graph topology invariant gradient and sampling complexity for decentralized and stochastic optimization

  • Guanghui Lan
  • Yuyuan Ouyang
  • Yi Zhou
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Stochastic Programming Tags , , ,

    One fundamental problem in decentralized multi-agent optimization is the trade-off between gradient/sampling complexity and communication complexity. We propose new algorithms whose gradient and sampling complexities are graph topology invariant, while their communication complexities remain optimal. For convex smooth deterministic problems, we propose a primal dual sliding (PDS) algorithm that computes an $\epsilon$-solution with $O((\tilde{L}/\epsilon)^{1/2})$ gradient … Read more

    Optimal Robust Policy for Feature-Based Newsvendor

  • Luhao Zhang
  • Jincheng Yang
  • Rui Gao
    • Categories Infinite Dimensional Optimization, Robust Optimization, Supply Chain Management Tags , , ,

    We study policy optimization for the feature-based newsvendor, which seeks an end-to-end policy that renders an explicit mapping from features to ordering decisions. Unlike existing works that restrict the policies to some parametric class which may suffer from sub-optimality (such as affine class) or lack of interpretability (such as neural networks), we aim to optimize … Read more

    Affine invariant convergence rates of the conditional gradient method

  • Javier F. Peña
    • Categories Convex Optimization Tags , , ,

    We show that the conditional gradient method for the convex composite problem \[\min_x\{f(x) + \Psi(x)\}\] generates primal and dual iterates with a duality gap converging to zero provided a suitable growth property holds and the algorithm makes a judicious choice of stepsizes. The rate of convergence of the duality gap to zero ranges from sublinear … Read more

    Worst-Case Complexity of an SQP Method for Nonlinear Equality Constrained Stochastic Optimization

  • Frank E. Curtis
  • Michael O'Neill
  • Daniel P. Robinson
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , , ,

    A worst-case complexity bound is proved for a sequential quadratic optimization (commonly known as SQP) algorithm that has been designed for solving optimization problems involving a stochastic objective function and deterministic nonlinear equality constraints. Barring additional terms that arise due to the adaptivity of the monotonically nonincreasing merit parameter sequence, the proved complexity bound is … Read more

    Metaheuristic, Models and Software for the Heterogeneous Fleet Pickup and Delivery Problem with Split Loads

  • Diogenes Gasque
  • Pedro Munari
    • Categories Meta Heuristics, Optimization Software and Modeling Systems, Transportation Tags , , , ,

    This paper addresses a rich variant of the vehicle routing problem (VRP) that involves pickup and delivery activities, customer time windows, heterogeneous fleet, multiple products and the possibility of splitting a customer demand among several routes. This variant generalizes traditional VRP variants by incorporating features that are commonly found in practice. We present two mixed-integer … Read more

    Using an Analytical Computational-Geometry Library to Model Nonoverlap and Boundary-Distance Constraints and their Application to Packing Poly-Bézier Shapes

  • Paul Morton
    • Categories Applications - Science and Engineering, Bound-constrained Optimization, Optimization Software and Modeling Systems Tags , , , , , , , , , , ,

    In this paper we will show how to model nonoverlap as well as uniform and nonuniform boundary-distance constraints between poly-Bézier shapes using an analytical computational-geometry library. We then use this capability to develop, implement and analyze analytical-optimization solutions to minimum-area rectangular-boundary packing-problems as well as minimum-area one- and two-dimensional puzzle-piece packing-problems. In the process, we … Read more

    Orbital $\varphi$-regularity in coincidence and fixed point problems in metric spaces

  • Nguyen Huu Tron
    • Categories Nonlinear Optimization Tags , , , ,

    The purpose of the present paper is to establish some (approximate) fixed point or coincidence theorems for set-valued mappings defined on metric spaces under the so-called orbital \varphi-regularity of the considered mappings. This is a type of (\varphi,\gamma)-regularity of set-valued mappings which is weaker than orbital regularity. In turn, it is used in the previous … Read more

    An oracle-based framework for robust combinatorial optimization

  • Enrico Bettiol
  • Christoph Buchheim
  • Marianna De Santis
  • Francesco Rinaldi
    • Categories Global Optimization, Robust Optimization Tags , ,

    We propose a general solution approach for min-max-robust counterparts of combinatorial optimization problems with uncertain linear objectives. We focus on the discrete scenario case, but our approach can be extended to other types of uncertainty sets such as polytopes or ellipsoids. Concerning the underlying certain problem,the algorithm is entirely oracle-based, i.e., our approach only requires … Read more

    A Lagrangian Dual Method for Two-Stage Robust Optimization with Binary Uncertainties

  • Anirudh Subramanyam
    • Categories Robust Optimization Tags , , ,

    This paper presents a new exact method to calculate worst-case parameter realizations in two-stage robust optimization problems with categorical or binary-valued uncertain data. Traditional exact algorithms for these problems, notably Benders decomposition and column-and-constraint generation, compute worst-case parameter realizations by solving mixed-integer bilinear optimization subproblems. However, their numerical solution can be computationally expensive not only … Read more

    Unmatched Preconditioning of the Proximal Gradient Algorithm

  • Marion Savanier
  • Émilie Chouzenoux
  • Jean-Christophe Pesquet
  • Cyril Riddel
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    This works addresses the resolution of penalized least-squares problems using the proximal gradient algorithm (PGA). It is known that PGA can be accelerated by preconditioning strategies. However, typical effective choices of preconditioners may correspond to intricate matrices that are not easily inverted, and lead to an increased complexity in the computation of the proximity step. … Read more