A preliminary set of applications leading to stochastic semidefinite programs and chance-constrained semidefinite programs

Ariyawansa and Zhu have recently introduced (two-stage) stochastic semidefinite programs (with recourse) (SSDPs) [1] and chance-constrained semidefinite programs (CCSDPs) [2] as paradigms for dealing with uncertainty in applications leading to semidefinite programs. Semidefinite programs have been the subject of intense research during the past 15 years, and one of the reasons for this research activity is the novelty and variety of applications of semidefinite programs. This research activity has produced, among other things, efficient interior point algorithms for semidefinite programs. Semidefinite programs however are defined using deterministic data while uncertainty is naturally present in applications. The definitions of SSDPs and CCSDPs in [1] and [2] were formulated with the expectation that they would enhance optimization modeling in applications that lead to semidefinite programs by providing ways to handle uncertainty in data. In this paper, we present results of our attempts to create SSDP and CCSDP models in four such applications. Our results are promising and we hope that the applications presented in this paper would encourage researchers to consider SSDP and CCSDP as new paradigms for stochastic optimization when they formulate optimization models.     

A note on constraint aggregation and value functions for two-stage stochastic integer programs

We consider a class of two-stage stochastic integer programs and their equivalent reformulation that uses the integer programming value functions in both stages. One class of solution methods in the literature is based on the idea of pre-computing and storing exact value functions, and then exploiting this information within a global branch-and-bound framework. Such methods are known to be very sensitive to the magnitude of feasible right-hand side values. In this note we propose a simple constraint-aggregation based approach that potentially alleviates this limitation.     

Scenario reduction in stochastic programming with respect to discrepancy distances

Discrete approximations to chance constrained and mixed-integer two-stage stochastic programs require moderately sized scenario sets. The relevant distances of (multivariate) probability distributions for deriving quantitative stability results for such stochastic programs are ℬ-discrepancies, where the class ℬ of Borel sets depends on their structural properties. Hence, the optimal scenario reduction problem for such models is stated with respect to ℬ-discrepancies. In this paper, upper and lower bounds, and some explicit solutions for optimal scenario reduction problems are derived. In addition, we develop heuristic algorithms for determining nearly optimally reduced probability measures, discuss the case of the cell discrepancy (or Kolmogorov metric) in some detail and provide some numerical experience.     

Duality and statistical tests of optimality for two stage stochastic programs

We present alternative methods for verifying the quality of a proposed solution to a two stage stochastic program with recourse. Our methods revolve around implications of a dual problem in which dual multipliers on the nonanticipativity constraints play a critical role. Using randomly sampled observations of the stochastic elements, we introduce notions of statistical dual feasibility and sampled error bounds. Additionally, we use the nonanticipativity multipliers to develop connections to reduced gradient methods. Finally, we propose a statistical test based on directional derivatives. We illustrate the applicability of these tests via some examples. This work was supported in part by Grant No. NSF-DMI-9414680 from the National Science Foundation     

Use of chance-constrained programming to account for stochastic variation in theA-matrix of large-scale linear programs: A forestry application

Linear programming (LP) is widely used to select the manner in which forest lands are managed. Because of the nature of forestry, this application has several unique characteristics. For example, the models consider many different management actions that take place over many years, thus resulting in very large LP formulations with diverse data. In addition, almost none of the data are known with certainty. The most pervasive occurrence of stochastic information is in the production coefficients, which indicate the uncertain response of the managed forest ecosystem to various management options. A chance-constrained approach to handling this uncertainty would often be appropriate in forestry applications —managers and decision makers would like to specify a probability with which uncertain constraints are met. Unfortunately, chance-constrained procedures forA-matrix uncertainty produce nonlinear programming problems, which cannot currently be solved for large-scale forestry applications. This paper utilizes a Monte Carlo simulation approach (a linear program is repeatedly solved with randomly perturbedA-matrix coefficients) to describe the distribution of total output when the individual production coefficients are random. An iterative procedure for chance-constraining feasibility is developed and demonstrated with this sort of randomA-matrix. An iterative approach is required because the mean and variance of total output are unknown functions of the randomA-matrix coefficients and the level of output required. This approach may have applications in other fields as well.     

A Notion of Stochastic Input-to-State Stability and Its Application to Stability of Cascaded Stochastic Nonlinear Systems

