On the stable containment of two sets

This paper studies the stability of the set containment problem. Given two non-empty sets in the Euclidean space which are the solution sets of two systems of (possibly infinite) inequalities, the Farkas type results allow to decide whether one of the two sets is contained or not in the other one (which constitutes the so-called containment problem). In those situations where the data (i.e., the constraints) can be affected by some kind of perturbations, the problem consists of determining whether the relative position of the two sets is preserved by sufficiently small perturbations or not. This paper deals with this stability problem as a particular case of the maintaining of the relative position of the images of two set-valued mappings; first for general set-valued mappings and second for solution sets mappings of convex and linear systems. Thus the results in this paper could be useful in the postoptimal analysis of optimization problems with inclusion constraints.      

Traveling salesman games

In this paper we discuss the problem of how to divide the total cost of a round trip along several institutes among the institutes visited. We introduce two types of cooperative games—fixed-route traveling salesman games and traveling salesman games—as a tool to attack this problem. Under very mild conditions we prove that fixed-route traveling salesman games have non-empty cores if the fixed route is a solution of the classical traveling salesman problem. Core elements provide us with fair cost allocations. A traveling salesman game may have an empty core, even if the cost matrix satisfies the triangle inequality. In this paper we introduce a class of matrices defining TS-games with non-empty cores.     

The largest Erdős-Ko-Rado sets of planes in finite projective and finite classical polar spaces

Erd?s-Ko-Rado sets of planes in a projective or polar space are non-extendable sets of planes such that every two have a non-empty intersection. In this article we classify all Erd?s-Ko-Rado sets of planes that generate at least a 6-dimensional space. For general dimension (projective space) or rank (polar space) we give a classification of the ten largest types of Erd?s-Ko-Rado sets of planes. For some small cases we find a better, sometimes complete, classification.     

A simple characterization of solution sets of convex programs

By means of elementary arguments we first show that the gradient of the objective function of a convex program is constant on the solution set of the problem. Furthermore the solution set lies in an affine subspace orthogonal to this constant gradient, and is in fact in the intersection of this affine subspace with the feasible region. As a consequence we give a simple polyhedral characterization of the solution set of a convex quadratic program and that of a monotone linear complementarity problem. For these two problems we can also characterize a priori the boundedness of their solution sets without knowing any solution point. Finally we give an extension to non-smooth convex optimization by showing that the intersection of the subdifferentials of the objective function on the solution set is non-empty and equals the constant subdifferential of the objective function on the relative interior of the optimal solution set. In addition, the solution set lies in the intersection with the feasible region of an affine subspace orthogonal to some subgradient of the objective function at a relative interior point of the optimal solution set.     

Bounded linear regularity of convex sets in Banach spaces and its applications

This paper deals with bounded linear regularity, linear regularity and the strong conical hull intersection property (CHIP) of a collection of finitely many closed convex intersecting sets in Banach spaces. It is shown that, as in finite dimensional space setting (see [6]), the standard constraint qualification implies bounded linear regularity, which in turn yields the strong conical hull intersection property, and that the collection of closed convex sets {C ₁, . . . ,C _n } is bounded linearly regular if and only if the tangent cones of {C ₁, . . . ,C _n } has the CHIP and the normal cones of {C ₁, . . . ,C _n } has the property (G)(uniformly on a neighborhood in the intersection C). As applications, we study the global error bounds for systems of linear and convex inequalities. The work of this author was partially supported by the National Natural Sciences Grant (No. 10471032) and the Excellent Young Teachers Program of MOE, P.R.C The authors thank professor K.F.Ng for his helpful discussion and the referee for their helpful suggestions on improving the first version of this paper     

A projection-type method for variational inequalities on Hadamard manifolds and verification of solution existence

In this paper, we extend a projection-type method for variational inequalities from Euclidean spaces to Hadamard manifolds. The proposed method has the following nice features: (i) the algorithm is well defined whether the solution set of the problem is non-empty or not, under weak assumptions; (ii) if the solution set is non-empty, then the sequence generated by the method is convergent to the solution, which is closest to the initial point; and (iii) the existence of the solutions to variational inequalities can be verified through the behaviour of the generated sequence. The results presented in this paper generalize and improve some known results given in literatures.     

Stability of semi-infinite vector optimization problems without compact constraints

