Stochastic Programming

New efficient accelerated and stochastic gradient descent algorithms based on locally Lipschitz gradient constants

  • Pham Thi Hoai
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , , , , , , ,

    In this paper, we revisit the recent stepsize applied for the gradient descent scheme which is called NGD proposed by [Hoai et al., A novel stepsize for gradient descent method, Operations Research Letters (2024) 53, doi: \href{10.1016/j.orl.2024.107072}{10.1016/j.orl.2024.107072}]. We first investigate NGD stepsize with two well-known accelerated techniques which are Heavy ball and Nesterov’s methods. In … Read more

    Accelerating Benders decomposition for solving a sequence of sample average approximation replications

  • Harshit Kothari
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Stochastic Programming

    Sample average approximation (SAA) is a technique for obtaining approximate solutions to stochastic programs that uses the average from a random sample to approximate the expected value that is being optimized. Since the outcome from solving an SAA is random, statistical estimates on the optimal value of the true problem can be obtained by solving … Read more

    Forecasting Outside the Box: Application-Driven Optimal Pointwise Forecasts for Stochastic Optimization

  • Tito Homem-de-Mello
    • Categories Data Science Algorithms, Stochastic Programming Tags ,

    The exponential growth in data availability in recent years has led to new formulations of data-driven optimization problems. One such formulation is that of stochastic optimization problems with contextual information, where the goal is to optimize the expected value of a certain function given some contextual information (also called features) that accompany the main data … Read more

    Single-Scenario Facet Preservation for Stochastic Mixed-Integer Programs

  • Aysenur Karagoz
    • Categories Integer Programming, Polyhedra, Stochastic Programming Tags , , ,

    We consider improving the polyhedral representation of the extensive form of a stochastic mixed-integer program (SMIP). Given a facet for a single-scenario version of an SMIP, our main result provides necessary and sufficient conditions under which this inequality remains facet-defining for the extensive form. We then present several implications, which show that common recourse structures … Read more

    On the ReLU Lagrangian Cuts for Stochastic Mixed Integer Programming

  • Weijun Xie
    • Categories Stochastic Programming Tags , , ,

    We study stochastic mixed integer programs with both first-stage and recourse decisions involving mixed integer variables. A new family of Lagrangian cuts, termed “ReLU Lagrangian cuts,” is introduced by reformulating the nonanticipativity constraints using ReLU functions. These cuts can be integrated into scenario decomposition methods. We show that including ReLU Lagrangian cuts is sufficient to … Read more

    Fully First-Order Methods for Decentralized Bilevel Optimization

  • Xiaoyu Wang
  • Xuxing Chen
  • Shiqian Ma
  • Tong Zhang
    • Categories Nonlinear Optimization, Parallel Algorithms, Stochastic Programming Tags , , ,

    This paper focuses on decentralized stochastic bilevel optimization (DSBO) where agents only communicate with their neighbors. We propose Decentralized Stochastic Gradient Descent and Ascent with Gradient Tracking (DSGDA-GT), a novel algorithm that only requires first-order oracles that are much cheaper than second-order oracles widely adopted in existing works. We further provide a finite-time convergence analysis … Read more

    Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications

  • Yue Huang
  • Zhaoxian Wu
  • Shiqian Ma
  • Qing Ling
    • Categories Nonlinear Optimization, Stochastic Programming Tags , , ,

    Stochastic approximation (SA) that involves multiple coupled sequences, known as multiple-sequence SA (MSSA), finds diverse applications in the fields of signal processing and machine learning. However, existing theoretical understandings of MSSA are limited: the multi-timescale analysis implies a slow convergence rate, whereas the single-timescale analysis relies on a stringent fixed point smoothness assumption. This paper … Read more

    A Dynamic Strategic Plan for the Transition to a Clean Bus Fleet using Multi-Stage Stochastic Programming with a Case Study in Istanbul

  • Neman Karimi
  • Burak Kocuk
  • Tuğçe Yüksel
    • Categories Energy, Stochastic Programming, Transportation Tags , , ,

    In recent years, the transition to clean bus fleets has accelerated. Although this transition might bring environmental and economic benefits, it requires a long-term strategic plan due to the large investment costs involved. This paper proposes a multi-stage stochastic program to optimize strategic plans for the clean bus fleet transition that explicitly considers the uncertainty … Read more

    Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees

  • Zhaosong Lu
  • Sanyou Mei
  • Yifeng Xiao
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    In this paper, we study a class of deterministically constrained stochastic optimization problems. Existing methods typically aim to find an \(\epsilon\)-stochastic stationary point, where the expected violations of both constraints and first-order stationarity are within a prescribed accuracy \(\epsilon\). However, in many practical applications, it is crucial that the constraints be nearly satisfied with certainty, … Read more

    Estimating the Unobservable Components of Electricity Demand Response with Inverse Optimization

  • Adrian Esteban Perez
    • Categories Energy, Statistics, Stochastic Programming Tags , , , , ,

    Understanding and predicting the electricity demand responses to prices are critical activities for system operators, retailers, and regulators. While conventional machine learning and time series analyses have been adequate for the routine demand patterns that have adapted only slowly over many years, the emergence of active consumers with flexible assets such as solar-plus-storage systems, and … Read more