Quantitative stability of mixed-integer two-stage quadratic stochastic programs

For our introduced mixed-integer quadratic stochastic program with fixed recourse matrices, random recourse costs, technology matrix and right-hand sides, we study quantitative stability properties of its optimal value function and optimal solution set when the underlying probability distribution is perturbed with respect to an appropriate probability metric. To this end, we first establish various Lipschitz continuity results about the value function and optimal solutions of mixed-integer parametric quadratic programs with parameters in the linear part of the objective function and in the right-hand sides of linear constraints. The obtained results extend earlier results about quantitative stability properties of stochastic integer programming and stability results for mixed-integer parametric quadratic programs.     

Quantitative stability of full random two-stage stochastic programs with recourse

In this paper, we consider quantitative stability analysis for two-stage stochastic linear programs when recourse costs, the technology matrix, the recourse matrix and the right-hand side vector are all random. For this purpose, we first investigate continuity properties of parametric linear programs. After deriving an explicit expression for the upper bound of its feasible solutions, we establish locally Lipschitz continuity of the feasible solution sets of parametric linear programs. These results are then applied to prove continuity of the generalized objective function derived from the full random second-stage recourse problem, from which we derive new forms of quantitative stability results of the optimal value function and the optimal solution set with respect to the Fortet–Mourier probability metric. The obtained results are finally applied to establish asymptotic behavior of an empirical approximation algorithm for full random two-stage stochastic programs.     

Convex Parametric Programming in Abstract Spaces

This article studies stability and optimality for convex parametric programming models in abstract spaces. Necessary conditions for continuity of the feasible set mapping are given in complete metric spaces. This continuity is characterized for models in which the space of decision variables is reflexive Banach space. The main result on optimality characterizes locally optimal parameters relative to stable perturbations of the parameter. The result is stated in terms of the existence of a saddle-point for a Lagrangian that uses a finite Borel measure. It does not hold for unstable perturbations even if the model is finite dimensional. The results are applicable to various formulations of control and optimal control problems.     

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.     

Performance evaluation of fault-tolerant routing algorithms: an optimization problem

In this paper, we present a new theoretical approach for studying the behaviour and the performance of shortest paths fault-tolerant distributed algorithms of a certain class. The behaviour of each processor is modeled by means of a stochastic matrix. We show that achieving the optimal behaviour of Nprocessors is equivalent to solvingan optimization problem of a function of 2N variables under constraints; this function is neither convex nor concave. Solutions for which such a type of algorithms has an optimal behaviour are derived. Using that result, we build a fuzzy set of solutions which provides a global overview (a sort of “relief”): each solution of the fuzzy set has value ? ranging between 0 and 1, which may be regarded as its“bench-mark” so (1 -?) points out the proximity of any solution from the optimal solution     

Global multi-parametric optimal value bounds and solution estimates for separable parametric programs

In this tutorial, a strategy is described for calculating parametric piecewise-linear optimal value bounds for nonconvex separable programs containing several parameters restricted to a specified convex set. The methodology is based on first fixing the value of the parameters, then constructing sequences of underestimating and overestimating convex programs whose optimal values respectively increase or decrease to the global optimal value of the original problem. Existing procedures are used for calculating parametric lower bounds on the optimal value of each underestimating problem and parametric upper bounds on the optimal value of each overestimating problem in the sequence, over the given set of parameters. Appropriate updating of the bounds leads to a nondecreasing sequence of lower bounds and a nonincreasing sequence of upper bounds, on the optimal value of the original problem, continuing until the bounds satisfy a specified tolerance at the value of the parameter that was fixed at the outset. If the bounds are also sufficiently tight over the entire set of parameters, according to criteria specified by the user, then the calculation is complete. Otherwise, another parameter value is selected and the procedure is repeated, until the specified criteria are satisfied over the entire set of parameters. A parametric piecewise-linear solution vector approximation is also obtained. Results are expected in the theory, computations, and practical applications. The general idea of developing results for general problems that are limits of results that hold for a sequence of well-behaved (e.g., convex) problems should be quite fruitful.     

On the Continuity of the Optimal Value in Parametric Linear Optimization: Stable Discretization of the Lagrangian Dual of Nonlinear Problems

