Spectral relaxations and branching strategies for global optimization of mixed-integer quadratic programs

  • Carlos Nohra
  • Arvind U. Raghunathan
  • Nikolaos Sahinidis
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    We consider the global optimization of nonconvex quadratic programs and mixed-integer quadratic programs. We present a family of convex quadratic relaxations which are derived by convexifying nonconvex quadratic functions through perturbations of the quadratic matrix. We investigate the theoretical properties of these quadratic relaxations and show that they are equivalent to some particular semidefinite programs. … Read more

    A General Framework for Optimal Data-Driven Optimization

  • Daniel Kuhn
  • Tobias Sutter
  • Bart Paul Gerard Van Parys
    • Categories Robust Optimization, Stochastic Programming Tags , , ,

    We propose a statistically optimal approach to construct data-driven decisions for stochastic optimization problems. Fundamentally, a data-driven decision is simply a function that maps the available training data to a feasible action. It can always be expressed as the minimizer of a surrogate optimization model constructed from the data. The quality of a data-driven decision … Read more

    On Distributionally Robust Multistage Convex Optimization: New Algorithms and Complexity Analysis

  • Xu Andy Sun
  • Shixuan Zhang
    • Categories Dynamic Programming, Robust Optimization, Stochastic Programming

    This paper presents a novel algorithmic study and complexity analysis of distributionally robust multistage convex optimization (DR-MCO). We propose a new class of algorithms for solving DR-MCO, namely a sequential dual dynamic programming (Seq-DDP) algorithm and its nonsequential version (NDDP). The new algorithms generalize and strengthen existing DDP-type algorithms by introducing the technique of regularization … Read more

    New algorithms for hierarchical optimisation in kidney exchange programmes

  • Maxence Delorme
  • Jacek Gondzio
  • William Pettersson
  • Sergio García
  • Joerg Kalcsics
  • David Manlove
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming Tags , , , ,

    Kidney exchange programmes (KEPs) across the world help match donors and recipients to identify kidney transplantations. Almost all KEPs use a hierarchical set of objectives to determine an optimal set of transplants to perform, and integer linear programming is often used to find such optimal matchings. In this work, we identify the barriers in existing … Read more

    Convergence of Proximal Gradient Algorithm in the Presence of Adjoint Mismatch

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

    We consider the proximal gradient algorithm for solving penalized least-squares minimization problems arising in data science. This first-order algorithm is attractive due to its flexibility and minimal memory requirements allowing to tackle large-scale minimization problems involving non-smooth penalties. However, for problems such as X-ray computed tomography, the applicability of the algorithm is dominated by the … Read more

    Matching Algorithms and Complexity Results for Constrained Mixed-Integer Optimal Control with Switching Costs

  • Felix Bestehorn
  • Christian Kirches
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms Tags , , , ,

    We extend recent work on the performance of the combinatorial integral approximation decomposition approach for Mixed-Integer Optimal Control Problems (MIOCPs) in the presence of combinatorial constraints or switching costs on an equidistant grid. For the time discretized problem, we reformulate the emerging rounding problem in the decomposition approach as a matching problem on a bipartite … Read more

    A Noise-Tolerant Quasi-Newton Method for Unconstrained Optimization

  • Richard H. Byrd
  • Jorge Nocedal
  • Hao-Jun Shi
  • Yuchen Xie
    • Categories Unconstrained Optimization Tags , , ,

    This paper describes an extension of the BFGS and L-BFGS methods for the minimization of a nonlinear function subject to errors. This work is motivated by applications that contain computational noise, employ low-precision arithmetic, or are subject to statistical noise. The classical BFGS and L-BFGS methods can fail in such circumstances because the updating procedure … Read more

    Tight bounds on the maximal perimeter and the maximal width of convex small polygons

  • Christian Bingane
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Quadratic Programming Tags , , , , ,

    A small polygon is a polygon of unit diameter. The maximal perimeter and the maximal width of a convex small polygon with $n=2^s$ vertices are not known when $s \ge 4$. In this paper, we construct a family of convex small $n$-gons, $n=2^s$ and $s\ge 3$, and show that the perimeters and the widths obtained … Read more

    Robot Dance: a mathematical optimization platform for intervention against Covid-19 in a complex network

  • Luis Gustavo Nonato
  • Claudia Sagastizábal
  • Paulo J. S. Silva
  • Pedro Peixoto
  • Tiago Pereira
    • Categories Biomedical Applications Tags , , ,

    Robot Dance is a computational platform developed in response to the coronavirus outbreak, to support the decision making on public policies at a regional level. The tool is suitable for understanding and suggesting levels of intervention needed to contain the spread of diseases when the mobility of inhabitants through a regional network is a concern. … Read more

    Optimal Steiner Trees Under Node and Edge Privacy Conflicts

  • Roberto Baldacci
  • Alessandro Hill
  • Stefan Voss
    • Categories Branch and Cut Algorithms, Network Optimization, Telecommunications Tags , , , ,

    In this work, we suggest concepts and solution methodologies for a series of strategic network design problems that find application in highly data-sensitive industries, such as, for instance, the high-tech, governmental, or military sector. Our focus is on the installation of widely used cost-efficient tree-structured communication infrastructure. As base model we use the well-known Steiner … Read more