Parallel decomposition of multistage stochastic programming problems

A new decomposition method for multistage stochastic linear programming problems is proposed. A multistage stochastic problem is represented in a tree-like form and with each node of the decision tree a certain linear or quadratic subproblem is associated. The subproblems generate proposals for their successors and some backward information for their predecessors. The subproblems can be solved in parallel and exchange information in an asynchronous way through special buffers. After a finite time the method either finds an optimal solution to the problem or discovers its inconsistency. An analytical illustrative example shows that parallelization can speed up computation over every sequential method. Computational experiments indicate that for large problems we can obtain substantial gains in efficiency with moderate numbers of processors.This work was partly supported by the International Institute for Applied Systems Analysis, Laxenburg, Austria.     

Using a factored dual in augmented Lagrangian methods for semidefinite programming

In the context of augmented Lagrangian approaches for solving semidefinite programming problems, we investigate the possibility of eliminating the positive semidefinite constraint on the dual matrix by employing a factorization. Hints on how to deal with the resulting unconstrained maximization of the augmented Lagrangian are given. We further use the approximate maximum of the augmented Lagrangian with the aim of improving the convergence rate of alternating direction augmented Lagrangian frameworks. Numerical results are reported, showing the benefits of the approach.     

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.     

On the convergence of inexact augmented Lagrangian methods for problems with convex constraints

We consider the augmented Lagrangian method (ALM) for constrained optimization problems in the presence of convex inequality and convex abstract constraints. We focus on the case where the Lagrangian sub-problems are solved up to approximate stationary points, with increasing accuracy. We analyze two different criteria of approximate stationarity for the sub-problems and we prove the global convergence to stationary points of ALM in both cases.     

Parallel decomposition of large-scale stochastic nonlinear programs

Many practical decision problems involve both nonlinear relationships and uncertainties. The resulting stochastic nonlinear programs become quite difficult to solve as the number of possible scenarios increases. In this paper, we provide a decomposition method for problems in which nonlinear constraints appear within periods. We also show how the method extends to lower bounding refinements of the set of scenarios when the random data are independent from period to period. We then apply the method to a stochastic model of the U.S. economy based on the Global 2100 method developed by Manne and Richels.This material is based upon work supported by the National Science Foundation under Award Numbers SES-9211937 and DDM-9215921.The research was performed under appointment to the U.S. Department of Energy, Graduate Fellowships for Global Change Program, administered by Oak Ridge Institute for Science and Education.     

L-shaped decomposition of two-stage stochastic programs with integer recourse

We consider two-stage stochastic programming problems with integer recourse. The L-shaped method of stochastic linear programming is generalized to these problems by using generalized Benders decomposition. Nonlinear feasibility and optimality cuts are determined via general duality theory and can be generated when the second stage problem is solved by standard techniques. Finite convergence of the method is established when Gomory’s fractional cutting plane algorithm or a branch-and-bound algorithm is applied.     

Scenario tree reduction for multistage stochastic programs

A framework for the reduction of scenario trees as inputs of (linear) multistage stochastic programs is provided such that optimal values and approximate solution sets remain close to each other. The argument is based on upper bounds of the L _r -distance and the filtration distance, and on quantitative stability results for multistage stochastic programs. The important difference from scenario reduction in two-stage models consists in incorporating the filtration distance. An algorithm is presented for selecting and removing nodes of a scenario tree such that a prescribed error tolerance is met. Some numerical experience is reported.     

The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming

We analyze the rate of local convergence of the augmented Lagrangian method in nonlinear semidefinite optimization. The presence of the positive semidefinite cone constraint requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and variational analysis on the projection operator in the symmetric matrix space. Without requiring strict complementarity, we prove that, under the constraint nondegeneracy condition and the strong second order sufficient condition, the rate of convergence is linear and the ratio constant is proportional to 1/c, where c is the penalty parameter that exceeds a threshold . The research of Defeng Sun is partly supported by the Academic Research Fund from the National University of Singapore. The research of Jie Sun and Liwei Zhang is partly supported by Singapore–MIT Alliance and by Grants RP314000-042/057-112 of the National University of Singapore. The research of Liwei Zhang is also supported by the National Natural Science Foundation of China under project grant no. 10471015 and by the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry, China.     