This paper is focused on the stability of the optimal value, and its immediate repercussion on the stability of the optimal set, for a general parametric family of linear optimization problems in ⁿ. In our approach, the parameter ranges over an arbitrary metric space, and each parameter determines directly a set of coefficient vectors describing the linear system of constraints. Thus, systems associated with different parameters are not required to have the same number (cardinality) of inequalities. In this way, discretization techniques for solving a nominal linear semi-infinite optimization problem may be modeled in terms of suitable parametrized problems. The stability results given in the paper are applied to the stability analysis of the Lagrangian dual associated with a parametric family of nonlinear programming problems. This dual problem is translated into a linear (semi-infinite) programming problem and, then, we prove that the lower semicontinuity of the corresponding feasible set mapping, the continuity of the optimal value function, and the upper semicontinuity of the optimal set mapping are satisfied. Then, the paper shows how these stability properties for the dual problem entail a nice behavior of parametric approximation and discretization strategies (in which an ordinary linear programming problem may be considered in each step). This approximation–discretization process is formalized by means of considering a double parameter: the original one and the finite subset of indices (grid) itself. Finally, the convex case is analyzed, showing that the referred process also allows us to approach the primal problem.Mathematics Subject Classifications (2000) Primary 90C34, 90C31; secondary 90C25, 90C05.     

Existence of fixed points for mappings of finite sets

We show that the existence theorem for zeros of a vector field (fixed points of a mapping) holds in the case of a “convex” finite set X and a “continuous” vector field (a self-mapping) directed inwards into the convex hull co X of X. The main goal is to give correct definitions of the notions of “continuity” and “convexity”. We formalize both these notions using a reflexive and symmetric binary relation on X, i.e., using a proximity relation. Continuity (we shall say smoothness) is formulated with respect to any proximity relation, and an additional requirement on the proximity (we shall call it the acyclicity condition) transforms X into a “convex” set. If these two requirements are satisfied, then the vector field has a zero (i.e., a fixed point).     

Bilevel convex programming models

Bilevel convex models are studied after being cast into a parametric programming form. This form has a lexicographic inner-outer structure where the optimal value of the outer model is optimized on the set of optimal solutions of the inner model. Optimal solutions are characterized using a Lagrangian saddle-point approach and a marginal value formula is given for the outer model. These are used to formulate a general method for finding an optimal solution by input optimization.     

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.     

Continuity of the optimal value function and optimal solutions of parametric mixed-integer quadratic programs

To properly describe and solve complex decision problems, research on theoretical properties and solution of mixed-integer quadratic programs is becoming very important. We establish in this paper different Lipschitz-type continuity results about the optimal value function and optimal solutions of mixed-integer parametric quadratic programs with parameters in the linear part of the objective function and in the right-hand sides of the linear constraints. The obtained results extend some existing results for continuous quadratic programs, and, more importantly, lay the foundation for further theoretical study and corresponding algorithm analysis on mixed-integer quadratic programs.     

When are static and adjustable robust optimization problems with constraint-wise uncertainty equivalent?

Adjustable robust optimization (ARO) generally produces better worst-case solutions than static robust optimization (RO). However, ARO is computationally more difficult than RO. In this paper, we provide conditions under which the worst-case objective values of ARO and RO problems are equal. We prove that when the uncertainty is constraint-wise, the problem is convex with respect to the adjustable variables and concave with respect to the uncertain parameters, the adjustable variables lie in a convex and compact set and the uncertainty set is convex and compact, then robust solutions are also optimal for the corresponding ARO problem. Furthermore, we prove that if some of the uncertain parameters are constraint-wise and the rest are not, then under a similar set of assumptions there is an optimal decision rule for the ARO problem that does not depend on the constraint-wise uncertain parameters. Also, we show for a class of problems that using affine decision rules that depend on all of the uncertain parameters yields the same optimal objective value as when the rules depend solely on the non-constraint-wise uncertain parameters. Finally, we illustrate the usefulness of these results by applying them to convex quadratic and conic quadratic problems.     

A parametric solution algorithm for a class of rank-two nonconvex programs

