Stability of the Feasible Set Mapping of Linear Systems with an Exact Constraint Set

This paper deals with the stability of the feasible set mapping of linear systems of an arbitrary number (possibly infinite) of equations and inequalities such that the variable x ranges on a certain fixed constraint set X?? ⁿ (X could represent the solution set of a given constraint system, e.g., the positive cone of ? ⁿ in the case of sign constraints). More in detail, the paper provides necessary as well as sufficient conditions for the lower and upper semicontinuity (in Berge sense), and the closedness, of the set-valued mapping which associates, with any admissible perturbation of the given (nominal) system its feasible set. The parameter space is formed by all the systems having the same structure (i.e., the same number of variables, equations and inequalities) as the nominal one, and the perturbations are measured by means of the pseudometric of the uniform convergence.     

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.     

On the Stability of the Feasible Set in Linear Optimization

This paper deals with the stability of two families of linear optimization problems, each one formed by the dual problems to the members of the other family. We characterize the problems of these families that are stable in the sense that they remain consistent (inconsistent) under sufficiently small arbitrary perturbations of all the data. This characterization is established in terms of the lower semicontinuity property of the feasible set mapping and the boundedness of the optimal set of the corresponding coupled problem. Other continuity properties of the feasible set mapping are also derived. This stability theory extends some well-known theorems of Williams and Robinson on the stability of ordinary linear programming problems to linear optimization problems with infinitely many variables or constraints.     

On the stability of infinite-dimensional linear inequality systems

The principal aim of this paper is to study the stability of the solution set mapping of a system composed by an arbitrary set of linear inequalities in an infinite-dimensional space. The unknowns space is assumed to be metrizable, which allows us to measure the size of any possible perturbation. Conditions guaranteeing the closedness, the lower semicontinuity and the upper semicontmuity of this mapping, at a particular nominal system, are given in the paper. The more significant differences with respect to the finite dimensional case, previously approached in the context of the so-called semi-infinite optimization, are illustrated by means of convenient examples.     

Solving Strategies and Well-Posedness in Linear Semi-Infinite Programming

In this paper we introduce the concept of solving strategy for a linear semi-infinite programming problem, whose index set is arbitrary and whose coefficient functions have no special property at all. In particular, we consider two strategies which either approximately solve or exactly solve the approximating problems, respectively. Our principal aim is to establish a global framework to cope with different concepts of well-posedness spread out in the literature. Any concept of well-posedness should entail different properties of these strategies, even in the case that we are not assuming the boundedness of the optimal set. In the paper we consider three desirable properties, leading to an exhaustive study of them in relation to both strategies. The more significant results are summarized in a table, which allows us to show the double goal of the paper. On the one hand, we characterize the main features of each strategy, in terms of certain stability properties (lower and upper semicontinuity) of the feasible set mapping, optimal value function and optimal set mapping. On the other hand, and associated with some cells of the table, we recognize different notions of Hadamard well-posedness. We also provide an application to the analysis of the Hadamard well-posedness for a linear semi-infinite formulation of the Lagrangian dual of a nonlinear programming problem.     

Topological stability of linear semi-infinite inequality systems

In this note, we analyze the relationship between the lower semicontinuity of the feasible set mapping for linear semi-infinite inequality systems and the so-called topological stability, which is held when the solution sets of all the systems obtained by sufficiently small perturbations of the data are homeomorphic to each other. This topological stability and its relation with the Mangasarian-Fromovitz constraints qualification have been studied deeply by Jongen et al. in Ref. 1. The main difference of our approach is that we are not assuming any kind of structure for the index set and, consequently, any particular property for the functional dependence between the inequalities and the associated indices. In addition, we deal with systems whose solution sets are not necessarily bounded.This work has been supported partially by the DGICYT of Spain, Grant PB93-0943, by Generalitat Valenciana, Grant GV-2219/94, and by IVEI, Grant 003/026.The authors would like to thank J. E. Martínez Legaz for his valuable comments.     

Regularity modulus of arbitrarily perturbed linear inequality systems

