Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity

  • Benjamin Grimmer
    • Categories Convex Optimization Tags , ,

    We generalize the classic convergence rate theory for subgradient methods to apply to non-Lipschitz functions via a new measure of steepness. For the deterministic projected subgradient method, we derive a global $O(1/\sqrt{T})$ convergence rate for any function with at most exponential growth. Our approach implies generalizations of the standard convergence rates for gradient descent on … Read more

    Robust optimization for models with uncertain SOC and SDP constraints

  • Frans J.C.T. de Ruiter
  • Dick den Hertog
  • Ernst Roos
  • Jianzhe Zhen
    • Categories Robust Optimization Tags , , , ,

    In this paper we consider uncertain second-order cone (SOC) and semidefinite programming (SDP) constraints with polyhedral uncertainty, which are in general computationally intractable. We propose to reformulate an uncertain SOC or SDP constraint as a set of adjustable robust linear optimization constraints with an ellipsoidal or semidefinite representable uncertainty set, respectively. The resulting adjustable problem … Read more

    Exact Methods for Solving Traveling Salesman Problems with Pickup and Delivery in Real Time

  • Karla Hoffman
  • Ryan J. O'Neil
    • Categories Transportation Tags , , , ,

    The Traveling Salesman Problem with Pickup and Delivery (TSPPD) describes the problem of finding a minimum cost path in which pickups precede their associated deliveries. The TSPPD is particularly important in the growing field of Dynamic Pickup and Delivery Problems (DPDP). These include the many-to-many Dial-A-Ride Problems (DARP) of companies such as Uber and Lyft, … Read more

    ”Active-set complexity” of proximal gradient: How long does it take to find the sparsity pattern?

  • Warren Hare
  • Mark Schmidt
  • Julie Nutini
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , ,

    Proximal gradient methods have been found to be highly effective for solving minimization problems with non-negative constraints or L1-regularization. Under suitable nondegeneracy conditions, it is known that these algorithms identify the optimal sparsity pattern for these types of problems in a finite number of iterations. However, it is not known how many iterations this may … Read more

    Approximate Positively Correlated Distributions and Approximation Algorithms for D-optimal Design

  • Mohit Singh
  • Weijun Xie
    • Categories Approximation Algorithms, Data-Mining Tags , , ,

    Experimental design is a classical problem in statistics and has also found new applications in machine learning. In the experimental design problem, the aim is to estimate an unknown vector x in m-dimensions from linear measurements where a Gaussian noise is introduced in each measurement. The goal is to pick k out of the given … Read more

    Forecasting Solar Flares using magnetogram-based predictors and Machine Learning

  • Federico Benvenuto
  • Manolis K. Georgoulis
  • D. Shaun Bloomfield
  • Kostas Florios
  • Jordan A. Guerra
  • Ioannis Kontogiannis
  • Sung-Hong Park
    • Categories Basic Sciences Applications, Data-Mining, Statistics Tags ,

    We propose a forecasting approach for solar flares based on data from Solar Cycle 24, taken by the Helioseismic and Magnetic Imager (HMI) on board the Solar Dynamics Observatory (SDO) mission. In particular, we use the Space-weather HMI Active Region Patches (SHARP) product that facilitates cut-out magnetograms of solar active regions (AR) in the Sun … Read more

    A feasible rounding approach for mixed-integer optimization problems

  • Christoph Neumann
  • Oliver Stein
  • Nathan Sudermann-Merx
    • Categories (Mixed) Integer Linear Programming

    We introduce granularity as a sufficient condition for the consistency of a mixed-integer optimization problem, and show how to exploit it for the computation of feasible points: For optimization problems which are granular, solving certain linear problems and rounding their optimal points always leads to feasible points of the original mixed-integer problem. Thus, the resulting … Read more

    Decision support for strategic energy planning: a complete robust optimization framework

  • Frédéric Babonneau
  • Michel Bierlaire
  • F Maréchal
  • Stefano Moret
    • Categories Robust Optimization

    This paper presents a complete robust optimization framework to deal with a large range of uncertainties in optimization-based energy models. Robust formulations are proposed to address specific features of long- term energy models – such as multiplied uncertain parameters in the objective and many uncertainties in the constraints. Then, we introduce an original approach to … Read more

    Model and Discretization Error Adaptivity within Stationary Gas Transport Optimization

  • Volker Mehrmann
  • Martin Schmidt
  • Jeroen J. Stolwijk
    • Categories Applications - Science and Engineering, Network Optimization, Systems governed by Differential Equations Optimization Tags , , , ,

    The minimization of operation costs for natural gas transport networks is studied. Based on a recently developed model hierarchy ranging from detailed models of instationary partial differential equations with temperature dependence to highly simplified algebraic equations, modeling and discretization error estimates are presented to control the overall error in an optimization method for stationary and … Read more

    Branch-and-Price for Routing with Probabilistic Customers

  • Mathias A. Klapp
  • Felipe Lagos
  • Alejandro Toriello
    • Categories Integer Programming, Transportation Tags ,

    The Vehicle Routing Problem with Probabilistic Customers (VRP-PC) is a fundamental building block within the broad family of stochastic routing models, and has two decision stages. In the first stage, a dispatcher determines a set of vehicle routes serving all potential customer locations, before actual requests for service realize. In the second stage, vehicles are … Read more