On complexity and convergence of high-order coordinate descent algorithms

  • V. S. Amaral
  • Roberto Andreani
  • Ernesto G. Birgin
  • José Mario Martínez
  • Diaulas S. Marcondes
    • Categories Nonlinear Optimization Tags , ,

    Coordinate descent methods with high-order regularized models for box-constrained minimization are introduced. High-order stationarity asymptotic convergence and first-order stationarity worst-case evaluation complexity bounds are established. The computer work that is necessary for obtaining first-order $\varepsilon$-stationarity with respect to the variables of each coordinate-descent block is $O(\varepsilon^{-(p+1)/p})$ whereas the computer work for getting first-order $\varepsilon$-stationarity with … Read more

    The Arc-Item-Load and Related Formulations for the Cumulative Vehicle Routing Problem

  • Mauro Henrique Mulati
  • Ricardo Fukasawa
  • Flávio Keidi Miyazawa
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization Tags , , , ,

    The Capacitated Vehicle Routing Problem (CVRP) consists of finding the cheapest way to serve a set of customers with a fleet of vehicles of a given capacity. While serving a particular customer, each vehicle picks up its demand and carries its weight throughout the rest of its route. While costs in the classical CVRP are … Read more

    ADMM and inexact ALM: the QP case

  • Stefano Cipolla
  • Jacek Gondzio
    • Categories Quadratic Programming Tags , ,

    Embedding randomization procedures in the Alternating Direction Method of Multipliers (ADMM) has recently attracted an increasing amount of interest as a remedy to the fact that the direct n-block generalization of ADMM is not necessarily convergent ($n \geq 3$). Even if, in practice, the introduction of such techniques could mitigate the diverging behaviour of the … Read more

    Branch-and-bound and objective branching with three objectives

  • Nicolas Forget
  • Sune Lauth Gadegaard
  • Kathrin Klamroth
  • Lars Relund Nielsen
  • Anthony Przybylski
    • Categories Multi-Criteria Optimization

    The recent success of bi-objective Branch-and-Bound (B&B) algorithms heavily relies on the efficient computation of upper and lower bound sets. Besides the classical dominance test, bound sets are used to improve the computational time by imposing inequalities derived from (partial) dominance in the objective space. This process is called objective branching since it is mostly … Read more

    A Structure Exploiting Algorithm for Non-Smooth Semi-Linear Elliptic Optimal Control Problems

  • Stephan Schmidt
  • Olga Weiß
  • Andrea Walther
    • Categories Infinite Dimensional Optimization, Nonsmooth Optimization

    We investigate optimization problems with a non-smooth partial differential equation as constraint, where the non-smoothness is assumed to be caused by Nemytzkii operators generated by the functions abs, min and max. For the efficient as well as robust solution of such problems, we propose a new optimization method based on abs-linearization, i.e., a special handling … Read more

    An exact solution approach for an electric bus dispatch problem

  • Matías Alvo
  • Gustavo Angulo
  • Mathias A. Klapp
    • Categories (Mixed) Integer Linear Programming, Scheduling, Transportation Tags , , ,

    We study how to efficiently plan the daily bus dispatch operation within a public transport terminal working with a fleet of electric buses. This requires to formulate and solve a new variant of the Vehicle Scheduling Problem model, in which one has to assign trip itineraries to each vehicle considering that driving ranges are limited, … Read more

    Kernel Distributionally Robust Optimization

  • Moritz Diehl
  • Wittawat Jitkrittum
  • Bernhard Schölkopf
  • Jia-Jie Zhu
    • Categories Robust Optimization, Statistics, Stochastic Programming Tags , , ,

    We propose kernel distributionally robust optimization (Kernel DRO) using insights from the robust optimization theory and functional analysis. Our method uses reproducing kernel Hilbert spaces (RKHS) to construct a wide range of convex ambiguity sets, including sets based on integral probability metrics and finite-order moment bounds. This perspective unifies multiple existing robust and stochastic optimization … Read more

    An Exact Projection-Based Algorithm for Bilevel Mixed-Integer Problems with Nonlinearities

  • Maximilian Merkert
  • Galina Orlinskaya
  • Dieter Weninger
    • Categories (Mixed) Integer Nonlinear Programming, Game Theory, Global Optimization Tags , , , ,

    We propose an exact global solution method for bilevel mixed-integer optimization problems with lower-level integer variables and including nonlinear terms such as, \eg, products of upper-level and lower-level variables. Problems of this type are extremely challenging as a single-level reformulation suitable for off-the-shelf solvers is not available in general. In order to solve these problems … Read more

    Planar Maximum Coverage Location Problem with Partial Coverage, Continuous Spatial Demand, and Adjustable Quality of Service

  • Manish Bansal
  • Parshin Shojaee
    • Categories Combinatorial Optimization

    We consider a generalization of the classical planar maximum coverage location problem (PMCLP) in which partial coverage is allowed, facilities have adjustable quality of service (QoS) or service range, and demand zones and service zone of each facility are represented by two-dimensional spatial objects such as rectangles, circles, polygons, etc. We denote this generalization by … Read more

    Moreau envelope of supremum functions with applications to infinite and stochastic programming

  • Pedro Pérez-Aros
  • Emilio Vilches
    • Categories Convex Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , , ,

    In this paper, we investigate the Moreau envelope of the supremum of a family of convex, proper, and lower semicontinuous functions. Under mild assumptions, we prove that the Moreau envelope of a supremum is the supremum of Moreau envelopes, which allows us to approximate possibly nonsmooth supremum functions by smooth functions that are also the … Read more