This paper is devoted to the continuity of solution maps for perturbation semi-infinite vector optimization problems without compact constraint sets. The sufficient conditions for lower semicontinuity and upper semicontinuity of solution maps under functional perturbations of both objective functions and constraint sets are established. Some examples are given to analyze the assumptions in the main result.     

Local linear convergence of approximate projections onto regularized sets

The numerical properties of algorithms for finding the intersection of sets depend to some extent on the regularity of the sets, but even more importantly on the regularity of the intersection. The alternating projection algorithm of von Neumann has been shown to converge locally at a linear rate dependent on the regularity modulus of the intersection. In many applications, however, the sets in question come from inexact measurements that are matched to idealized models. It is unlikely that any such problems in applications will enjoy metrically regular intersection, let alone set intersection. We explore a regularization strategy that generates an intersection with the desired regularity properties. The regularization, however, can lead to a significant increase in computational complexity. In a further refinement, we investigate and prove linear convergence of an approximate alternating projection algorithm. The analysis provides a regularization strategy that fits naturally with many ill-posed inverse problems, and a mathematically sound stopping criterion for extrapolated, approximate algorithms. The theory is demonstrated on the phase retrieval problem with experimental data. The conventional early termination applied in practice to unregularized, consistent problems in diffraction imaging can be justified fully in the framework of this analysis providing, for the first time, proof of convergence of alternating approximate projections for finite dimensional, consistent phase retrieval problems.     

On the equivalence of parametric contexts for linear inequality systems

In this paper we analyze the connections among different parametric settings in which the stability theory for linear inequality systems may be developed. Our discussion is focussed on the existence, or not, of an index set (possibly infinite). For some stability approaches it is not convenient to have a fixed set indexing the constraints. This is the case, for example, of discretization techniques viewed as approximation strategies (i.e., discretization regarded as data perturbation). The absence of a fixed index set is also a key point in the stability analysis of parametrized convex systems via standard linearization. In other frameworks the index set is very useful, for example if the constraints are perturbed one by one, even to measure the global perturbation size. This paper shows to what extent an index set may be introduced or removed in relation to stability.     

Stability radius of linear parameter-varying systems and applications

In this paper, we present a unifying approach to the problems of computing of stability radii of positive linear systems. First, we study stability radii of linear time-invariant parameter-varying differential systems. A formula for the complex stability radius under multi perturbations is given. Then, under hypotheses of positivity of the system matrices, we prove that the complex, real and positive stability radii of the system under multi perturbations (or affine perturbations) coincide and they are computed via simple formulae. As applications, we consider problems of computing of (strong) stability radii of linear time-invariant time-delay differential systems and computing of stability radii of positive linear functional differential equations under multi perturbations and affine perturbations. We show that for a class of positive linear time-delay differential systems, the stability radii of the system under multi perturbations (or affine perturbations) are equal to the strong stability radii. Next, we prove that the stability radii of a positive linear functional differential equation under multi perturbations (or affine perturbations) are equal to those of the associated linear time-invariant parameter-varying differential system. In particular, we get back some explicit formulas for these stability radii which are given recently in [P.H.A. Ngoc, Strong stability radii of positive linear time-delay systems, Internat. J. Robust Nonlinear Control 15 (2005) 459-472; P.H.A. Ngoc, N.K. Son, Stability radii of positive linear functional differential equations under multi perturbations, SIAM J. Control Optim. 43 (2005) 2278-2295]. Finally, we give two examples to illustrate the obtained results.     

On regularity and stability in semi-infinite optimization

For stationary solutions and Langrange multipliers of a semi-infinite program withC ¹ data, we study some stability behaviour which is closely related to (metric) regularity of the constraint system. The multiplier set mapping considered here has its images in a finite-dimensional space. In this framework, regularity is a necessary and sufficient condition to have bounded sets of multipliers.     

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.     

A weaker regularity condition for subdifferential calculus and Fenchel duality in infinite dimensional spaces

In this paper we present a new regularity condition for the subdifferential sum formula of a convex function with the precomposition of another convex function with a continuous linear mapping. This condition is formulated by using the epigraphs of the conjugates of the functions involved and turns out to be weaker than the generalized interior-point regularity conditions given so far in the literature. Moreover, it provides a weak sufficient condition for Fenchel duality regarding convex optimization problems in infinite dimensional spaces. As an application, we discuss the strong conical hull intersection property (CHIP) for a finite family of closed convex sets.     