An enhanced decomposition algorithm for multistage stochastic hydroelectric scheduling

Handling uncertainty in natural inflow is an important part of a hydroelectric scheduling model. In a stochastic programming formulation, natural inflow may be modeled as a random vector with known distribution, but the size of the resulting mathematical program can be formidable. Decomposition-based algorithms take advantage of special structure and provide an attractive approach to such problems. We develop an enhanced Benders decomposition algorithm for solving multistage stochastic linear programs. The enhancements include warm start basis selection, preliminary cut generation, the multicut procedure, and decision tree traversing strategies. Computational results are presented for a collection of stochastic hydroelectric scheduling problems.     

Lagrangian decomposition of block-separable mixed-integer all-quadratic programs

The purpose of this paper is threefold. First we propose splitting schemes for reformulating non-separable problems as block-separable problems. Second we show that the Lagrangian dual of a block-separable mixed-integer all-quadratic program (MIQQP) can be formulated as an eigenvalue optimization problem keeping the block-separable structure. Finally we report numerical results on solving the eigenvalue optimization problem by a proximal bundle algorithm applying Lagrangian decomposition. The results indicate that appropriate block-separable reformulations of MIQQPs could accelerate the running time of dual solution algorithms considerably.The work was supported by the German Research Foundation (DFG) under grant NO 421/2-1Mathematics Subject Classification (2000): 90C22, 90C20, 90C27, 90C26, 90C59     

A parallel inexact newton method for stochastic programs with recourse

A parallel inexact Newton method with a line search is proposed for two-stage quadratic stochastic programs with recourse. A lattice rule is used for the numerical evaluation of multi-dimensional integrals, and a parallel iterative method is used to solve the quadratic programming subproblems. Although the objective only has a locally Lipschitz gradient, global convergence and local superlinear convergence of the method are established. Furthermore, the method provides an error estimate which does not require much extra computation. The performance of the method is illustrated on a CM5 parallel computer.This work was supported by the Australian Research Council and the numerical experiments were done on the Sydney Regional Centre for Parallel Computing CM5.     

Nested decomposition of multistage nonlinear programs with recourse

Nested decomposition is extended to the case of arborescent nonlinear programs. Duals of extensive forms of nonlinear multistage stochastic programs constitute a particular class of those problems; the method is tested on a set of problems of that type.     

A new augmented Lagrangian function for inequality constraints in nonlinear programming problems

In this paper, a new augmented Lagrangian function is introduced for solving nonlinear programming problems with inequality constraints. The relevant feature of the proposed approach is that, under suitable assumptions, it enables one to obtain the solution of the constrained problem by a single unconstrained minimization of a continuously differentiable function, so that standard unconstrained minimization techniques can be employed. Numerical examples are reported.     

On the implementation of a log-barrier progressive hedging method for multistage stochastic programs

A progressive hedging method incorporated with self-concordant barrier for solving multistage stochastic programs is proposed recently by Zhao [G. Zhao, A Lagrangian dual method with self-concordant barrier for multistage stochastic convex nonlinear programming, Math. Program. 102 (2005) 1-24]. The method relaxes the nonanticipativity constraints by the Lagrangian dual approach and smoothes the Lagrangian dual function by self-concordant barrier functions. The convergence and polynomial-time complexity of the method have been established. Although the analysis is done on stochastic convex programming, the method can be applied to the nonconvex situation. We discuss some details on the implementation of this method in this paper, including when to terminate the solution of unconstrained subproblems with special structure and how to perform a line search procedure for a new dual estimate effectively. In particular, the method is used to solve some multistage stochastic nonlinear test problems. The collection of test problems also contains two practical examples from the literature. We report the results of our preliminary numerical experiments. As a comparison, we also solve all test problems by the well-known progressive hedging method.     

A regularized stochastic decomposition algorithm for two-stage stochastic linear programs

