On structure and stability in stochastic programs with random technology matrix and complete integer recourse

For two-stage stochastic programs with integrality constraints in the second stage, we study continuity properties of the expected recourse as a function both of the first-stage policy and the integrating probability measure.Sufficient conditions for lower semicontinuity, continuity and Lipschitz continuity with respect to the first-stage policy are presented. Furthermore, joint continuity in the policy and the probability measure is established. This leads to conclusions on the stability of optimal values and optimal solutions to the two-stage stochastic program when subjecting the underlying probability measure to perturbations.This research is supported by the Schwerpunktprogramm Anwendungsbezogene Optimierung und Steuerung of the Deutsche Forschungsgemeinschaft.The main part of the paper was written while the author was an assistant at the Department of Mathematics at Humboldt University Berlin.     

Continuous Selection and Unique Polyhedral Representation of Solutions to Convex Parametric Quadratic Programs

A method for obtaining continuous solutions to convex quadratic and linear programs with parameters in the linear part of the objective function and right-hand side of the constraints is presented. For parameter values for which the problem has nonunique solutions, the optimizer with the least Euclidean norm is selected. The normal cone optimality condition is utilized to obtain a unique polyhedral representation of the piecewise affine minimizer function. This research is part of the Strategic University Program on Computational Methods for Nonlinear Motion Control funded by the Research Council of Norway. We thank Dr. E.C. Kerrigan at the Department of Electrical Engineering, Imperial College, London and Dr. Colin Jones at ETH Zürich for their comments. Finally, we thank the anonymous reviewers for their comments.     

Continuity of the Solution Map in Quadratic Programs under Linear Perturbations

It is well known that the solution map of a quadratic program where only the linear part of the data is subject to perturbation is an upper Lipschitz multifunction. This paper characterizes the continuity and lower semicontinuity of that solution map.This work was supported by the Brain Korea 21 Project in 2003, the APEC Postdoctoral Fellowships Program, and the KOSEF Brain Pool Program. The authors thank Professor F. Giannessi and two anonymous referees for helpful comments.Communicated by F. Giannessi     

Quantitative stability of fully random mixed-integer two-stage stochastic programs

Mixed-integer two-stage stochastic programs with fixed recourse matrix, random recourse costs, technology matrix, and right-hand sides are considered. Quantitative continuity properties of its optimal value and solution set are derived when the underlying probability distribution is perturbed with respect to an appropriate probability metric.     

Continuity of solutions for parametric variational inequalities in Banach space

We consider here a type of pseudo-monotone parametric variational inequalities on a class of Banach spaces and show that such problems admit continuous (with respect to the parameter) solutions, as long as generic existence and uniqueness conditions for these solutions are satisfied. In particular, we show that such results are valid on a class of Banach spaces whenever we deal with strong pseudo-monotonicity, while others are valid in Hilbert spaces, whenever strict monotonicity is present. We also provide examples to illustrate the new results.     

Uniqueness of Limit Cycle for the Quadratic Systems with Weak Saddle and Focus

It is proved that the quadratic system with a weak saddle has at most one limit cycle,andthat if this system has a separatrix cycle passing through the weak saddle,then the stability of theseparatrix cycle is contrary to that of the singular point surrounded by it.     

The continuity of the optimum in parametric programming and applications to stochastic programming

It is proved a sufficient condition that the optimal value of a linear program be a continuous function of the coefficients. The condition isessential, in the sense that, if it is not imposed, then examples with discontinuous optimal-value function may be found. It is shown that certain classes of linear programs important in applications satisfy this condition. Using the relation between parametric linear programming and the distribution problem in stochastic programming, a necessary and sufficient condition is given that such a program has optimal value. Stable stochastic linear programs are introduced, and a sufficient condition of such stability, important in computation problems, is established.This note is a slightly modified version of a paper presented at the Institute of Econometrics and Operations Research of the University of Bonn, Bonn, Germany, 1972.The author is grateful to G. B. Dantzig and S. Karamardian for useful comments on an earlier draft of this paper. In particular, S. Karamardian proposed modifications which made clearer the proof of Lemma 2.1.     

Uniqueness of Limit Cycle for the Quadratic Systems with Weak Saddle and Focus

It is proved that the quadratic system with a weak saddle has at most one limit cycle, and that if this system has a separatrix cycle passing through the weak saddle, then the stability of the separatrix cycle is contrary to that of the singular point surrounded by it.     

Quadratic convergence of a special quasi-cyclic Jacobi method

