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.     

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.     

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.     

Critical Objective Size and Calmness Modulus in Linear Programming

This paper introduces the concept of critical objective size associated with a linear program in order to provide operative point-based formulas (only involving the nominal data, and not data in a neighborhood) for computing or estimating the calmness modulus of the optimal set (argmin) mapping under uniqueness of nominal optimal solution and perturbations of all coefficients. Our starting point is an upper bound on this modulus given in Cánovas et al. (4). In this paper we prove that this upper bound is attained if and only if the norm of the objective function coefficient vector is less than or equal to the critical objective size. This concept also allows us to obtain operative lower bounds on the calmness modulus. We analyze in detail an illustrative example in order to explore some strategies that can improve the referred upper and lower bounds.     

On Implicit Active Constraints in Linear Semi-Infinite Programs with Unbounded Coefficients

The concept of implicit active constraints at a given point provides useful local information about the solution set of linear semi-infinite systems and about the optimal set in linear semi-infinite programming provided the set of gradient vectors of the constraints is bounded, commonly under the additional assumption that there exists some strong Slater point. This paper shows that the mentioned global boundedness condition can be replaced by a weaker local condition (LUB) based on locally active constraints (active in a ball of small radius whose center is some nominal point), providing geometric information about the solution set and Karush-Kuhn-Tucker type conditions for the optimal solution to be strongly unique. The maintaining of the latter property under sufficiently small perturbations of all the data is also analyzed, giving a characterization of its stability with respect to these perturbations in terms of the strong Slater condition, the so-called Extended-Nürnberger condition, and the LUB condition.     

Sensitivity analysis in linear semi-infinite programming: Perturbing cost and right-hand-side coefficients

This paper analyzes the effect on the optimal value of a given linear semi-infinite programming problem of the kind of perturbations which more frequently arise in practical applications: those which affect the objective function and the right-hand-side coefficients of the constraints. In particular, we give formulae which express the exact value of a perturbed problem as a linear function of the perturbation.     

A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem

We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig–Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.     

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 sensitivity of central solutions in semidefinite programming

In this paper we study the properties of the analytic central path of a semidefinite programming problem under perturbation of the right hand side of the constraints, including the limiting behavior when the central optimal solution, namely the analytic center of the optimal set, is approached. Our analysis assumes the primal-dual Slater condition and the strict complementarity condition. Our findings are as follows. First, on the negative side, if we view the central optimal solution as a function of the right hand side of the constraints, then this function is not continuous in general, whereas in the linear programming case this function is known to be Lipschitz continuous. On the positive side, compared with the previous conclusion we obtain a (seemingly) paradoxical result: on the central path any directional derivative with respect to the right hand side of the constraints is bounded, and even converges as the central optimal solution is approached. This phenomenon is possible due to the lack of a uniform bound on the derivatives with respect to the right hand side parameters. All these results are based on the strict complementarity assumption. Concerning this last property we give an example. In that example the set of right hand side parameters for which the strict complementarity condition holds is neither open nor closed. This is remarkable since a similar set for which the primal-dual Slater condition holds is always open. Received: April 2, 1998 / Accepted: January 16, 2001?Published online March 22, 2001     

Upper Semicontinuity of the Feasible Set Mapping for Linear Inequality Systems

In this paper we characterize the upper semicontinuity of the feasible set mapping at a consistent linear semi-infinite system (LSIS, in brief). In our context, no standard hypothesis is required in relation to the set indexing the constraints and, consequently, the functional dependence between the linear constraints and their associated indices has no special property. We consider, as parameter space, the set of all LSIS having the same index set, endowed with an extended metric to measure the size of the perturbations. We introduce the concept of reinforced system associated with our nominal system. Then, the upper semicontinuity property of the feasible set mapping at the nominal system is characterized looking at the feasible sets of both systems. The fact that this characterization depends only on the nominal system, not involving systems in a neighbourhood, is remarkable. We also provide a necessary and sufficient condition for the aimed property exclusively in terms of the coefficients of the system.     

Stability and augmented Lagrangian duality in nonconvex semi-infinite programming

In this paper the pseudo-Lipschitz property of the constraint set mapping and the Lipschitz property of the optimal value function of parametric nonconvex semi-infinite optimization problems are obtained under suitable conditions on the limiting subdifferential and the limiting normal cone. Then we derive sufficient conditions for the strong duality of nonconvex semi-infinite optimality problems and a criterion for exact penalty representations via an augmented Lagrangian approach. Examples are given to illustrate the obtained results.     

Stability analysis of stochastic programs with second order dominance constraints

