Sample average approximation of stochastic dominance constrained programs

In this paper we study optimization problems with second-order stochastic dominance constraints. This class of problems allows for the modeling of optimization problems where a risk-averse decision maker wants to ensure that the solution produced by the model dominates certain benchmarks. Here we deal with the case of multi-variate stochastic dominance under general distributions and nonlinear functions. We introduce the concept of ${\mathcal{C}}$ -dominance, which generalizes some notions of multi-variate dominance found in the literature. We apply the Sample Average Approximation (SAA) method to this problem, which results in a semi-infinite program, and study asymptotic convergence of optimal values and optimal solutions, as well as the rate of convergence of the feasibility set of the resulting semi-infinite program as the sample size goes to infinity. We develop a finitely convergent method to find an ${\epsilon}$ -optimal solution of the SAA problem. An important aspect of our contribution is the construction of practical statistical lower and upper bounds for the true optimal objective value. We also show that the bounds are asymptotically tight as the sample size goes to infinity.     

Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications

Inspired by a recent work by Alexander et al. (J Bank Finance 30:583–605, 2006) which proposes a smoothing method to deal with nonsmoothness in a conditional value-at-risk problem, we consider a smoothing scheme for a general class of nonsmooth stochastic problems. Assuming that a smoothed problem is solved by a sample average approximation method, we investigate the convergence of stationary points of the smoothed sample average approximation problem as sample size increases and show that w.p.1 accumulation points of the stationary points of the approximation problem are weak stationary points of their counterparts of the true problem. Moreover, under some metric regularity conditions, we obtain an error bound on approximate stationary points. The convergence result is applied to a conditional value-at-risk problem and an inventory control problem.      

Second-order stochastic dominance constrained portfolio optimization: Theory and computational tests

Due to the definition of second-order stochastic dominance (SSD) in terms of utility theory, portfolio optimization with SSD constraints is of major practical interest. We contribute to the field in two ways: first, we present a self-contained theory with some new results and new proofs of known results; second, we perform a set of tests for computational efficiency. We provide new and simple arguments for the formulation of SSD constraints in a mathematical programming framework. For many individuals, an SSD constraint may seem too severe wherefore various relaxations (ASSD), have been proposed. We introduce yet another relaxation, directional SSD, where a candidate portfolio is admissible if a step from the benchmark in the direction of the candidate yields a dominating portfolio. Optimal step size depends on individual preferences reflected by the objective function. We compare computational efficiency of seven approaches for SD constrained portfolio problems, including SSD and ASSD constrained cases.     

Sample Average Approximation Method for Chance Constrained Programming: Theory and Applications

We study sample approximations of chance constrained problems. In particular, we consider the sample average approximation (SAA) approach and discuss the convergence properties of the resulting problem. We discuss how one can use the SAA method to obtain good candidate solutions for chance constrained problems. Numerical experiments are performed to correctly tune the parameters involved in the SAA. In addition, we present a method for constructing statistical lower bounds for the optimal value of the considered problem and discuss how one should tune the underlying parameters. We apply the SAA to two chance constrained problems. The first is a linear portfolio selection problem with returns following a multivariate lognormal distribution. The second is a joint chance constrained version of a simple blending problem. B.K. Pagnoncelli’s research was supported by CAPES and FUNENSEG. S. Ahmed’s research was partly supported by the NSF Award DMI-0133943. A. Shapiro’s research was partly supported by the NSF Award DMI-0619977.     

A SUCCESSIVE APPROXIMATION METHOD FOR SOLVING PROBABILISTIC CONSTRAINED PROGRAMS

ＡＳＵＣＣＥＳＳＩＶＥＡＰＰＲＯＸＩＭＡＴＩＯＮＭＥＴＨＯＤＦＯＲＳＯＬＶＩＮＧＰＲＯＢＡＢＩＬＩＳＴＩＣＣＯＮＳＴＲＡＩＮＥＤＰＲＯＧＲＡＭＳＷＡＮＧＪＩＮＤＥ（王金德）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＮａｎｊｉｎｇＵｎｉｖｅｒｓ...     

Robust solutions of uncertain complex-valued quadratically constrained programs

In this paper, we discuss complex convex quadratically constrained optimization with uncertain data. Using S-Lemma, we show that the robust counterpart of complex convex quadratically constrained optimization with ellipsoidal or intersection-of-two-ellipsoids uncertainty set leads to a complex semidefinite program. By exploring the approximate S-Lemma, we give a complex semidefinite program which approximates the NP-hard robust counterpart of complex convex quadratic optimization with intersection-of-ellipsoids uncertainty set.     