This paper considers the ultimate asymptotic convergence of a block- oriented, quasi-cyclic Jacobi method for symmetric matrices. The conclusion applies to the new one-sided Jacobi method for computing the singular value decomposition, recently proposed by Drmač and Veselić. Using a simple qualitative analysis, the discussion indicates that a quadratic off-norm reduction per quasi-sweep is to be expected in all perceivable cases.      

Stability of weak vector variational inequality

In this paper, a key assumption is introduced by virtue of a parametric gap function. Then, by using the key assumption, sufficient conditions of the continuity and Hausdorff continuity of a solution set map for a parametric weak vector variational inequality are obtained in Banach spaces with the objective space being finite-dimensional.     

Some Aspects of Stability in Stochastic Programming

Some developments in structure and stability of stochastic programs during the last decade together with interrelations to optimization theory and stochastics are reviewed. With weak convergence of probability measures as a backbone we discuss qualitative and quantitative stability of recourse models that possibly involve integer variables. We sketch stability in chance constrained stochastic programming and provide some applications in statistical estimation. Finally, an outlook is devoted to issues that were not discussed in detail and to some open problems.     

Convergence Properties of Two-Stage Stochastic Programming

This paper considers a procedure of two-stage stochastic programming in which the performance function to be optimized is replaced by its empirical mean. This procedure converts a stochastic optimization problem into a deterministic one for which many methods are available. Another strength of the method is that there is essentially no requirement on the distribution of the random variables involved. Exponential convergence for the probability of deviation of the empirical optimum from the true optimum is established using large deviation techniques. Explicit bounds on the convergence rates are obtained for the case of quadratic performance functions. Finally, numerical results are presented for the famous news vendor problem, which lends experimental evidence supporting exponential convergence.     

Convergence Analysis of an Inexact Potential Reduction Method for Convex Quadratic Programming

We analyze the convergence of an infeasible inexact potential reduction method for quadratic programming problems. We show that the convergence of this method is achieved if the residual of the KKT system satisfies a bound related to the duality gap. This result suggests stopping criteria for inner iterations that can be used to adapt the accuracy of the computed direction to the quality of the potential reduction iterate in order to achieve computational efficiency. This research was partially supported by the Italian MIUR, Project FIRB—Large Scale Nonlinear Optimization # RBNE01WBBB and Project PRIN—Innovative Problems and Methods in Nonlinear Optimization # 2005017083.     

Stochastic capacity expansion with multiple sources of capacity

In this paper, we consider the multi-period single resource stochastic capacity expansion problem with three sources of capacity: permanent, contract, and spot market. The problem is modeled as a multi-stage stochastic integer program. We show that the problem has the totally unimodular property and develop polynomial-time primal and dual algorithms to solve the problem.     

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 Sequential Quadratically Constrained Quadratic Programming Method of Feasible Directions

In this paper, a sequential quadratically constrained quadratic programming method of feasible directions is proposed for the optimization problems with nonlinear inequality constraints. At each iteration of the proposed algorithm, a feasible direction of descent is obtained by solving only one subproblem which consist of a convex quadratic objective function and simple quadratic inequality constraints without the second derivatives of the functions of the discussed problems, and such a subproblem can be formulated as a second-order cone programming which can be solved by interior point methods. To overcome the Maratos effect, an efficient higher-order correction direction is obtained by only one explicit computation formula. The algorithm is proved to be globally convergent and superlinearly convergent under some mild conditions without the strict complementarity. Finally, some preliminary numerical results are reported. Project supported by the National Natural Science Foundation (No. 10261001), Guangxi Science Foundation (Nos. 0236001, 064001), and Guangxi University Key Program for Science and Technology Research (No. 2005ZD02) of China.     

概率约束规划逼近最优解集的稳定性和最优值的连续性

在原始规划可行集上引入了正则的概念,并在此正则条件下,研究了更一般的概率约束规划问题的稳定性.在一定的条件下,得到了概率约束规划逼近最优解集的稳定性和最优值的连续性,从而对近似求解这类问题提供了某种理论依据.     

Convergent Cutting-Plane and Partial-Sampling Algorithm for Multistage Stochastic Linear Programs with Recourse

We propose an algorithm for multistage stochastic linear programs with recourse where random quantities in different stages are independent. The algorithm approximates successively expected recourse functions by building up valid cutting planes to support these functions from below. In each iteration, for the expected recourse function in each stage, one cutting plane is generated using the dual extreme points of the next-stage problem that have been found so far. We prove that the algorithm is convergent with probability one.     

Stability Radii of Some Stochastic Differential Equations

Characterizations of the stability radii of a stable linear stochastic Itô system with respect to structured stochastic multiperturbations are given. We extend some results in [1], [2]     

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.