In this paper we present a stability analysis of a stochastic optimization problem with stochastic second order dominance constraints. We consider a perturbation of the underlying probability measure in the space of regular measures equipped with pseudometric discrepancy distance (Römisch in Stochastic Programming. Elsevier, Amsterdam, pp 483–554, 2003). By exploiting a result on error bounds in semi-infinite programming due to Gugat (Math Program Ser B 88:255–275, 2000), we show under the Slater constraint qualification that the optimal value function is Lipschitz continuous and the optimal solution set mapping is upper semicontinuous with respect to the perturbation of the probability measure. In particular, we consider the case when the probability measure is approximated by an empirical probability measure and show an exponential rate of convergence of the sequence of optimal solutions obtained from solving the approximation problem. The analysis is extended to the stationary points.     

Quantitative stability of linear infinite inequality systems under block perturbations with applications to convex systems

The original motivation for this paper was to provide an efficient quantitative analysis of convex infinite (or semi-infinite) inequality systems whose decision variables run over general infinite-dimensional (resp. finite-dimensional) Banach spaces and that are indexed by an arbitrary fixed set J. Parameter perturbations on the right-hand side of the inequalities are required to be merely bounded, and thus the natural parameter space is l _??(J). Our basic strategy consists of linearizing the parameterized convex system via splitting convex inequalities into linear ones by using the Fenchel?CLegendre conjugate. This approach yields that arbitrary bounded right-hand side perturbations of the convex system turn on constant-by-blocks perturbations in the linearized system. Based on advanced variational analysis, we derive a precise formula for computing the exact Lipschitzian bound of the feasible solution map of block-perturbed linear systems, which involves only the system??s data, and then show that this exact bound agrees with the coderivative norm of the aforementioned mapping. In this way we extend to the convex setting the results of Cánovas et?al. (SIAM J. Optim. 20, 1504?C1526, 2009) developed for arbitrary perturbations with no block structure in the linear framework under the boundedness assumption on the system??s coefficients. The latter boundedness assumption is removed in this paper when the decision space is reflexive. The last section provides the aimed application to the convex case.     

Conditions for the uniqueness of the optimal solution in linear semi-infinite programming

In this paper, we establish different conditions for the uniqueness of the optimal solution of a semi-infinite programming problem. The approach here is based on the differentiability properties of the optimal value function and yields the corresponding extensions to the general linear semi-infinite case of many results provided by Mangasarian and others. In addition, detailed optimality conditions for the most general problem are supplied, and some features of the optimal set mapping are discussed. Finally, we obtain a dimensional characterization of the optimal set, provided that a usual closedness condition (Farkas-Minkowski condition) holds.     

Inscribed Balls and Their Centers

A ball of maximal radius inscribed in a convex closed bounded set with a nonempty interior is considered in the class of uniformly convex Banach spaces. It is shown that, under certain conditions, the centers of inscribed balls form a uniformly continuous (as a set function) set-valued mapping in the Hausdorff metric. In a finite-dimensional space of dimension n, the set of centers of balls inscribed in polyhedra with a fixed collection of normals satisfies the Lipschitz condition with respect to sets in the Hausdorff metric. A Lipschitz continuous single-valued selector of the set of centers of balls inscribed in such polyhedra can be found by solving n + 1 linear programming problems.     

On distributionally robust optimization problems with k-th order stochastic dominance constraints induced by full random quadratic recourse

In this paper, we consider the optimization problems with k-th order stochastic dominance constraint on the objective function of the two-stage stochastic programs with full random quadratic recourse. By establishing the Lipschitz continuity of the feasible set mapping under some pseudo-metric, we show the Lipschitz continuity of the optimal value function and the upper semicontinuity of the optimal solution mapping of the problem. Furthermore, by the Hölder continuity of parameterized ambiguity set under the pseudo-metric, we demonstrate the quantitative stability results of the feasible set mapping, the optimal value function and the optimal solution mapping of the corresponding distributionally robust problem.     

A generalized knapsack problem with variable coefficients

The ordinary knapsack problem is to find the optimal combination of items to be packed in a knapsack under a single constraint on the total allowable resources, where all coefficients in the objective function and in the constraint are constant.In this paper, a generalized knapsack problem with coefficients depending on variable parameters is proposed and discussed. Developing an effective branch and bound algorithm for this problem, the concept of relaxation and the efficiency function introduced here will play important roles. Furthermore, a relation between the algorithm and the dynamic programming approach is discussed, and subsequently it will be shown that the ordinary 0–1 knapsack problem, the linear programming knapsack problem and the single constrained linear programming problem with upper-bounded variables are special cases of the interested problem. Finally, practical applications of the problem and its computational experiences will be shown.     

Characterization of total ill-posedness in linear semi-infinite optimization

This paper deals with the stability of linear semi-infinite programming (LSIP, for short) problems. We characterize those LSIP problems from which we can obtain, under small perturbations in the data, different types of problems, namely, inconsistent, consistent unsolvable, and solvable problems. The problems of this class are highly unstable and, for this reason, we say that they are totally ill-posed. The characterization that we provide here is of geometrical nature, and it depends exclusively on the original data (i.e., on the coefficients of the nominal LSIP problem). Our results cover the case of linear programming problems, and they are mainly obtained via a new formula for the subdifferential mapping of the support function.