In this paper, the property of practical input-to-state stability and its application to stability of cascaded nonlinear systems are investigated in the stochastic framework. Firstly, the notion of （practical） stochastic input-to-state stability with respect to a stochastic input is introduced, and then by the method of changing supply functions, （a） an （practical） SISS-Lyapunov function for the overall system is obtained from the corresponding Lyapunov functions for cascaded （practical） SISS subsystems.     

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.     

A tighter variant of Jensen’s lower bound for stochastic programs and separable approximations to recourse functions

In this paper, we propose a new method to compute lower bounds on the optimal objective value of a stochastic program and show how this method can be used to construct separable approximations to the recourse functions. We show that our method yields tighter lower bounds than Jensen’s lower bound and it requires a reasonable amount of computational effort even for large problems. The fundamental idea behind our method is to relax certain constraints by associating dual multipliers with them. This yields a smaller stochastic program that is easier to solve. We particularly focus on the special case where we relax all but one of the constraints. In this case, the recourse functions of the smaller stochastic program are one dimensional functions. We use these one dimensional recourse functions to construct separable approximations to the original recourse functions. Computational experiments indicate that our lower bounds can significantly improve Jensen’s lower bound and our recourse function approximations can provide good solutions.     

BBPH: Using progressive hedging within branch and bound to solve multi-stage stochastic mixed integer programs

Progressive hedging, though an effective heuristic for solving stochastic mixed integer programs (SMIPs), is not guaranteed to converge in this case. Here, we describe BBPH, a branch and bound algorithm that uses PH at each node in the search tree such that, given sufficient time, it will always converge to a globally optimal solution. In addition to providing a theoretically convergent “wrapper” for PH applied to SMIPs, computational results demonstrate that for some difficult problem instances branch and bound can find improved solutions after exploring only a few nodes.     

A penalty function-based random search algorithm for optimal control of switched systems with stochastic constraints and its application in automobile test-driving with gear shifts

Practical industrial process is usually a dynamic process including uncertainty. Stochastic constraints can be used for industrial process modeling, when system sate and/or control input constraints cannot be strictly satisfied. Thus, optimal control of switched systems with stochastic constraints can be available to address practical industrial process problems with different modes. In general, obtaining an analytical solution of the optimal control problem is usually very difficult due to the discrete nature of the switching law and the complexity of stochastic constraints. To obtain a numerical solution, this problem is formulated as a constrained nonlinear parameter selection problem (CNPSP) based on a relaxation transformation (RT) technique, an adaptive sample approximation (ASA) method, a smooth approximation (SA) technique, and a control parameterization (CP) method. Following that, a penalty function-based random search (PFRS) algorithm is designed for solving the CNPSP based on a novel search rule-based penalty function (NSRPF) method and a novel random search (NRS) algorithm. The convergence results show that the proposed method is globally convergent. Finally, an optimal control problem in automobile test-driving with gear shifts (ATGS) is further extended to illustrate the effectiveness of the proposed method by taking into account some stochastic constraints. Numerical results show that compared with other typical methods, the proposed method is less conservative and can obtain a stable and robust performance when considering the small perturbations in initial system state. In addition, to balance the computation amount and the numerical solution accuracy, a tolerance setting method is also provided by the numerical analysis technique.     

Asymptotic analysis for a stochastic semidefinite programming

Stochastic semidefinite programming (SSDP) is a new class of optimization problems with a wide variety of applications. In this article, asymptotic analysis results of sample average approximation estimator for SSDP are established. Asymptotic analysis result already existing for stochastic nonlinear programming is extended to SSDP, that is, the conditions ensuring the convergence in distribution of sample average approximation estimator for SSDP to a multivariate normal are obtained and the corresponding covariance matrix is described in a closed form.     

Monte Carlo and quasi-Monte Carlo sampling methods for a class of stochastic mathematical programs with equilibrium constraints

In this paper, we consider a class of stochastic mathematical programs with equilibrium constraints introduced by Birbil et al. (Math Oper Res 31:739–760, 2006). Firstly, by means of a Monte Carlo method, we obtain a nonsmooth discrete approximation of the original problem. Then, we propose a smoothing method together with a penalty technique to get a standard nonlinear programming problem. Some convergence results are established. Moreover, since quasi-Monte Carlo methods are generally faster than Monte Carlo methods, we discuss a quasi-Monte Carlo sampling approach as well. Furthermore, we give an example in economics to illustrate the model and show some numerical results with this example. The first author’s work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science and SRF for ROCS, SEM. The second author’s work was supported in part by the United Kingdom Engineering and Physical Sciences Research Council grant. The third author’s work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science.     

