On the Convergence of Sampling-Based Decomposition Algorithms for Multistage Stochastic Programs

The paper presents a convergence proof for a broad class of sampling algorithms for multistage stochastic linear programs in which the uncertain parameters occur only in the constraint right-hand sides. This class includes SDDP, AND, ReSa, and CUPPS. We show that, under some independence assumptions on the sampling procedure, the algorithms converge with probability 1.The first author acknowledges support by the Swiss National Science Foundation. The second author acknowledges support by NZPGST Grant UOAX0203. The authors are grateful to the anonymous referees for comments improving the exposition of this paper.     

A Primal-Dual Decomposition Algorithm for Multistage Stochastic Convex Programming

This paper presents a new and high performance solution method for multistage stochastic convex programming. Stochastic programming is a quantitative tool developed in the field of optimization to cope with the problem of decision-making under uncertainty. Among others, stochastic programming has found many applications in finance, such as asset-liability and bond-portfolio management. However, many stochastic programming applications still remain computationally intractable because of their overwhelming dimensionality. In this paper we propose a new decomposition algorithm for multistage stochastic programming with a convex objective and stochastic recourse matrices, based on the path-following interior point method combined with the homogeneous self-dual embedding technique. Our preliminary numerical experiments show that this approach is very promising in many ways for solving generic multistage stochastic programming, including its superiority in terms of numerical efficiency, as well as the flexibility in testing and analyzing the model.Research supported by Hong Kong RGC Earmarked Grant CUHK4233/01E.     

Outcome-Space Cutting-Plane Algorithm for Linear Multiplicative Programming

This article presents an outcome-space pure cutting-plane algorithm for globally solving the linear multiplicative programming problem. The framework of the algorithm is taken from a pure cutting-plane decision set-based method developed by Horst and Tuy for solving concave minimization problems. By adapting this method to an outcome-space reformulation of the linear multiplicative programming problem, rather than applying directly the method to the original decision-set formulation, it is expected that considerable computational savings can be obtained. Also, we show how additional computational benefits might be obtained by implementing the new algorithm appropriately. To illustrate the new algorithm, we apply it to the solution of a sample problem.     

Solving Stochastic Linear Programs with Restricted Recourse Using Interior Point Methods

In this paper we present a specialized matrix factorization procedure for computing the dual step in a primal-dual path-following interior point algorithm for solving two-stage stochastic linear programs with restricted recourse. The algorithm, based on the Birge-Qi factorization technique, takes advantage of both the dual block-angular structure of the constraint matrix and of the special structure of the second-stage matrices involved in the model. Extensive computational experiments on a set of test problems have been conducted in order to evaluate the performance of the developed code. The results are very promising, showing that the code is competitive with state-of-the-art optimizers.     

A Globally Convergent Sequential Quadratic Programming Algorithm for Mathematical Programs with Linear Complementarity Constraints

This paper presents a sequential quadratic programming algorithm for computing a stationary point of a mathematical program with linear complementarity constraints. The algorithm is based on a reformulation of the complementarity condition as a system of semismooth equations by means of Fischer-Burmeister functional, combined with a classical penalty function method for solving constrained optimization problems. Global convergence of the algorithm is established under appropriate assumptions. Some preliminary computational results are reported.     

Scenarios for Multistage Stochastic Programs

A major issue in any application of multistage stochastic programming is the representation of the underlying random data process. We discuss the case when enough data paths can be generated according to an accepted parametric or nonparametric stochastic model. No assumptions on convexity with respect to the random parameters are required. We emphasize the notion of representative scenarios (or a representative scenario tree) relative to the problem being modeled.     

A Conditional Logic Approach for Strengthening Mixed 0-1 Linear Programs

We study a conditional logic approach for tightening the continuous relaxation of a mixed 0-1 linear program. The procedure first constructs quadratic inequalities by computing pairwise products of constraints, and then surrogates modified such inequalities to produce valid linear restrictions. Strength is achieved by adjusting the coefficients on the quadratic restrictions. The approach is a unifying framework for published coefficient adjustment methods, and generalizes the process of sequential lifting. We give illustrative examples and discuss various extensions, including the use of more complex conditional logic constructs that compute and surrogate polynomial expressions, and the application to general integer programs. Partially supported by NSF grant #DMI-0423415 and ONR grant #N00014-97-1-0784.     

Conditional Value-at-Risk in Stochastic Programs with Mixed-Integer Recourse

In classical two-stage stochastic programming the expected value of the total costs is minimized. Recently, mean-risk models - studied in mathematical finance for several decades - have attracted attention in stochastic programming. We consider Conditional Value-at-Risk as risk measure in the framework of two-stage stochastic integer programming. The paper addresses structure, stability, and algorithms for this class of models. In particular, we study continuity properties of the objective function, both with respect to the first-stage decisions and the integrating probability measure. Further, we present an explicit mixed-integer linear programming formulation of the problem when the probability distribution is discrete and finite. Finally, a solution algorithm based on Lagrangean relaxation of nonanticipativity is proposed. Received: April, 2004     

一般形式多阶段有补偿问题的广义对偶理论

本文在文［１］的基础上，讨论一般形式多阶段有补偿非线性随机规划问题的广义对偶理论与最优化性条件．通过发掘凸规划对偶理论的本质，首先推广了与通常规划问题对偶理论有关的概念的含义，由此构造出所论问题在等价意义下的广义原始泛函与广义对偶泛函，进而得到其广义对偶理论，所得结论不仅能恰当合理地反映问题本身的属性，而且有关定理的表述形式简明、结论较强，可直接应用于多阶段有补偿问题的其它理论研究与数值求解算法的设计中去．上述结果与所用研究方法均推广和发展了通常的对偶理论     

On the Convergence of a Population-Based Global Optimization Algorithm