We aim to quantify the stability of systems of (possibly infinitely many) linear inequalities under arbitrary perturbations of the data. Our focus is on the Aubin property (also called pseudo-Lipschitz) of the solution set mapping, or, equivalently, on the metric regularity of its inverse mapping. The main goal is to determine the regularity modulus of the latter mapping exclusively in terms of the system's data. In our context, both, the right- and the left-hand side of the system are subject to possible perturbations. This fact entails notable differences with respect to previous developments in the framework of linear systems with perturbations of the right-hand side. In these previous studies, the feasible set mapping is sublinear (which is not our current case) and the well-known Radius Theorem constitutes a useful tool for determining the modulus. In our current setting we do not have an explicit expression for the radius of metric regularity, and we have to tackle the modulus directly. As an application we approach, under appropriate assumptions, the regularity modulus for a semi-infinite system associated with the Lagrangian dual of an ordinary nonlinear programming problem.     

On the Stability of Generalized Vector Quasivariational Inequality Problems

In this paper, we obtain some stability results for generalized vector quasivariational inequality problems. We prove that the solution set is a closed set and establish the upper semicontinuity property of the solution set for perturbed generalized vector quasivariational inequality problems. These results extend those obtained in Ref. 1. We obtain also the lower semicontinuity property of the solution set for perturbed classical variational inequalities. Several examples are given for the illustration of our results.     

Continuity and Stability of a Quadratic Mixed-Integer Stochastic Program

For the two-stage quadratic stochastic program where the second-stage problem is a general mixed-integer quadratic program with a random linear term in the objective function and random right-hand sides in constraints, we study continuity properties of the second-stage optimal value as a function of both the first-stage policy and the random parameter vector. We also present sufficient conditions for lower or upper semicontinuity, continuity, and Lipschitz continuity of the second-stage problem's optimal value function and the upper semicontinuity of the optimal solution set mapping with respect to the first-stage variables and/or the random parameter vector. These results then enable us to establish conclusions on the stability of optimal value and optimal solutions when the underlying probability distribution is perturbed with respect to the weak convergence of probability measures.     

Calmness of partially perturbed linear systems with an application to the central path

ABSTRACT

In this paper we develop point-based formulas for the calmness modulus of the feasible set mapping in the context of linear inequality systems with a fixed abstract constraint and (partially) perturbed linear constraints. The case of totally perturbed linear systems was previously analyzed in [Cánovas MJ, López MA, Parra J, et al. Calmness of the feasible set mapping for linear inequality systems. Set-Valued Var Anal. 2014;22:375–389, Section 5]. We point out that the presence of such an abstract constraint yields the current paper to appeal to a notable different methodology with respect to previous works on the calmness modulus in linear programming. The interest of this model comes from the fact that partially perturbed systems naturally appear in many applications. As an illustration, the paper includes an example related to the classical central path construction. In this example we consider a certain feasible set mapping whose calmness modulus provides a measure of the convergence of the central path. Finally, we underline the fact that the expression for the calmness modulus obtained in this paper is (conceptually) implementable as far as it only involves the nominal data.     

Stability in linear optimization and related topics. A personal tour

This paper is a kind of biased survey of the most representative and recent results on stability for the linear optimization problem. Qualitative and quantitative approaches are considered in this survey, and some infinite-dimensional extensions of the main results to more general problems are also included. In particular the paper deals with the lower/upper semicontinuity of the feasible/optimal set mappings, different types of ill-posedness, distance to ill-posedness, Lipschitz properties of these mappings under different types of perturbations, and estimates of the associated Lipschitz bounds.     

Semicontinuity and convergence for vector optimization problems with approximate equilibrium constraints

This paper mainly intends to present some semicontinuity and convergence results for perturbed vector optimization problems with approximate equilibrium constraints. We establish the lower semicontinuity of the efficient solution mapping for the vector optimization problem with perturbations of both the objective function and the constraint set. The constraint set is the set of approximate weak efficient solutions of the vector equilibrium problem. Moreover, upper Painlevé–Kuratowski convergence results of the weak efficient solution mapping are showed. Finally, some applications to the optimization problems with approximate vector variational inequality constraints and the traffic network equilibrium problems are also given. Our main results are different from the ones in the literature.     

Continuity of the optimal value function in indefinite quadratic programming

