stochastic optimization

Data-Driven Stochastic Dual Dynamic Programming: Performance Guarantees and Regularization Schemes

  • Hyuk Park
  • Zhuangzhuang Jia
  • Grani A. Hanasusanto
    • Categories Stochastic Programming Tags , , , ,

    We propose a data-driven scheme for multistage stochastic linear programming with Markovian random parameters by extending the stochastic dual dynamic programming (SDDP) algorithm. In our data-driven setting, only a finite number of historical trajectories are available. The proposed SDDP scheme evaluates the cost-to-go functions only at the observed sample points, where the conditional expectations are … Read more

    A Simplified Convergence Theory for Byzantine Resilient Stochastic Gradient Descent

  • Lindon Roberts
    • Categories Optimization in Data Science, Stochastic Programming Tags , ,

    In distributed learning, a central server trains a model according to updates provided by nodes holding local data samples. In the presence of one or more malicious servers sending incorrect information (a Byzantine adversary), standard algorithms for model training such as stochastic gradient descent (SGD) fail to converge. In this paper, we present a simplified … 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 , , , ,

    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 most suited in practice. This is especially so … Read more

    Efficient composite heuristics for integer bound constrained noisy optimization

  • Morteza Kimiaei
  • Arnold Neumaier
    • Categories Bound-constrained Optimization, Integer Programming, Optimization Software Benchmark Tags , , , ,

    This paper discusses a composite algorithm for bound constrained noisy derivative-free optimization problems with integer variables. This algorithm is an integer variant of the matrix adaptation evolution strategy. An integer derivative-free line search strategy along affine scaling matrix directions is used to generate candidate points. Each affine scaling matrix direction is a product of the … Read more

    A Stochastic Optimization Approach to Energy-Efficient Underground Timetabling under Uncertain Dwell and Running Times

  • Andreas Bärmann
  • Patrick Gemander
  • Alexander Martin
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming, Transportation Tags , , , , ,

    We consider a problem from the context of energy-efficient underground railway timetabling, in which an existing timetable draft is improved by slightly changing departure and running times. In practice, synchronization between accelerating and braking trains to utilize regenerative braking plays a major role for the energy-efficiency of a timetable. Since deviations from a planned timetable … Read more

    An Adaptive Sampling Sequential Quadratic Programming Method for Equality Constrained Stochastic Optimization

  • Albert S. Berahas
  • Raghu Bollapragada
  • Baoyu Zhou
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , ,

    This paper presents a methodology for using varying sample sizes in sequential quadratic programming (SQP) methods for solving equality constrained stochastic optimization problems. The first part of the paper deals with the delicate issue of dynamic sample selection in the evaluation of the gradient in conjunction with inexact solutions to the SQP subproblems. Under reasonable … Read more

    First- and Second-Order High Probability Complexity Bounds for Trust-Region Methods with Noisy Oracles

  • Liyuan Cao
  • Albert S. Berahas
  • Katya Scheinberg
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    In this paper, we present convergence guarantees for a modified trust-region method designed for minimizing objective functions whose value is computed with noise and for which gradient and Hessian estimates are inexact and possibly random. In order to account for the noise, the method utilizes a relaxed step acceptance criterion and a cautious trust-region radius … Read more

    Accelerating Stochastic Sequential Quadratic Programming for Equality Constrained Optimization using Predictive Variance Reduction

  • Albert S. Berahas
  • Jiahao Shi
  • Zihong Yi
  • Baoyu Zhou
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , ,

    In this paper, we propose a stochastic variance reduction method for solving equality constrained optimization problems. Specifically, we develop a method based on the sequential quadratic programming paradigm that utilizes gradient approximations via predictive variance reduction techniques. Under reasonable assumptions, we prove that a measure of first-order stationarity evaluated at the iterates generated by our … Read more

    Intraday Power Trading: Towards an Arms Race in Weather Forecasting?

  • Thomas Kuppelwieser
  • David Wozabal
    • Categories Finance and Economics, Stochastic Programming Tags , , , ,

    We propose the first weather-based algorithmic trading strategy on a continuous intraday power market. The strategy uses neither production assets nor power demand and generates profits purely based on superior information about aggregate output of weather-dependent renewable production. We use an optimized parametric policy based on state-of-the-art intraday updates of renewable production forecasts and evaluate … Read more

    Convergence rates of the stochastic alternating algorithm for bi-objective optimization

  • Suyun Liu
  • Luis Nunes Vicente
    • Categories Convex and Nonsmooth Optimization, Multi-Criteria Optimization, Nonlinear Optimization Tags , , ,

    Stochastic alternating algorithms for bi-objective optimization are considered when optimizing two conflicting functions for which optimization steps have to be applied separately for each function. Such algorithms consist of applying a certain number of steps of gradient or subgradient descent on each single objective at each iteration. In this paper, we show that stochastic alternating … Read more