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     

On a mixture of the fix-and-relax coordination and Lagrangian substitution schemes for multistage stochastic mixed integer programming

We present a framework for solving large-scale multistage mixed 0–1 optimization problems under uncertainty in the coefficients of the objective function, the right-hand side vector, and the constraint matrix. A scenario tree-based scheme is used to represent the Deterministic Equivalent Model of the stochastic mixed 0–1 program with complete recourse. The constraints are modeled by a splitting variable representation via scenarios. So, a mixed 0–1 model for each scenario cluster is considered, plus the nonanticipativity constraints that equate the 0–1 and continuous so-called common variables from the same group of scenarios in each stage. Given the high dimensions of the stochastic instances in the real world, it is not realistic to obtain the optimal solution for the problem. Instead we use the so-called Fix-and-Relax Coordination (FRC) algorithm to exploit the characteristics of the nonanticipativity constraints of the stochastic model. A mixture of the FRC approach and the Lagrangian Substitution and Decomposition schemes is proposed for satisfying, both, the integrality constraints for the 0–1 variables and the nonanticipativity constraints. This invited paper is discussed in the comments available at: doi:, doi:, doi:, doi:.     

Feasible Interior Methods Using Slacks for Nonlinear Optimization

A slack-based feasible interior point method is described which can be derived as a modification of infeasible methods. The modification is minor for most line search methods, but trust region methods require special attention. It is shown how the Cauchy point, which is often computed in trust region methods, must be modified so that the feasible method is effective for problems containing both equality and inequality constraints. The relationship between slack-based methods and traditional feasible methods is discussed. Numerical results using the KNITRO package show the relative performance of feasible versus infeasible interior point methods.     

Duality Gaps in Stochastic Integer Programming

In this note, we explore the implications of a result that suggests that the duality gap caused by a Lagrangian relaxation of the nonanticipativity constraints in a stochastic mixed integer (binary) program diminishes as the number of scenarios increases. By way of an example, we illustrate that this is not the case. In general, the duality gap remains bounded away from zero.     

A Riccati-based primal interior point solver for multistage stochastic programming

We propose a new method for certain multistage stochastic programs with linear or nonlinear objective function, combining a primal interior point approach with a linear-quadratic control problem over the scenario tree. The latter problem, which is the direction finding problem for the barrier subproblem is solved through dynamic programming using Riccati equations. In this way we combine the low iteration count of interior point methods with an efficient solver for the subproblems. The computational results are promising. We have solved a financial problem with 1,000,000 scenarios, 15,777,740 variables and 16,888,850 constraints in 20 hours on a moderate computer.     

Two-stage linear decision rules for multi-stage stochastic programming

Multi-stage stochastic linear programs (MSLPs) are notoriously hard to solve in general. Linear decision rules (LDRs) yield an approximation of an MSLP by restricting the decisions at each stage to be an affine function of the observed uncertain parameters. Finding an optimal LDR is a static optimization problem that provides an upper bound on the optimal value of the MSLP, and, under certain assumptions, can be formulated as an explicit linear program. Similarly, as proposed by Kuhn et al. (Math Program 130(1):177–209, 2011) a lower bound for an MSLP can be obtained by restricting decisions in the dual of the MSLP to follow an LDR. We propose a new approximation approach for MSLPs, two-stage LDRs. The idea is to require only the state variables in an MSLP to follow an LDR, which is sufficient to obtain an approximation of an MSLP that is a two-stage stochastic linear program (2SLP). We similarly propose to apply LDR only to a subset of the variables in the dual of the MSLP, which yields a 2SLP approximation of the dual that provides a lower bound on the optimal value of the MSLP. Although solving the corresponding 2SLP approximations exactly is intractable in general, we investigate how approximate solution approaches that have been developed for solving 2SLP can be applied to solve these approximation problems, and derive statistical upper and lower bounds on the optimal value of the MSLP. In addition to potentially yielding better policies and bounds, this approach requires many fewer assumptions than are required to obtain an explicit reformulation when using the standard static LDR approach. A computational study on two example problems demonstrates that using a two-stage LDR can yield significantly better primal policies and modestly better dual policies than using policies based on a static LDR.

     

Risk exposure and Lagrange multipliers of nonanticipativity constraints in multistage stochastic problems

We take advantage of the interpretation of stochastic capacity expansion problems as stochastic equilibrium models for assessing the risk exposure of new equipment in a competitive electricity economy. We develop our analysis on a standard multistage generation capacity expansion problem. We focus on the formulation with nonanticipativity constraints and show that their dual variables can be interpreted as the net margin accruing to plants in the different states of the world. We then propose a procedure to estimate the distribution of the Lagrange multipliers of the nonanticipativity constraints associated with first stage decisions; this gives us the distribution of the discounted cash flow of profitable plants in that stage.     

A Parallel Interior Point Method and Its Application to Facility Location Problems

We present a parallel interior point algorithm to solve block structured linear programs. This algorithm can solve block diagonal linear programs with both side constraints (common rows) and side variables (common columns). The performance of the algorithm is investigated on uncapacitated, capacitated and stochastic facility location problems. The facility location problems are formulated as mixed integer linear programs. Each subproblem of the branch and bound phase of the MIP is solved using the parallel interior point method. We compare the total time taken by the parallel interior point method with the simplex method to solve the complete problems, as well as the various costs of reoptimisation of the non-root nodes of the branch and bound. Computational results on two parallel computers (Fujitsu AP1000 and IBM SP2) are also presented in this paper.     

A constraint shifting homotopy method for general non-linear programming

In this article, a constraint shifting homotopy method (CSHM) is proposed for solving non-linear programming with both equality and inequality constraints. A new homotopy is constructed, and existence and global convergence of a homotopy path determined by it are proven. All problems that can be solved by the combined homotopy interior point method (CHIPM) can also be solved by the proposed method. In contrast to the combined homotopy infeasible interior point method (CHIIPM), it needs a weaker regularity condition. And the starting point in the proposed method is not necessarily a feasible point or an interior point, so it is more convenient to be implemented than CHIPM and CHIIPM. Numerical results show that the proposed algorithm is feasible and effective.     

Subregular recourse in nonlinear multistage stochastic optimization

We consider nonlinear multistage stochastic optimization problems in the spaces of integrable functions. We allow for nonlinear dynamics and general objective functionals, including dynamic risk measures. We study causal operators describing the dynamics of the system and derive the Clarke subdifferential for a penalty function involving such operators. Then we introduce the concept of subregular recourse in nonlinear multistage stochastic optimization and establish subregularity of the resulting systems in two formulations: with built-in nonanticipativity and with explicit nonanticipativity constraints. Finally, we derive optimality conditions for both formulations and study their relations.