Homogeneous Self-dual Algorithms for Stochastic Second-Order Cone Programming

Jin et al. (in J. Optim. Theory Appl. 155:1073–1083, 2012) proposed homogeneous self-dual algorithms for stochastic semidefinite programs with finite event space. In this paper, we utilize their work to derive homogeneous self-dual algorithms for stochastic second-order cone programs with finite event space. We also show how the structure in the stochastic second-order cone programming problems may be exploited so that the algorithms developed for these problems have less complexity than the algorithms developed for stochastic semidefinite programs mentioned above.     

Logarithmic barrier decomposition-based interior point methods for stochastic symmetric programming

We introduce and study two-stage stochastic symmetric programs with recourse to handle uncertainty in data defining (deterministic) symmetric programs in which a linear function is minimized over the intersection of an affine set and a symmetric cone. We present a Benders’ decomposition-based interior point algorithm for solving these problems and prove its polynomial complexity. Our convergence analysis proved by showing that the log barrier associated with the recourse function of stochastic symmetric programs behaves a strongly self-concordant barrier and forms a self-concordant family on the first stage solutions. Since our analysis applies to all symmetric cones, this algorithm extends Zhao’s results [G. Zhao, A log barrier method with Benders’ decomposition for solving two-stage stochastic linear programs, Math. Program. Ser. A 90 (2001) 507–536] for two-stage stochastic linear programs, and Mehrotra and Özevin’s results [S. Mehrotra, M.G. Özevin, Decomposition-based interior point methods for two-stage stochastic semidefinite programming, SIAM J. Optim. 18 (1) (2007) 206–222] for two-stage stochastic semidefinite programs.     

A gaussian upper bound for gaussian multi-stage stochastic linear programs

This paper deals with two-stage and multi-stage stochastic programs in which the right-hand sides of the constraints are Gaussian random variables. Such problems are of interest since the use of Gaussian estimators of random variables is widespread. We introduce algorithms to find upper bounds on the optimal value of two-stage and multi-stage stochastic (minimization) programs with Gaussian right-hand sides. The upper bounds are obtained by solving deterministic mathematical programming problems with dimensions that do not depend on the sample space size. The algorithm for the two-stage problem involves the solution of a deterministic linear program and a simple semidefinite program. The algorithm for the multi-stage problem invovles the solution of a quadratically constrained convex programming problem.     

Stochastic semidefinite programming: a new paradigm for stochastic optimization

Semidefinite programs are a class of optimization problems that have been studied extensively during the past 15 years. Semidefinite programs are naturally related to linear programs, and both are defined using deterministic data. Stochastic programs were introduced in the 1950s as a paradigm for dealing with uncertainty in data defining linear programs. In this paper, we introduce stochastic semidefinite programs as a paradigm for dealing with uncertainty in data defining semidefinite programs.The work of this author was supported in part by the U.S. Army Research Office under Grant DAAD 19-00-1-0465. The material in this paper is part of the doctoral dissertation of this author in preparation at Washington State University.     

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.     

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.     

Stochastic programming with simple integer recourse

Stochastic integer programs are notoriously difficult. Very few properties are known and solution algorithms are very scarce. In this paper, we introduce the class of stochastic programs with simple integer recourse, a natural extension of the simple recourse case extensively studied in stochastic continuous programs.Analytical as well as computational properties of the expected recourse function of simple integer recourse problems are studied. This includes sharp bounds on this function and the study of the convex hull. Finally, a finite termination algorithm is obtained that solves two classes of stochastic simple integer recourse problems.Supported by the National Operations Research Network in the Netherlands (LNMB).     

Primal and dual linear decision rules in stochastic and robust optimization

Linear stochastic programming provides a flexible toolbox for analyzing real-life decision situations, but it can become computationally cumbersome when recourse decisions are involved. The latter are usually modeled as decision rules, i.e., functions of the uncertain problem data. It has recently been argued that stochastic programs can quite generally be made tractable by restricting the space of decision rules to those that exhibit a linear data dependence. In this paper, we propose an efficient method to estimate the approximation error introduced by this rather drastic means of complexity reduction: we apply the linear decision rule restriction not only to the primal but also to a dual version of the stochastic program. By employing techniques that are commonly used in modern robust optimization, we show that both arising approximate problems are equivalent to tractable linear or semidefinite programs of moderate sizes. The gap between their optimal values estimates the loss of optimality incurred by the linear decision rule approximation. Our method remains applicable if the stochastic program has random recourse and multiple decision stages. It also extends to cases involving ambiguous probability distributions.     