Addition and multiplication of sets

Ordinal addition and multiplication can be extended in a natural way to all sets. I survey the structure of the sets under these operations. In particular, the natural partial ordering associated with addition of sets is shown to be a tree. This allows us to prove that any set has a unique representation as a sum of additively irreducible sets, and that the non-empty elements of any model of set theory can be partitioned into infinitely many submodels, each isomorphic to the original model. Also any model of set theory has an isomorphic extension in which the empty set of the original model is non-empty. Among other results, the relations between the arithmetical operations and the transitive closure and the adductive hierarchy are elucidated. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Generalization of Primal—Dual Interior-Point Methods to Convex Optimization Problems in Conic Form

We generalize primal—dual interior-point methods for linear programming (LP) problems to the convex optimization problems in conic form. Previously, the most comprehensive theory of symmetric primal—dual interior-point algorithms was given by Nesterov and Todd for feasible regions expressed as the intersection of a symmetric cone with an affine subspace. In our setting, we allow an arbitrary convex cone in place of the symmetric cone. Even though some of the impressive properties attained by Nesterov—Todd algorithms are impossible in this general setting of convex optimization problems, we show that essentially all primal—dual interior-point algorithms for LP can be extended easily to the general setting. We provide three frameworks for primal—dual algorithms, each framework corresponding to a different level of sophistication in the algorithms. As the level of sophistication increases, we demand better formulations of the feasible solution sets. Our algorithms, in return, attain provably better theoretical properties. We also make a very strong connection to quasi-Newton methods by expressing the square of the symmetric primal—dual linear transformation (the so-called scaling) as a quasi-Newton update in the case of the least sophisticated framework. August 25, 1999. Final version received: March 7, 2001.     

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.     

Convex Sets in the Plane with Three of Every Four Meeting

Dedicated to the memory of Paul Erdős Suppose we have a finite collection of closed convex sets in the plane, (which without loss of generality we can take to be polygons). Suppose further that among any four of them, some three have non-empty intersection. We show that 13 points are sufficient to meet every one of the convex sets. Received October 27, 1999/Revised April 11, 2000 RID="*" ID="*" Supported by grant OTKA-T-029074. RID="†" ID="†" Supported by NSF grant DMS-99-70071, OTKA-T-020914 and OTKA-F-22234.     

A Helly-Type Theorem for Semi-monotone Sets and Monotone Maps

We consider sets and maps defined over an o-minimal structure over the reals, such as real semi-algebraic or globally subanalytic sets. A monotone map is a multi-dimensional generalization of a usual univariate monotone continuous function on an open interval, while the closure of the graph of a monotone map is a generalization of a compact convex set. In a particular case of an identically constant function, such a graph is called a semi-monotone set. Graphs of monotone maps are, generally, non-convex, and their intersections, unlike intersections of convex sets, can be topologically complicated. In particular, such an intersection is not necessarily the graph of a monotone map. Nevertheless, we prove a Helly-type theorem, which says that for a finite family of subsets of $\mathbb{R }^n$ , if all intersections of subfamilies, with cardinalities at most $n+1$ , are non-empty and graphs of monotone maps, then the intersection of the whole family is non-empty and the graph of a monotone map.     

A recognition algorithm for the intersection graphs of directed paths in directed trees

Consider a finite family of non-empty sets. The intersection graph of this family is obtained by representing each set by a vertex, two vertices being connected by an edge if and only if the corresponding sets intersect. The intersection graph of a family of directed paths in a directed tree is called a directed path graph. In this paper we present an efficient algorithm which constructs to a given graph a representation by a family of directed paths on a directed tree, if one exists. Also, we prove that a graph is a proper directed path graph if and only if it is a directed path graph.     

On minimal exposed faces

In this paper we consider the problem of the non-empty intersection of exposed faces in a Banach space. We find a sufficient condition to assure that the non-empty intersection of exposed faces is an exposed face. This condition involves the concept of inner point. Finally, we also prove that every minimal face of the unit ball must be an extreme point and show that this is not the case at all for minimal exposed faces since we prove that every Banach space with dimension greater than or equal to 2 can be equivalently renormed to have a non-singleton, minimal exposed face.