This paper characterizes the continuity property of the optimal value function in a general parametric quadratic programming problem with linear constraints. The lower semicontinuity and upper semicontinuity properties of the optimal value function are studied as well.     

Upper semicontinuity result for the solution mapping of a mixed parametric generalized vector quasiequilibrium problem with moving cones

In this paper, we give sufficient conditions for the upper semicontinuity property of the solution mapping of a parametric generalized vector quasiequilibrium problem with mixed relations and moving cones. The main result is proven under the assumption that moving cones have local openness/local closedness properties and set-valued maps are cone-semicontinuous in a sense weaker than the usual sense of semicontinuity. The nonemptiness and the compactness of the solution set are also investigated.     

Calmness of the Argmin Mapping in Linear Semi-Infinite Optimization

This paper characterizes the calmness property of the argmin mapping in the framework of linear semi-infinite optimization problems under canonical perturbations; i.e., continuous perturbations of the right-hand side of the constraints (inequalities) together with perturbations of the objective function coefficient vector. This characterization is new for semi-infinite problems without requiring uniqueness of minimizers. For ordinary (finitely constrained) linear programs, the calmness of the argmin mapping always holds, since its graph is piecewise polyhedral (as a consequence of a classical result by Robinson). Moreover, the so-called isolated calmness (corresponding to the case of unique optimal solution for the nominal problem) has been previously characterized. As a key tool in this paper, we appeal to a certain supremum function associated with our nominal problem, not involving problems in a neighborhood, which is related to (sub)level sets. The main result establishes that, under Slater constraint qualification, perturbations of the objective function are negligible when characterizing the calmness of the argmin mapping. This result also states that the calmness of the argmin mapping is equivalent to the calmness of the level set mapping.     

Stability in convex semi-infinite programming and rates of convergence of optimal solutions of discretized finite subproblems

We consider convex semiinfinite programming (SIP) problems with an arbitrary fixed index set T. The article analyzes the relationship between the upper and lower semicontinuity (lsc) of the optimal value function and the optimal set mapping, and the so-called Hadamard well-posedness property (allowing for more than one optimal solution). We consider the family of all functions involved in some fixed optimization problem as one element of a space of data equipped with some topology, and arbitrary perturbations are premitted as long as the perturbed problem continues to be convex semiinfinite. Since no structure is required for T, our results apply to the ordinary convex programming case. We also provide conditions, not involving any second order optimality one, guaranteeing that the distance between optimal solutions of the discretized subproblems and the optimal set of the original problem decreases by a rate which is linear with respect to the discretization mesh-size.     

Continuity of the efficient solution mapping for vector optimization problems

This paper aims at investigating the continuity of the efficient solution mapping of perturbed vector optimization problems. First, we introduce the concept of the level mapping. We give sufficient conditions for the upper semicontinuity and the lower semicontinuity of the level mapping. The upper semicontinuity and the lower semicontinuity of the efficient solution mapping are established by using the continuity properties of the level mapping. We establish a corollary about the lower semicontinuity of the minimal point set-valued mapping. Meanwhile, we give some examples to illustrate that the corollary is different from the ones in the literature.     

Stability analysis for vector quasiequilibrium problems

This paper is devoted to the continuity of the solution mapping for vector quasiequilibrium problems under mapping perturbations. We show that the solution mapping is upper semicontinuous and Hausdorff upper semicontinuous. Sufficient conditions for the lower semicontinuity and Hausdorff lower semicontinuity of the solution mapping are established. Finally, we apply our results to traffic network problems as example.     

On the stability of closed-convex-valued mappings and the associated boundaries

This paper deals with the stability properties of those set-valued mappings from locally metrizable spaces to Euclidean spaces for which the images are the convex hull of their boundaries (i.e., they are closed convex sets not containing a halfspace). Examples of this class of mappings are the feasible set and the optimal set of convex optimization problems, and the solution set of convex systems, when the data are subject to perturbations. More in detail, we associate with the given set-valued mapping its corresponding boundary mapping and we analyze the transmission of the stability properties (lower and upper semicontinuity, continuity and closedness) from the given mapping to its boundary and vice versa.