Stochastic Programming

Extrapolation-based Direct Search for Nonsmooth Stochastic Zeroth-Order Optimization

  • AnthonyPalmieri
  • Francesco Rinaldi
  • Sara Shashaani
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , ,

    We propose and analyze a stochastic direct-search method for unconstrained zeroth-order minimization of locally Lipschitz, possibly nonsmooth, objectives. The method combines random polling directions with a stochastic extrapolating line search based on a sufficient-decrease test of order \(p\). Under conditional accuracy assumptions on the stochastic estimates, which can be verified for mean-zero finite-higher-moment oracle noise … Read more

    Stochastic Bilevel Optimization for the Network Design of Multimodal Transit Systems with Heterogeneous Rider Preferences under Uncertain Travel Times and Demand

  • Yiling Zhang
  • Beste Basciftci
    • Categories Bilevel Optimization, Stochastic Programming, Transportation

    Designing efficient and user-friendly multimodal transit networks is critical for modern urban mobility. We study a novel stochastic multimodal transit network design problem that integrates fixed-route services with on-demand shuttles, explicitly accounting for heterogeneous rider preferences, uncertain travel times, and passenger demand. The hierarchical decision-making process is modeled using a two-stage stochastic bilevel optimization problem, … Read more

    Stochastic convergence of parallel asynchronous adaptive first-order methods

  • Serge Gratton
  • Philippe L. Toint
    • Categories Data Science Algorithms, Stochastic Programming, Unconstrained Optimization Tags , , , , ,

    A new class of asynchronous adaptive first-order optimization methods is introduced, comprising asynchronous variants of several popular algorithms. Versions of these methods using momentum and/or inexact normalization are also considered. The convergence of methods in the class on non-convex functions is analyzed in a fully stochastic setting, and is shown to be (up to logarithmic … Read more

    Non-convergence Analysis of Probabilistic Direct Search

  • Cunxin Huang
  • Zaikun Zhang
    • Categories Nonlinear Optimization, Stochastic Programming Tags , , , ,

    We present a non-convergence theory for probabilistic direct search, a randomized derivative-free optimization method, where non-convergence means the failure to produce iterates that achieve stationarity asymptotically. The motivation is to understand whether the submartingale-like assumption in the existing convergence theory is essential or merely an artifact of the analysis techniques. For convex objectives, we prove … Read more

    Lipschitz Gradient Guarantees for Probability Functions and a New Algorithm for Probability Maximization

  • Wim van Ackooij
  • Carolina Chiu
  • Welington de Oliveira
  • Pedro Pérez-Aros
    • Categories Stochastic Programming Tags , , ,

    This work studies probability functions that appear in stochastic programming models. Although their differentiability has been widely investigated, the Lipschitz continuity of their gradients, crucial for the design and analysis of modern optimization algorithms, has received little attention. We develop a general framework that ensures differentiability and gradient Lipschitz continuity under practical conditions. Our framework … Read more

    Distributionally Robust Optimization via Targeted Integral Probability Metrics for General Data Processes

  • Lanran Fang
  • Jianqiang Cheng
  • Grani A. Hanasusanto
  • Yijie Wang
    • Categories Optimization in Data Science, Robust Optimization, Stochastic Programming Tags , , , , , ,

    Distributionally robust optimization (DRO) has been successful in addressing decision-making problems under uncertainty when the underlying distribution is unknown. Existing data-driven DRO frameworks, however, often impose restrictive assumptions on the data-generating process. We propose a new DRO framework based on targeted integral probability metrics. The ambiguity set is defined directly through the loss functions induced … Read more

    Stochastic Gradient Methods with Online Scaling

  • Wanyu Zhang
  • Wenzhi Gao
  • Yinyu Ye
  • Madeleine Udell
    • Categories Convex Optimization, Stochastic Programming

    This paper introduces Stochastic Online Scaled Gradient Methods (SOSGM), a generalization of the recently developed adaptive preconditioning framework in \cite{gao2025gradient,chu2025gradient} to stochastic optimization. Under standard assumptions, we establish convergence guarantees for SOSGM using large batchsize or variance reduction. SOSGM is compatible with popular diagonal and/or low-rank preconditioners as well as heavy-ball momentum, while maintaining memory … Read more

    Optimality Gap of Tailored Base-Surge Policies Decays Exponentially in Regular-Source Lead Times for Dual-Sourcing Models

  • Xin Chen
  • Shuai Li
  • Weijun Xie
    • Categories Dynamic Programming, Stochastic Programming, Supply Chain Management Tags , , , , ,

    This paper resolves an open problem posed in the literature by proving that, in dual-sourcing inventory systems, the optimality gap of tailored base-surge (TBS) policies decays exponentially with the regular source lead time, with the express-source lead time fixed. In contrast to the existing approach, which relies on conditional Jensen inequalities and a vanishing-discount argument … Read more

    Probabilistic analysis of dual decomposition on two-stage stochastic integer programs

  • Jingye Xu
    • Categories Integer Programming, Stochastic Programming Tags ,

    Two-stage stochastic integer programs provide a powerful framework for modeling decision-making under uncertainty, but they are notoriously difficult to solve at scale due to their high dimensionality and intrinsic nonconvexity. Decomposition-based algorithms such as Benders methods and Branch-and-Price (related dual decomposition methods) have become standard computational approaches for such problems and demonstrate excellent empirical performance … Read more

    Pseudo-Compact Formulations and Branch-and-Cut Approaches for the Capacitated Vehicle Routing Problem with Stochastic Demands

  • Caio Tomazella
  • Pedro Munari
  • Reinaldo Morabito
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Stochastic Programming Tags , , ,

    In this paper, we address the Capacitated Vehicle Routing Problem with Stochastic Demands (CVRPSD), in which routes are planned a priori and recourse actions are performed to ensure demand fulfillment. These recourse actions are defined through policies and may include replenishment trips or demand backlogging subject to penalties. We develop the first family of pseudo-compact … Read more