Conditional value-at-risk in portfolio optimization: Coherent but fragile

We evaluate conditional value-at-risk (CVaR) as a risk measure in data-driven portfolio optimization. We show that portfolios obtained by solving mean-CVaR and global minimum CVaR problems are unreliable due to estimation errors of CVaR and/or the mean, which are magnified by optimization. This problem is exacerbated when the tail of the return distribution is made heavier. We conclude that CVaR, a coherent risk measure, is fragile in portfolio optimization due to estimation errors.     

Stochastic mathematical programs with equilibrium constraints,modelling and sample average approximation

In this article, we discuss the sample average approximation (SAA) method applied to a class of stochastic mathematical programs with variational (equilibrium) constraints. To this end, we briefly investigate the structure of both–the lower level equilibrium solution and objective integrand. We show almost sure convergence of optimal values, optimal solutions (both local and global) and generalized Karush–Kuhn–Tucker points of the SAA program to their true counterparts. We also study uniform exponential convergence of the sample average approximations, and as a consequence derive estimates of the sample size required to solve the true problem with a given accuracy. Finally, we present some preliminary numerical test results.     

Supply chain design under uncertainty using sample average approximation and dual decomposition

We present a supply chain design problem modeled as a sequence of splitting and combining processes. We formulate the problem as a two-stage stochastic program. The first-stage decisions are strategic location decisions, whereas the second stage consists of operational decisions. The objective is to minimize the sum of investment costs and expected costs of operating the supply chain. In particular the model emphasizes the importance of operational flexibility when making strategic decisions. For that reason short-term uncertainty is considered as well as long-term uncertainty. The real-world case used to illustrate the model is from the Norwegian meat industry. We solve the problem by sample average approximation in combination with dual decomposition. Computational results are presented for different sample sizes and different levels of data aggregation in the second stage.     

The sample average approximation method for empty container repositioning with uncertainties

One of the challenges faced by liner operators today is to effectively operate empty containers in order to meet demand and to reduce inefficiency in an uncertain environment. To incorporate uncertainties in the operations model, we formulate a two-stage stochastic programming model with random demand, supply, ship weight capacity, and ship space capacity. The objective of this model is to minimize the expected operational cost for Empty Container Repositioning (ECR). To solve the stochastic programs with a prohibitively large number of scenarios, the Sample Average Approximation (SAA) method is applied to approximate the expected cost function. To solve the SAA problem, we consider applying the scenario aggregation by combining the approximate solution of the individual scenario problem. Two heuristic algorithms based on the progressive hedging strategy are applied to solve the SAA problem. Numerical experiments are provided to show the good performance of the scenario-based method for the ECR problem with uncertainties.     

On a class of stochastic differential equations arising from the stochastic approximation theory

The paper dealt with generalized stochastic approximation procedures of Robbins-Monro type. We consider these procedures as strong solutions of some stochastic differential equations with respect to semimartingales and investigate their almost sure convergence and mean square convergence     

Numerical methods for stochastic programs with second order dominance constraints with applications to portfolio optimization

Inspired by the successful applications of the stochastic optimization with second order stochastic dominance (SSD) model in portfolio optimization, we study new numerical methods for a general SSD model where the underlying functions are not necessarily linear. Specifically, we penalize the SSD constraints to the objective under Slater’s constraint qualification and then apply the well known stochastic approximation (SA) method and the level function method to solve the penalized problem. Both methods are iterative: the former requires to calculate an approximate subgradient of the objective function of the penalized problem at each iterate while the latter requires to calculate a subgradient. Under some moderate conditions, we show that w.p.1 the sequence of approximated solutions generated by the SA method converges to an optimal solution of the true problem. As for the level function method, the convergence is deterministic and in some cases we are able to estimate the number of iterations for a given precision. Both methods are applied to portfolio optimization problem where the return functions are not necessarily linear and some numerical test results are reported.     

The value of the stochastic solution in stochastic linear programs with fixed recourse