The aim of this paper is to propose a solution algorithm for a particular class of rank-two nonconvex programs having a polyhedral feasible region. The algorithm lies within the class of the so called “optimal level solutions” parametric methods. The subproblems obtained by means of this parametrical approach are quadratic convex ones, but not necessarily neither strictly convex nor linear. For this very reason, in order to solve in an unifying framework all of the considered rank-two nonconvex programs a new approach needs to be proposed. The efficiency of the algorithm is improved by means of the use of underestimation functions. The results of a computational test are provided and discussed.     

Maximal Monotone Multifunctions of Brøndsted–Rockafellar Type

We consider whether the “inequality-splitting” property established in the Brøndsted–Rockafellar theorem for the subdifferential of a proper convex lower semicontinuous function on a Banach space has an analog for arbitrary maximal monotone multifunctions. We introduce the maximal monotone multifunctions of type (ED), for which an “inequality-splitting” property does hold. These multifunctions form a subclass of Gossez"s maximal monotone multifunctions of type (D); however, in every case where it has been proved that a multifunction is maximal monotone of type (D) then it is also of type (ED). Specifically, the following maximal monotone multifunctions are of type (ED): ? ultramaximal monotone multifunctions, which occur in the study of certain nonlinear elliptic functional equations; ? single-valued linear operators that are maximal monotone of type (D); ? subdifferentials of proper convex lower semicontinuous functions; ? “subdifferentials” of certain saddle-functions. We discuss the negative alignment set of a maximal monotone multifunction of type (ED) with respect to a point not in its graph – a mysterious continuous curve without end-points lying in the interior of the first quadrant of the plane. We deduce new inequality-splitting properties of subdifferentials, almost giving a substantial generalization of the original Brøndsted–Rockafellar theorem. We develop some mathematical infrastructure, some specific to multifunctions, some with possible applications to other areas of nonlinear analysis: ? the formula for the biconjugate of the pointwise maximum of a finite set of convex functions – in a situation where the “obvious” formula for the conjugate fails; ? a new topology on the bidual of a Banach space – in some respects, quite well behaved, but in other respects, quite pathological; ? an existence theorem for bounded linear functionals – unusual in that it does not assume the existence of any a priori bound; ? the 'big convexification" of a multifunction.

     

Stability in multistage stochastic programming

Multistage stochastic programs are regarded as mathematical programs in a Banach spaceX of summable functions. Relying on a result for parametric programs in Banach spaces, the paper presents conditions under which linearly constrained convex multistage problems behave stably when the (input) data process is subjected to (small) perturbations. In particular, we show the persistence of optimal solutions, the local Lipschitz continuity of the optimal value and the upper semicontinuity of optimal sets with respect to the weak topology inX. The linear case with deterministic first-stage decisions is studied in more detail.This research has been supported by the Schwerpunktprogramm Anwendungsbezogene Optimierung und Steuerung of the Deutsche Forschungsgemeinschaft.     

On the stability of general convex programs under slater’s condition and primal solution boundedness

This paper was motivated by an article by Best and Chakravarti, who presented some stability results for convex quadratic programs under linear perturbation of the data. We show that the regularity conditions assumed are much too restrictive and demonstrate that stronger stability results follow under weaker assumptions (primal solution boundedness and the Slater condition) and from known results, not only for convex quadratic problems but for general convex programs with general perturbations. In so doing, we give a simple and reasonably complete characterization of the stability of an important class of well-behaved convex programs, collecting results that heretofore have apparently not been presented in a unified manner. The results, virtually all from Hogan and Robinson, involve mainly stability of the feasible region and solution existence under small perturbations, and continuity and differentiability of the optimal value function. We note that Auslender and Coutat have recently provided similar extensions for saddle points of generalized linear-quadratic programs introduced by Rockafellar and Wets, utilizing the same assumptions that we use in this paper     

Parametric Disjunctive Programming: One-Sided Differentiability of the Value Function

We consider a countable family of one-parameter convex programs and give sufficient conditions for the one-sided differentiability of its optimal value function. The analysis is based on the Borwein dual problem for a family of convex programs (a convex disjunctive program). We give conditions that assure stability of the situation of perfect duality in the Borwein theory.For the reader's convenience, we start with a review of duality results for families of convex programs. A parametric family of dual problems is introduced that contains the dual problems of Balas and Borwein as special cases. In addition, a vector optimization problem is defined as a dual problem. This generalizes a result by Helbig about families of linear programs.