In global optimization, a typical population-based stochastic search method works on a set of sample points from the feasible region. In this paper, we study a recently proposed method of this sort. The method utilizes an attraction-repulsion mechanism to move sample points toward optimality and is thus referred to as electromagnetism-like method (EM). The computational results showed that EM is robust in practice, so we further investigate the theoretical structure. After reviewing the original method, we present some necessary modifications for the convergence proof. We show that in the limit, the modified method converges to the vicinity of global optimum with probability one.     

A Cutting Plane Algorithm for Linear Reverse Convex Programs

In this paper, global optimization of linear programs with an additional reverse convex constraint is considered. This type of problem arises in many applications such as engineering design, communications networks, and many management decision support systems with budget constraints and economies-of-scale. The main difficulty with this type of problem is the presence of the complicated reverse convex constraint, which destroys the convexity and possibly the connectivity of the feasible region, putting the problem in a class of difficult and mathematically intractable problems. We present a cutting plane method within the scope of a branch-and-bound scheme that efficiently partitions the polytope associated with the linear constraints and systematically fathoms these portions through the use of the bounds. An upper bound and a lower bound for the optimal value is found and improved at each iteration. The algorithm terminates when all the generated subdivisions have been fathomed.     

基于随机搜索的一个约束优化问题的全局收敛算法

讨论了具有一般约束的全局优化问题,给出该问题的一个随机搜索算法,证明了该算法依概率1收敛到问题的全局最优解．数值结果显示该方法是有效的．     

双层线性规划的一个全局优化方法

用线性规划对偶理论分析了双层线性规划的最优解与下层问题的对偶问题可行域上极点之间的关系，通过求得下层问题的对偶问题可行域上的极点，将双层线性规划转化为有限个线性规划问题，从而用线性规划方法求得问题的全局最优解．由于下层对偶问题可行域上只有有限个极点，所以方法具有全局收敛性．     

Quantitative Stability Analysis of Two-Stage Stochastic Linear Programs with Full Random Recourse

Abstract

In this paper, we apply the parametric linear programing technique and pseudo metrics to study the quantitative stability of the two-stage stochastic linear programing problem with full random recourse. Under the simultaneous perturbation of the cost vector, coefficient matrix, and right-hand side vector, we first establish the locally Lipschitz continuity of the optimal value function and the boundedness of optimal solutions of parametric linear programs. On the basis of these results, we deduce the locally Lipschitz continuity and the upper bound estimation of the objective function of the two-stage stochastic linear programing problem with full random recourse. Then by adopting different pseudo metrics, we obtain the quantitative stability results of two-stage stochastic linear programs with full random recourse which improve the current results under the partial randomness in the second stage problem. Finally, we apply these stability results to the empirical approximation of the two-stage stochastic programing model, and the rate of convergence is presented.     

Parallelizable Preprocessing Method for Multistage Stochastic Programming Problems

Stochastic programming has extensive applications in practical problems such as production planning and portfolio selection. Typically, the model has very large size and some techniques are often used to exploit the special structure of the programs. It has been noticed that the coefficient matrix may not be of full rank in the well-known scenario formulation of stochastic programming; thus, the preprocessing is often necessary in developing rapid decomposition methods. In this paper, we propose a parallelizable preprocessing method, which exploits effectively the structure of the formulation. Although the underlying idea is simple, the method turns out to be very useful in practice, since it may help us to select the nonanticipativity constraints efficiently. Some numerical results are reported confirming the usefulness of the method.This work was partially supported by the Informatics Research Center for Development of Knowledge Society Infrastructure, Graduate School of Informatics, Kyoto University, Kyoto, Japan. The work of the first author was also supported in part by the National Science Foundation of China, Grant 10571039. The work of the second author was also supported in part by the Scientific Research Grant-in-Aid from the Japan Society for the Promotion of Science. The authors are grateful to the referees for careful reading of the paper and helpful comments.This author’s work was done while he was visiting Kyoto University.     

一种求解线性二层规划的割平面方法

以下层问题的K-T最优性条件代替下层问题,将线性二层规划转化为相应的单层规划问题,通过分析单层规划可行解集合的结构特征,设计了一种求解线性二层规划全局最优解的割平面算法.数值结果表明所设计的割平面算法是可行、有效的.     

下层独立的一主多从双层随机线性规划问题研究

Herminia I.Calvete等研究了一主多从双层确定性线性规划问题,证明了这类问题等价于一类常规的双层线性规划问题.本文在此基础上,推广确定型的问题到随机型优化情况,考虑了一类下层优化相互独立的一主多从双层随机优化问题(SLBMFP).在特定的随机变量分布条件下,理论上证明了该类问题可以转化为一主一从双层确定性优化问题.本文的研究对于求解一主多从双层随机优化模型,解决此类模型在实际应用中的问题具有一定的意义.     

A Superlinearly Convergent SSLE Algorithm for Optimization Problems with Linear Complementarity Constraints

In this paper we study a special kind of optimization problems with linear complementarity constraints. First, by a generalized complementarity function and perturbed technique, the discussed problem is transformed into a family of general nonlinear optimization problems containing parameters. And then, using a special penalty function as a merit function, we establish a sequential systems of linear equations (SSLE) algorithm. Three systems of equations solved at each iteration have the same coefficients. Under some suitable conditions, the algorithm is proved to possess not only global convergence, but also strong and superlinear convergence. At the end of the paper, some preliminary numerical experiments are reported.     

On the convergence of stochastic dual dynamic programming and related methods

We discuss the almost-sure convergence of a broad class of sampling algorithms for multistage stochastic linear programs. We provide a convergence proof based on the finiteness of the set of distinct cut coefficients. This differs from existing published proofs in that it does not require a restrictive assumption.