Scenario formulation in an algebraic modelling language

Algebraic modelling languages have simplified management of many types of large linear programs but have not specifically supported stochastic modelling. This paper considers modelling language support for multistage stochastic linear recourse problems with finite distributions. We describe basic language requirements for formulation of finite event trees in algebraic modelling languages and show representative problems in AMPL using three commonly used scenario types.     

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.     

Nonlinear semidefinite programming: sensitivity, convergence, and an application in passive reduced-order modeling

We consider the solution of nonlinear programs with nonlinear semidefiniteness constraints. The need for an efficient exploitation of the cone of positive semidefinite matrices makes the solution of such nonlinear semidefinite programs more complicated than the solution of standard nonlinear programs. This paper studies a sequential semidefinite programming (SSP) method, which is a generalization of the well-known sequential quadratic programming method for standard nonlinear programs. We present a sensitivity result for nonlinear semidefinite programs, and then based on this result, we give a self-contained proof of local quadratic convergence of the SSP method. We also describe a class of nonlinear semidefinite programs that arise in passive reduced-order modeling, and we report results of some numerical experiments with the SSP method applied to problems in that class.     

Initialization in semidefinite programming via a self-dual skew-symmetric embedding

The formulation of interior point algorithms for semidefinite programming has become an active research area, following the success of the methods for large-scale linear programming. Many interior point methods for linear programming have now been extended to the more general semidefinite case, but the initialization problem remained unsolved.In this paper we show that the initialization strategy of embedding the problem in a self-dual skew-symmetric problem can also be extended to the semidefinite case. This method also provides a solution for the initialization of quadratic programs and it is applicable to more general convex problems with conic formulation.     

Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs

A rigorous decomposition approach to solve separable mixed-integer nonlinear programs where the participating functions are nonconvex is presented. The proposed algorithms consist of solving an alternating sequence of Relaxed Master Problems (mixed-integer linear program) and two nonlinear programming problems (NLPs). A sequence of valid nondecreasing lower bounds and upper bounds is generated by the algorithms which converge in a finite number of iterations. A Primal Bounding Problem is introduced, which is a convex NLP solved at each iteration to derive valid outer approximations of the nonconvex functions in the continuous space. Two decomposition algorithms are presented in this work. On finite termination, the first yields the global solution to the original nonconvex MINLP and the second finds a rigorous bound to the global solution. Convergence and optimality properties, and refinement of the algorithms for efficient implementation are presented. Finally, numerical results are compared with currently available algorithms for example problems, illuminating the potential benefits of the proposed algorithm.     

Interior-Point Algorithms for Semidefinite Programming Based on a Nonlinear Formulation

Recently in Burer et al. (Mathematical Programming A, submitted), the authors of this paper introduced a nonlinear transformation to convert the positive definiteness constraint on an n × n matrix-valued function of a certain form into the positivity constraint on n scalar variables while keeping the number of variables unchanged. Based on this transformation, they proposed a first-order interior-point algorithm for solving a special class of linear semidefinite programs. In this paper, we extend this approach and apply the transformation to general linear semidefinite programs, producing nonlinear programs that have not only the n positivity constraints, but also n additional nonlinear inequality constraints. Despite this complication, the transformed problems still retain most of the desirable properties. We propose first-order and second-order interior-point algorithms for this type of nonlinear program and establish their global convergence. Computational results demonstrating the effectiveness of the first-order method are also presented.     

The FFTRR-based fast direct algorithms for complex inhomogeneous biharmonic problems with applications to incompressible flows

We develop analysis-based fast and accurate direct algorithms for several biharmonic problems in a unit disk derived directly from the Green’s functions of these problems and compare the numerical results with the “decomposition” algorithms (see Ghosh and Daripa, IMA J. Numer. Anal. 36(2), 824–850 [17]) in which the biharmonic problems are first decomposed into lower order problems, most often either into two Poisson problems or into two Poisson problems and a homogeneous biharmonic problem. One of the steps in the “decomposition algorithm” as discussed in Ghosh and Daripa (IMA J. Numer. Anal. 36(2), 824–850 [17]) for solving certain biharmonic problems uses the “direct algorithm” without which the problem can not be solved. Using classical Green’s function approach for these biharmonic problems, solutions of these problems are represented in terms of singular integrals in the complex z?plane (the physical plane) involving explicitly the boundary conditions. Analysis of these singular integrals using FFT and recursive relations (RR) in Fourier space leads to the development of these fast algorithms which are called FFTRR based algorithms. These algorithms do not need to do anything special to overcome coordinate singularity at the origin as often the case when solving these problems using finite difference methods in polar coordinates. These algorithms have some other desirable properties such as the ease of implementation and parallel in nature by construction. Moreover, these algorithms have O(logN) complexity per grid point where N ² is the total number of grid points and have very low constant behind this order estimate of the complexity. Performance of these algorithms is shown on several test problems. These algorithms are applied to solving viscous flow problems at low and moderate Reynolds numbers and numerical results are presented.     

