Stochastic Programming

Using Taylor-Approximated Gradients to Improve the Frank-Wolfe Method for Empirical Risk Minimization

  • Zikai Xiong
  • Robert M. Freund
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Stochastic Programming Tags , , , , ,

    The Frank-Wolfe method has become increasingly useful in statistical and machine learning applications, due to the structure-inducing properties of the iterates, and especially in settings where linear minimization over the feasible set is more computationally efficient than projection. In the setting of Empirical Risk Minimization — one of the fundamental optimization problems in statistical and … Read more

    Software for data-based stochastic programming using bootstrap estimation

  • Xiaotie Chen
  • David L. Woodruff
    • Categories Other Topics, Stochastic Programming

    In this paper we describe software for stochastic programming that uses only sampled data to obtain both a consistent sample-average solution and a consistent estimate of confidence intervals for the optimality gap using bootstrap and bagging. The underlying distribution whence the samples come is not required. ArticleDownload View PDF

    Stochastic nested primal-dual method for nonconvex constrained composition optimization

  • Ling-Zi Jin
  • Xiao Wang
    • Categories Constrained Nonlinear Optimization, Data Science Algorithms, Stochastic Programming Tags , , , , , , ,

    In this paper we study the nonconvex constrained composition optimization, in which the objective contains a composition of two expected-value functions whose accurate information is normally expensive to calculate. We propose a STochastic nEsted Primal-dual (STEP) method for such problems. In each iteration, with an auxiliary variable introduced to track the inner layer function values … Read more

    Statistical performance of subgradient step-size update rules in Lagrangian relaxations of chance-constrained optimization models

  • Charlotte Ritter
  • Bismark Singh
    • Categories Stochastic Programming Tags , , , ,

    Published in Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-031-47859-8_26 Lagrangian relaxation schemes, coupled with a subgradient procedure, are frequently employed to solve chance-constrained optimization models. The subgradient procedure typically relies on a step-size update rule. Although there is extensive research on the properties of these step-size update rules, there is little consensus on which rules are … Read more

    A momentum-based linearized augmented Lagrangian method for nonconvex constrained stochastic optimization

  • Qiankun Shi
  • Xiao Wang
  • Hao Wang
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    Nonconvex constrained stochastic optimization has emerged in many important application areas. Subject to general functional constraints it minimizes the sum of an expectation function and a nonsmooth regularizer. Main challenges arise due to the stochasticity in the random integrand and the possibly nonconvex functional constraints. To address these issues we propose a momentum-based linearized augmented … Read more

    Markov Chain-based Policies for Multi-stage Stochastic Integer Linear Programming with an Application to Disaster Relief Logistics

  • Margarita P Castro
  • Merve Bodur
  • Yongjia Song
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

    We introduce an aggregation framework to address multi-stage stochastic programs with mixed-integer state variables and continuous local variables (MSILPs). Our aggregation framework imposes additional structure to the integer state variables by leveraging the information of the underlying stochastic process, which is modeled as a Markov chain (MC). We demonstrate that the aggregated MSILP can be … Read more

    Asymptotic Consistency for Nonconvex Risk-Averse Stochastic Optimization with Infinite Dimensional Decision Spaces

  • Johannes Milz
  • Thomas Surowiec
    • Categories Optimization of Systems modeled by PDEs, Stochastic Programming, Systems governed by Differential Equations Optimization Tags , , , , , , ,

    Optimal values and solutions of empirical approximations of stochastic optimization problems can be viewed as statistical estimators of their true values. From this perspective, it is important to understand the asymptotic behavior of these estimators as the sample size goes to infinity, which is both of theoretical as well as practical interest. This area of … Read more

    A General Wasserstein Framework for Data-driven Distributionally Robust Optimization: Tractability and Applications

  • Jonathan Yu-Meng Li
  • Tiantian Mao
    • Categories Robust Optimization, Stochastic Programming Tags , ,

    Data-driven distributionally robust optimization is a recently emerging paradigm aimed at finding a solution that is driven by sample data but is protected against sampling errors. An increasingly popular approach, known as Wasserstein distributionally robust optimization (DRO), achieves this by applying the Wasserstein metric to construct a ball centred at the empirical distribution and finding … Read more

    A single cut proximal bundle method for stochastic convex composite optimization

  • Jiaming Liang
  • Vincent Guigues
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Stochastic Programming Tags , , ,

    This paper considers optimization problems where the objective is the sum of a function given by an expectation and a closed convex composite function, and proposes stochastic composite proximal bundle (SCPB) methods for solving it. Complexity guarantees are established for them without requiring knowledge of parameters associated with the problem instance. Moreover, it is shown … Read more

    Routing and resource allocation in non-profit settings with equity and efficiency measures under demand uncertainty

  • Faisal Alkaabneh
  • Karmel S. Shehadeh
  • Ali Diabat
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

    Motivated by food distribution operations for non-profit organizations, we study a variant of the stochastic routing-allocation problem under demand uncertainty, in which one decides the assignment of trucks for demand nodes, the sequence of demand nodes to visit (i.e., truck route), and the allocation of food supply to each demand node. We propose three stochastic … Read more