|
Article Excerpt
We consider the parametric space of all the linear semi-infinite programming problems with constraint systems having the same index set. Under a certain regularity condition, the so-called well- posedness with respect to the solvability, it is known from Canovas et al. [2] that the optimal value function is Lipschitz continuous around the nominal problem [pi]. In this paper we obtain an explicit Lipschitz constant for such a function in a certain neighborhood of [pi]. We emphasize the fact that both the constant and the size of the neighborhood are exclusively expressed in terms of the nominal problem data, and that they involve the distances to primal and to dual inconsistency. Moreover, a uniform bound for the optimal set is provided. This bound constitutes a key ingredient to derive the Lipschitz constant for the optimal value function.
Key words: Lipschitz continuity of the optimal value; boundedness of the optimal set; distance to ill-posedness; linear semi-infinite programming
MSC2000 subject classification: Primary: 90C31, 90C34; secondary: 65F22, 90C05, 49J53
OR/MS subject classification: Programming/linear
History: Received May 5, 2005; revised November 29, 2005, and January 17, 2006.
1. Introduction. This paper deals with the stability and sensitivity of linear optimization problems, in [R.sup.n], in the form
(1) [pi]: Inf c'x s.t. [a.sub.t]'x [greater than or equal to] [b.sub.t], t [member of] T,
with coefficients c, [a.sub.t] [member of] [R.sup.n] (regarded as column- vectors), [b.sub.t] [member of] R, decision variables vector x [member of] [R.sup.n], and where y' denotes the transpose of y [member of] [R.sup.n]. Specifically, our focus is on the question of whether the change of the optimal value of problems around (1) can be bounded by a constant multiple of the magnitude of the data perturbations. In our stability study we follow the classical approach of Robinson, in which arbitrary perturbations of all the coefficients are allowed. Early papers of this author (Robinson [15, 16]) tackle the same question when concerned with the feasible set (see also Robinson [17] for an extension to differentiable nonlinear systems).
The nonempty index set, T, is arbitrary, and so no topological structure is assumed for it. When T is finite, (1) is nothing else but an ordinary linear programming--LP, for short--problem (in primal format). If T is infinite, (1) becomes a linear semi-infinite programming problem. If
(2) [sigma]:= {[a.sub.t]'x [greater than or equal to] [b.sub.t], t [member of] T]
denotes the constraint system of (1), then the problem [pi] can be identified with the pair (c, [sigma]). Associated with [pi] = (c, [sigma]), we consider the following elements:
F := {x [member of] [R.sup.n]: [a.sub.t]'x [greater than or equal to] [b.sub.t] for all t [member of] T], the feasible set of [pi] (or [sigma]);
v := inf{c'x: x [member of] F] [member of] [-[infinity], +[infinity]], the optimal value of [pi] (v = +[infinity] when F = [empty set]);
[F.sup.op] := {x [member of] F: c'x = v}, the optimal set of [pi].
The parameter space of all the linear optimization problems [pi] = (c, [sigma]) in the form (1) will be denoted by [PI] = [R.sup.n] x [THETA], while [THETA] = [([R.sup.n] x R).sup.T] will represent the parameter space of all the linear inequality systems [sigma] in the form (2). Note that, in such a way, we are identifying or with the parameter vector [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. When different problems are considered in [PI] or [THETA], they and their associated elements are distinguished by means of sub(super)scripts. For instance, if [[pi].sub.1] [member of] [PI], then [[pi].sub.1] = ([c.sup.1], [[sigma].sub.1]) where [[sigma].sub.1] := {([a.sup.1.sub.t])'x [greater than or equal to] [b.sup.1.sub.t]), t [member of] T], and the feasible set, the optimal value, and the optimal set of [[pi].sub.1] are, respectively, represented by [F.sub.1], [v.sub.1], and [F.sup.op.sub.1].
We consider the following relevant subsets of [PI] and [THETA]:
[[PI].sub.c] := {[pi] = (c, [sigma]) [member of] [PI]: [sigma] [member of] [[THETA].sub.c]], where [[THETA].sub.c] := {[sigma] [member of] [THETA]: F [not equal to] [empty set]];
[[PI].sub.s] := {[pi] = (c, [sigma]) [member of] [PI]: [F.sup.op] [not equal to] [empty set]].
Here the subscripts c and s mean consistent and solvable, respectively.
Given two arbitrary norms in [R.sup.n] and [R.sup.n+1], both denoted by [parallel]*[parallel], we consider the extended distances d: [THETA] x [THETA] [right arrow] [0, +[infinity]], given by
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.],
and [delta]: [PI] x [PI] [right arrow] [0, +[infinity]], defined by
[delta]([[pi].sub.1], [pi]) := max{[parallel][c.sup.1] - c[parallel], d([[sigma].sub.1], [sigma])].
They endow [THETA] and [PI], respectively, with the topology of the uniform convergence of the coefficient vectors (see Goberna and Lopez [10, Chapters 6 and 10]).
If X is a subset of any topological space, int(X), cl(X), and bd(X) denote the interior set, the closure, and the boundary of X, respectively.
The aim of this paper may be placed in the intersection of the stability and sensitivity analysis in the context of linear (semi-infinite) optimization. It tackles the stability of the problem [pi] from a quantitative point of view. Under the stability assumption [pi] [member of] int([[PI].sub.s]), a bound on the rate of variation of the optimal value with respect to the parameters (a Lipschitz constant), in a neighborhood of [pi], is provided here via a uniform bound on the optimal set. An explicit formula for such a uniform bound is also given in the paper. We underline that both the Lipschitz constant and the neighborhood, as well as the referred bound, are given exclusively in terms of the nominal problem data, and that to the authors' knowledge, the main results of the paper provide new information on this subject even in the setting of ordinary linear programming.
A Lipschitz condition for the optimal value in the general context (1) was already established in Canovas et al. [2, Theorem 4.2], but no computing process for the associated constant was described (only its existence, through the existence of a Slater point, among other elements, was established there). In the particular case of LP problems, we find that, under certain assumptions, Corollary 3.1 and Theorem 4.3 provide refinements of the corresponding results traced out from Renegar [13]. Actually, the paper (Renegar [13]) constitutes a background on this perturbation theory in the context of conic linear systems (see [section]3), where the parameter space is a normed space. Early antecedents on this perturbation framework may be found in Robinson [15, 16]. However, the results given there do not apply to our context of problems (1) when T is infinite (in which case [PI] and [THETA] are not normed spaces). Nevertheless, the ordinary LP setting (with T finite) constitutes a common framework for Renegar's work [13] and the present paper, and this relationship is explored at the end of [subsection]3 and 4.
In relation to sensitivity analysis, the Lipschitz property of the optimal value function constitutes a starting point. In the LP context, De Wolf [6] provides an expression of the generalized derivative of the optimal value function depending on the coefficients of the constraints (keeping fixed the objective function and the right-hand-side coefficients in the constraints). In our notation, De Wolf [6, Theorem 1] requires [pi] [member of] int([[PI].sub.c]) and certain Lipschitz property of...
|
