This paper surveys the use of Monte Carlo sampling-based methods for stochastic optimization problems. Such methods are required when—as it often happens in practice—the model involves quantities such as expectations and probabilities that cannot be evaluated exactly. While estimation procedures via sampling are well studied in statistics, the use of such methods in an optimization … Read more
Kusuoka representations provide an important and useful characterization of law invariant coherent risk measures in atomless probability spaces. However, the applicability of these results is limited by the fact that such representations do not always exist in probability spaces with atoms, such as finite probability spaces. We introduce the class of functionally coherent risk measures, … Read more
We present a novel accelerated primal-dual (APD) method for solving a class of deterministic and stochastic saddle point problems (SPP). The basic idea of this algorithm is to incorporate a multi-step acceleration scheme into the primal-dual method without smoothing the objective function. For deterministic SPP, the APD method achieves the same optimal rate of convergence … Read more
In this paper we consider the use of probabilistic or random models within a classical trust-region framework for optimization of deterministic smooth general nonlinear functions. Our method and setting differs from many stochastic optimization approaches in two principal ways. Firstly, we assume that the value of the function itself can be computed without noise, in … Read more
We consider models of two-stage stochastic programming with a quantile second stage criterion and optimization models with a chance constraint on the second stage objective function values. Such models allow to formalize requirements to reliability and safety of the system under consideration, and to optimize the system in extreme conditions. We suggest a method of … Read more
Stochastic-approximation gradient methods are attractive for large-scale convex optimization because they offer inexpensive iterations. They are especially popular in data-fitting and machine-learning applications where the data arrives in a continuous stream, or it is necessary to minimize large sums of functions. It is known that by appropriately decreasing the variance of the error at each … Read more
In a stochastic interdiction game a proliferator aims to minimize the expected duration of a nuclear weapons development project, while an interdictor endeavors to maximize the project duration by delaying some of the project tasks. We formulate static and dynamic versions of the interdictor’s decision problem where the interdiction plan is either pre-committed or adapts … Read more
Recently, there has been a growing interest in developing inventory control policies which are robust to model misspecification. One approach is to posit that nature selects a worst-case distribution for any relevant stochastic primitives from some pre-specified family. Several communities have observed that a subtle phenomena known as time inconsistency can arise in this framework. … Read more
We suggest a method for equivalent transformation of a quantile optimization problem with discrete distribution of random parameters to mixed integer programming problems. The number of additional integer (in fact boolean) variables in the equivalent problems equals to the number of possible scenarios for random data. The obtained mixed integer problems are solved by standard … Read more
We formulate a risk-averse multi-stage stochastic program using conditional value at risk as the risk measure. The underlying random process is assumed to be stage-wise independent, and a stochastic dual dynamic programming (SDDP) algorithm is applied. We discuss the poor performance of the standard upper bound estimator in the risk-averse setting and propose a new … Read more