sample average approximation

An inexact restoration-nonsmooth algorithm with variable accuracy for stochastic nonsmooth convex optimization problems in machine learning and stochastic linear complementarity problems

  • Nataša Krejić
  • Nataša Krklec Jerinkić
  • Tijana Ostojić
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Stochastic Programming Tags , , , ,

    We study unconstrained optimization problems with nonsmooth and convex objective function in the form of a mathematical expectation. The proposed method approximates the expected objective function with a sample average function using Inexact Restoration-based adapted sample sizes. The sample size is chosen in an adaptive manner based on Inexact Restoration. The algorithm uses line search … Read more

    Data-driven sample average approximation with covariate information

  • Rohit Kannan
  • Güzin Bayraksan
  • James R. Luedtke
    • Categories Stochastic Programming Tags , , , , ,

    We study optimization for data-driven decision-making when we have observations of the uncertain parameters within the optimization model together with concurrent observations of covariates. Given a new covariate observation, the goal is to choose a decision that minimizes the expected cost conditioned on this observation. We investigate three data-driven frameworks that integrate a machine learning … Read more

    On sample average approximation for two-stage stochastic programs without relatively complete recourse

  • Rui Chen
  • James R. Luedtke
    • Categories Stochastic Programming Tags , , ,

    We investigate sample average approximation (SAA) for two-stage stochastic programs without relatively complete recourse, i.e., for problems in which there are first-stage feasible solutions that are not guaranteed to have a feasible recourse action. As a feasibility measure of the SAA solution, we consider the “recourse likelihood”, which is the probability that the solution has … Read more

    Sample Average Approximation for Stochastic Nonconvex Mixed Integer Nonlinear Programming via Outer Approximation

  • David E. Bernal Neira
  • Kevin C Furman
  • Ignacio E. Grossmann
  • Can Li
    • Categories (Mixed) Integer Nonlinear Programming, Stochastic Programming Tags , , ,

    Stochastic mixed-integer nonlinear programming (MINLP) is a very challenging type of problem. Although there have been recent advances in developing decomposition algorithms to solve stochastic MINLPs, none of the existing algorithms can address stochastic MINLPs with continuous distributions. We propose a sample average approximation-based outer approximation algorithm (SAAOA) that can address nonconvex two-stage stochastic programs … Read more

    Transmission Switching Under Wind Uncertainty Using Linear Decision Rules

  • Grani A. Hanasusanto
  • Yuqi Zhou
  • Hao Zhu
    • Categories Applications - Science and Engineering Tags , , ,

    Increasing penetration of wind and renewable generation poses significant challenges to the power system operations and reliability. This paper considers the real-time optimal transmission switching (OTS) problem for determining the generation dispatch and network topology that can account for uncertain energy resources. To efficiently solve the resultant two-stage stochastic program, we propose a tractable linear … Read more

    Improving sample average approximation using distributional robustness

  • Edward Anderson
  • Andrew B. Philpott
    • Categories Stochastic Programming Tags , ,

    We consider stochastic optimization problems in which we aim to minimize the expected value of an objective function with respect to an unknown distribution of random parameters. We analyse the out-of-sample performance of solutions obtained by solving a distributionally robust version of the sample average approximation problem for unconstrained quadratic problems, and derive conditions under … Read more

    Solving Chance-Constrained Problems via a Smooth Sample-Based Nonlinear Approximation

  • James R. Luedtke
  • Alejandra Pena-Ordieres
  • Andreas Wächter
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , , , , , ,

    We introduce a new method for solving nonlinear continuous optimization problems with chance constraints. Our method is based on a reformulation of the probabilistic constraint as a quantile function. The quantile function is approximated via a differentiable sample average approximation. We provide theoretical statistical guarantees of the approximation, and illustrate empirically that the reformulation can … Read more

    A Scenario-Based Approach for the Vehicle Routing Problem with Roaming Delivery Locations under Stochastic Travel Times

  • Joris Kinable
  • Afonso Sampaio
  • Lucas Veelenturf
  • Tom Van Woensel
    • Categories Meta Heuristics, Stochastic Programming, Transportation Tags , ,

    We address a stochastic variant of the Vehicle Routing Problem with Roaming Delivery Locations. In this model, direct-to-consumer deliveries can be made in the trunk of the customer’s car, while the vehicle is parked at a location along the customer’s itinerary. The stochasticity arises from the uncertainty in travel times and the problem is formulated … Read more

    Identifying Effective Scenarios for Sample Average Approximation

  • Lijian Chen
    • Categories Stochastic Programming Tags

    We introduce a method to improve the tractability of the well-known Sample Average Approximation (SAA) without compromising important theoretical properties, such as convergence in probability and the consistency of an independent and identically distributed (iid) sample. We consider each scenario as a polyhedron of the mix of first-stage and second-stage decision variables. According to John’s … Read more

    An Efficient Linear Programming Based Method for the Influence Maximization Problem in Social Networks

  • Evren Güney
    • Categories 0-1 Programming, Approximation Algorithms, Network Optimization Tags , , ,

    The influence maximization problem (IMP) aims to determine the most influential individuals within a social network. In this study first we develop a binary integer program that approximates the original problem by Monte Carlo sampling. Next, to solve IMP efficiently, we propose a linear programming relaxation based method with a provable worst case bound that … Read more