In this paper a regularized stochastic decomposition algorithm with master programs of finite size is described for solving two-stage stochastic linear programming problems with recourse. In a deterministic setting cut dropping schemes in decomposition based algorithms have been used routinely. However, when only estimates of the objective function are available such schemes can only be properly justified if convergence results are not sacrificed. It is shown that almost surely every accumulation point in an identified subsequence of iterates produced by the algorithm, which includes a cut dropping scheme, is an optimal solution. The results are obtained by including a quadratic proximal term in the master program. In addition to the cut dropping scheme, other enhancements to the existing methodology are described. These include (i) a new updating rule for the retained cuts and (ii) an adaptive rule to determine when additional reestimation of the cut associated with the current solution is needed. The algorithm is tested on problems from the literature assuming both descrete and continuous random variables.A majority of this work is part of the author's Ph.D. dissertation prepared at the University of Arizona in 1990.     

A proximal augmented Lagrangian method for equilibrium problems

Considering a recently proposed proximal point method for equilibrium problems, we construct an augmented Lagrangian method for solving the same problem in reflexive Banach spaces with cone constraints generating a strongly convergent sequence to a certain solution of the problem. This is an inexact hybrid method meaning that at a certain iterate, a solution of an unconstrained equilibrium problem is found, allowing a proper error bound, followed by a Bregman projection of the initial iterate onto the intersection of two appropriate halfspaces. Assuming a set of reasonable hypotheses, we provide a full convergence analysis.     

Adaptive discretization of convex multistage stochastic programs

We propose a new scenario tree reduction algorithm for multistage stochastic programs, which integrates the reduction of a scenario tree into the solution process of the stochastic program. This allows to construct a scenario tree that is highly adapted on the optimization problem. The algorithm starts with a rough approximation of the original tree and locally refines this approximation as long as necessary. Promising numerical results for scenario tree reductions in the settings of portfolio management and power management with uncertain load are presented.     

Finite master programs in regularized stochastic decomposition

Stochastic decomposition is a stochastic analog of Benders' decomposition in which randomly generated observations of random variables are used to construct statistical estimates of supports of the objective function. In contrast to deterministic Benders' decomposition for two stage stochastic programs, the stochastic version requires infinitely many inequalities to ensure convergence. We show that asymptotic optimality can be achieved with a finite master program provided that a quadratic regularizing term is included. Our computational results suggest that the elimination of the cutting planes impacts neither the number of iterations required nor the statistical properties of the terminal solution.This work was supported in part by Grant No. AFOSR-88-0076 from the Air Force Office of Scientific Research and Grant Nos. DDM-89-10046, DDM-9114352 from the National Science Foundation.Corresponding author.     

Cut sharing for multistage stochastic linear programs with interstage dependency

Multistage stochastic programs with interstage independent random parameters have recourse functions that do not depend on the state of the system. Decomposition-based algorithms can exploit this structure by sharing cuts (outer-linearizations of the recourse function) among different scenario subproblems at the same stage. The ability to share cuts is necessary in practical implementations of algorithms that incorporate Monte Carlo sampling within the decomposition scheme. In this paper, we provide methodology for sharing cuts in decomposition algorithms for stochastic programs that satisfy certain interstage dependency models. These techniques enable sampling-based algorithms to handle a richer class of multistage problems, and may also be used to accelerate the convergence of exact decomposition algorithms. Research leading to this work was partially supported by the Department of Energy Contract DE-FG03-92ER25116-A002; the Office of Naval Research Contract N00014-89-J-1659; the National Science Foundation Grants ECS-8906260, DMS-8913089; and the Electric Power Research Institute Contract RP 8010-09, CSA-4O05335. This author's work was supported in part by the National Research Council under a Research Associateship at the Naval Postgraduate School, Monterey, California.     

Convex relaxation and Lagrangian decomposition for indefinite integer quadratic programming

We study lower bounding methods for indefinite integer quadratic programming problems. We first construct convex relaxations by D.C. (difference of convex functions) decomposition and linear underestimation. Lagrangian bounds are then derived by applying dual decomposition schemes to separable relaxations. Relationships between the convex relaxation and Lagrangian dual are established. Finally, we prove that the lower bound provided by the convex relaxation coincides with the Lagrangian bound of the orthogonally transformed problem.