New approach to optimal control of stochastic Volterra integral equations

ABSTRACT

We study optimal control of stochastic Volterra integral equations (SVIE) with jumps by using Hida-Malliavin calculus.

• We give conditions under which there exist unique solutions of such equations.

• Then we prove both a sufficient maximum principle (a verification theorem) and a necessary maximum principle via Hida-Malliavin calculus.

• As an application we solve a problem of optimal consumption from a cash flow modelled by an SVIE.

     

A contribution to the linear programming approach to joint cost allocation: Methodology and application

The linear programming (LP) approach has been commonly proposed for joint cost allocation purposes. Within a LP framework, the allocation rules are based on a marginal analysis. Unfortunately, the additivity property which is required to completely allocate joint costs fails in presence of capacity, institutional or environmental constraints.     

Continuity of parametric mixed-integer quadratic programs and its application to stability analysis of two-stage quadratic stochastic programs with mixed-integer recourse

For mixed-integer quadratic program where all coefficients in the objective function and the right-hand sides of constraints vary simultaneously, we show locally Lipschitz continuity of its optimal value function, and derive the corresponding global estimation; furthermore, we also obtain quantitative estimation about the change of its optimal solutions. Applying these results to two-stage quadratic stochastic program with mixed-integer recourse, we establish quantitative stability of the optimal value function and the optimal solution set with respect to the Fortet-Mourier probability metric, when the underlying probability distribution is perturbed. The obtained results generalize available results on continuity properties of mixed-integer quadratic programs and extend current results on quantitative stability of two-stage quadratic stochastic programs with mixed-integer recourse.     

Stochastic asymptotical stability for stochastic impulsive differential equations and it is application to chaos synchronization

In this paper, the stochastic asymptotical stability of stochastic impulsive differential equations is studied, and a comparison theory about the stochastic asymptotical stability of trivial solution is established. From the comparison theory, we can find out whether the stochastic impulsive differential system is stochastic asymptotically stable by studying the stability of a deterministic comparison system. As an application of this theory, we study the problem of chaos synchronization in Chua circuit using impulsive method. Finally, numerical simulation is employed to verify the feasibility of our method.     

极大极小随机规划逼近问题最优解集和最优值的稳定性

研究了特殊的二层极大极小随机规划逼近收敛问题. 首先将下层初始随机规划最优解集拓展到非单点集情形, 且可行集正则的条件下, 讨论了下层随机规划逼近问题最优解集关于上层决策变量参数的上半收敛性和最优值函数的连续性. 然后把下层随机规划的epsilon-最优解向量函数反馈到上层随机规划的目标函数中, 得到了上层随机规划逼近问题的最优解集关于最小信息概率度量收敛的上半收敛性和最优值的连续性.     

A multi-objective facility location model for closed-loop supply chain network under uncertain demand and return

A closed-loop supply chain (CLSC) network consists of both forward and reverse supply chains. In this paper, a CLSC network is investigated which includes multiple plants, collection centres, demand markets, and products. To this aim, a mixed-integer linear programming model is proposed that minimizes the total cost. Besides, two test problems are examined. The model is extended to consider environmental factors by weighed sums and ε-constraint methods. In addition, we investigate the impact of demand and return uncertainties on the network configuration by stochastic programming (scenario-based). Computational results show that the model can handle demand and return uncertainties, simultaneously.     

An exact algorithm for solving large-scale two-stage stochastic mixed-integer problems: Some theoretical and experimental aspects

We present an algorithmic framework, so-called BFC-TSMIP, for solving two-stage stochastic mixed 0–1 problems. The constraints in the Deterministic Equivalent Model have 0–1 variables and continuous variables at any stage. The approach uses the Twin Node Family (TNF) concept within an adaptation of the algorithmic framework so-called Branch-and-Fix Coordination for satisfying the nonanticipativity constraints for the first stage 0–1 variables. Jointly we solve the mixed 0–1 submodels defined at each TNF integer set for satisfying the nonanticipativity constraints for the first stage continuous variables. In these submodels the only integer variables are the second stage 0–1 variables. A numerical example and some theoretical and computational results are presented to show the performance of the proposed approach.