On Polynomial Optimization Over Non-compact Semi-algebraic Sets

The optimal value of a polynomial optimization over a compact semi-algebraic set can be approximated as closely as desired by solving a hierarchy of semidefinite programs and the convergence is finite generically under the mild assumption that a quadratic module generated by the constraints is Archimedean. We consider a class of polynomial optimization problems with non-compact semi-algebraic feasible sets, for which an associated quadratic module, that is generated in terms of both the objective function and the constraints, is Archimedean. For such problems, we show that the corresponding hierarchy converges and the convergence is finite generically. Moreover, we prove that the Archimedean condition (as well as a sufficient coercivity condition) can be checked numerically by solving a similar hierarchy of semidefinite programs. In other words, under reasonable assumptions, the now standard hierarchy of semidefinite programming relaxations extends to the non-compact case via a suitable modification.     

Overlapping Domain Decomposition Algorithms for General Sparse Matrices

Domain decomposition methods for finite element problems using a partition based on the underlying finite element mesh have been extensively studied. In this paper, we discuss algebraic extensions of the class of overlapping domain decomposition algorithms for general sparse matrices. The subproblems are created with an overlapping partition of the graph corresponding to the sparsity structure of the matrix. These algebraic domain decomposition methods are especially useful for unstructured mesh problems. We also discuss some difficulties encountered in the algebraic extension, particularly the issues related to the coarse solver.     

Stochastic Material and Topology Design

In order to find a robust optimal topology or material design with respect to stochastic variations of the model parameters of a mechanical structure, the basic optimization problem under stochastic uncertainty must be replaced by an appropriate deterministic substitute problem. Starting from the equilibrium equation and the yield/strength conditions, the problem can be formulated as a stochastic (linear) program “with recourse”. Hence, by discretization the design space by finite elements, linearizing the yield conditions, in case of discrete probability distributions the resulting deterministic substitute problems are linear programs with a dual decomposition data structure.     

Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming

Decomposition has proved to be one of the more effective tools for the solution of large-scale problems, especially those arising in stochastic programming. A decomposition method with wide applicability is Benders' decomposition, which has been applied to both stochastic programming as well as integer programming problems. However, this method of decomposition relies on convexity of the value function of linear programming subproblems. This paper is devoted to a class of problems in which the second-stage subproblem(s) may impose integer restrictions on some variables. The value function of such integer subproblem(s) is not convex, and new approaches must be designed. In this paper, we discuss alternative decomposition methods in which the second-stage integer subproblems are solved using branch-and-cut methods. One of the main advantages of our decomposition scheme is that Stochastic Mixed-Integer Programming (SMIP) problems can be solved by dividing a large problem into smaller MIP subproblems that can be solved in parallel. This paper lays the foundation for such decomposition methods for two-stage stochastic mixed-integer programs.     

Decomposition strategy for the stochastic pooling problem

The stochastic pooling problem is a type of stochastic mixed-integer bilinear program arising in the integrated design and operation of various important industrial networks, such as gasoline blending, natural gas production and transportation, water treatment, etc. This paper presents a rigorous decomposition method for the stochastic pooling problem, which guarantees finding an ${\epsilon}$ -optimal solution with a finite number of iterations. By convexification of the bilinear terms, the stochastic pooling problem is relaxed into a lower bounding problem that is a potentially large-scale mixed-integer linear program (MILP). Solution of this lower bounding problem is then decomposed into a sequence of relaxed master problems, which are MILPs with much smaller sizes, and primal bounding problems, which are linear programs. The solutions of the relaxed master problems yield a sequence of nondecreasing lower bounds on the optimal objective value, and they also generate a sequence of integer realizations defining the primal problems which yield a sequence of nonincreasing upper bounds on the optimal objective value. The decomposition algorithm terminates finitely when the lower and upper bounds coincide (or are close enough), or infeasibility of the problem is indicated. Case studies involving two example problems and two industrial problems demonstrate the dramatic computational advantage of the proposed decomposition method over both a state-of-the-art branch-and-reduce global optimization method and explicit enumeration of integer realizations, particularly for large-scale problems.