Stochastic linear programs have been rarely used in practical situations largely because of their complexity. In evaluating these problems without finding the exact solution, a common method has been to find bounds on the expected value of perfect information. In this paper, we consider a different method. We present bounds on the value of the stochastic solution, that is, the potential benefit from solving the stochastic program over solving a deterministic program in which expected values have replaced random parameters. These bounds are calculated by solving smaller programs related to the stochastic recourse problem.This paper is an extension of part of the author's dissertation in the Department of Operations Research, Stanford University, Stanford, California. The research was supported at Stanford by the Department of Energy under Contract DE-AC03-76SF00326, PA#DE-AT03-76ER72018, Office of Naval Research under Contract N00014-75-C-0267 and the National Science Foundation under Grants MCS76-81259, MCS-7926009 and ECS-8012974 (formerly ENG77-06761).     

The Newton differential correction algorithm for rational Chebyshev approximation with constrained denominators

An algorithm for constrained rational Chebyshev approximation is introduced that combines the idea of an algorithm due to Hettich and Zencke, for which superlinear convergence is guaranteed, with the auxiliary problem used in the well-known original differential correction method. Superlinear convergence of the algorithm is proved. Numerical examples illustrate the fast convergence of the method and its advantages compared with the algorithm of Hettich and Zencke.     

On complexity of multistage stochastic programs

In this paper we derive estimates of the sample sizes required to solve a multistage stochastic programming problem with a given accuracy by the (conditional sampling) sample average approximation method. The presented analysis is self-contained and is based on a relatively elementary, one-dimensional, Cramér's Large Deviations Theorem.     

Convergence of a stochastic approximation algorithm for the GI/G/1 queue using infinitesimal perturbation analysis

Discrete-event systems to which the technique of infinitesimal perturbation analysis (IPA) is applicable are natural candidates for optimization via a Robbins-Monro type stochastic approximation algorithm. We establish a simple framework for single-run optimization of systems with regenerative structure. The main idea is to convert the original problem into one in which unbiased estimators can be derived from strongly consistent IPA gradient estimators. Standard stochastic approximation results can then be applied. In particular, we consider the GI/G/1 queue, for which IPA gives strongly consistent estimators for the derivative of the mean system time. Convergence (w.p.1) proofs for the problem of minimizing the mean system time with respect to a scalar service time parameter are presented.     

A smoothing method for solving portfolio optimization with CVaR and applications in allocation of generation asset

This paper focuses on the computation issue of portfolio optimization with scenario-based CVaR. According to the semismoothness of the studied models, a smoothing technology is considered, and a smoothing SQP algorithm then is presented. The global convergence of the algorithm is established. Numerical examples arising from the allocation of generation assets in power markets are done. The computation efficiency between the proposed method and the linear programming (LP) method is compared. Numerical results show that the performance of the new approach is very good. The remarkable characteristic of the new method is threefold. First, the dimension of smoothing models for portfolio optimization with scenario-based CVaR is low and is independent of the number of samples. Second, the smoothing models retain the convexity of original portfolio optimization problems. Third, the complicated smoothing model that maximizes the profit under the CVaR constraint can be reduced to an ordinary optimization model equivalently. All of these show the advantage of the new method to improve the computation efficiency for solving portfolio optimization problems with CVaR measure.     

A method of stochastic subgradients with complete feedback stepsize rule for convex stochastic approximation problems

A stochastic subgradient algorithm for solving convex stochastic approximation problems is considered. In the algorithm, the stepsize coefficients are controlled on-line on the basis of information gathered in the course of computations according to a new, complete feedback rule derived from the concept of regularized improvement function. Convergence with probability 1 of the method is established.This work was supported by Project No. CPBP/02.15.     

Single and multi-period optimal inventory control models with risk-averse constraints

This paper presents some convex stochastic programming models for single and multi-period inventory control problems where the market demand is random and order quantities need to be decided before demand is realized. Both models minimize the expected losses subject to risk aversion constraints expressed through Value at Risk (VaR) and Conditional Value at Risk (CVaR) as risk measures. A sample average approximation method is proposed for solving the models and convergence analysis of optimal solutions of the sample average approximation problem is presented. Finally, some numerical examples are given to illustrate the convergence of the algorithm.     

随机DEA期望值模型的一些性质

为判别决策单元在随机DEA期望值模型下的随机有效性,首次提出了随机期望无效、随机期望弱有效、随机期望有效以及随机期望超有效的概念．并给出了三个命题用于判别不同显著性水平下随机期望效率与期望效率的关系．在此基础上,得到了两个重要的性质：（1）当期望效率保持不变时,随机期望效率为显著性水平的增函数;（2）当显著性水平保持不变时,随机期望效率为期望效率的增函数．最后,利用随机模拟和一个算例对上述结论进行了验证．