Lipschitz behavior of convex semi-infinite optimization problems: a variational approach

In this paper we make use of subdifferential calculus and other variational techniques, traced out from [Ioffe, A.D.: Metric regularity and subdifferential calculus. Uspekhi Mat. Nauk 55, 3(333), 103–162; Engligh translation Math. Surveys 55, 501–558 (2000); Ioffe, A.D.: On rubustness of the regularity property of maps. Control cybernet 32, 543–554 (2003)], to derive different expressions for the Lipschitz modulus of the optimal set mapping of canonically perturbed convex semi-infinite optimization problems. In order to apply this background for obtaining the modulus of metric regularity of the associated inverse multifunction, we have to analyze the stable behavior of this inverse mapping. In our semi-infinite framework this analysis entails some specific technical difficulties. We also provide a new expression of a global variational nature for the referred regularity modulus.      

Stability of Indices in the KKT Conditions and Metric Regularity in Convex Semi-Infinite Optimization

This paper deals with a parametric family of convex semi-infinite optimization problems for which linear perturbations of the objective function and continuous perturbations of the right-hand side of the constraint system are allowed. In this context, Cánovas et al. (SIAM J. Optim. 18:717–732, [2007]) introduced a sufficient condition (called ENC in the present paper) for the strong Lipschitz stability of the optimal set mapping. Now, we show that ENC also entails high stability for the minimal subsets of indices involved in the KKT conditions, yielding a nice behavior not only for the optimal set mapping, but also for its inverse. Roughly speaking, points near optimal solutions are optimal for proximal parameters. In particular, this fact leads us to a remarkable simplification of a certain expression for the (metric) regularity modulus given in Cánovas et al. (J. Glob. Optim. 41:1–13, [2008]) (and based on Ioffe (Usp. Mat. Nauk 55(3):103–162, [2000]; Control Cybern. 32:543–554, [2003])), which provides a key step in further research oriented to find more computable expressions of this regularity modulus. This research was partially supported by Grants MTM2005-08572-C03 (01-02) and MTM2006-27491-E (MEC, Spain, and FEDER, E.U.), ACOMP06/117-203 and ACOMP/2007/247-292 (Generalitat Valenciana, Spain), and CIO (UMH, Spain).     

Stability of Mann’s iterates under metric regularity

We consider a Mann-like iteration for solving the inclusion xT(x) where is a set-valued mapping, defined from a Banach space X into itself, which is metrically regular near a point in its graph. We study the behavior of the iterates generated by our method and prove that they inherit the regularity properties of the mapping T. First we consider the case when the mapping T is metrically regular, then the case when it is strongly metrically regular. Finally, we present an inexact version of our method and we study its convergence when the mapping T is strongly metrically subregular.     

Forest embeddings in regular graphs of large girth

This paper deals with the enumeration of distinct embeddings (both induced and partial) of arbitrary graphs in regular graphs of large girth. A simple explicit recurrence formula is presented for the number of embeddings of an arbitrary forest F in an arbitrary regular graph G of sufficiently large girth. This formula (and hence the number of embeddings) depends only on the order and degree of regularity of G, and the degree sequence and component structure (multiset of component orders) of F. A concept called c-subgraph regularity is introduced which generalizes the familiar notion of regularity in graphs. (Informally, a graph is c-subgraph regular if its vertices cannot be distinguished on the basis of embeddings of graphs of order less than or equal to c.) A central result of this paper is that if G is regular and has girth g, then G is (g ? 1)-subgraph regular.     

Distance to Ill-Posedness in Linear Optimization via the Fenchel-Legendre Conjugate

We consider the parameter space of all the linear inequality systems, in the n-dimensional Euclidean space and with a fixed index set, endowed with the topology of the uniform convergence of the coefficient vectors. A system is ill-posed with respect to the consistency when arbitrarily small perturbations yield both consistent and inconsistent systems. In this paper, we establish a formula for measuring the distance from the nominal system to the set of ill-posed systems. To this aim, we use the Fenchel-Legendre conjugation theory and prove a refinement of the formula in Ref. 1 for the distance from any point to the boundary of a convex set.This research has been partially supported by grants BFM2002–04114-C02 (01–02) from MEC (Spain) and FEDER (EU) and by grants GV04B-648 and GRUPOS04/79 from Generalitat Valenciana (Spain).     

Stability properties of the Tikhonov regularization for nonmonotone inclusions

We study the Tikhonov regularization for perturbed inclusions of the form T(x) ' y^*{T(x) \ni y^*} where T is a set-valued mapping defined on a Banach space that enjoys metric regularity properties and y* is an element near 0. We investigate the case when T is metrically regular and strongly regular and we show the existence of both a solution x* to the perturbed inclusion and a Tikhonov sequence which converges to x*. Finally, we show that the Tikhonov sequences associated to the perturbed problem inherit the regularity properties of the inverse of T.     

An inertial proximal scheme for nonmonotone mappings

We present an inertial proximal method for solving an inclusion involving a nonmonotone set-valued mapping enjoying some regularity properties. More precisely, we investigate the local convergence of an implicit scheme for solving inclusions of the type T(x)∋0 where T is a set-valued mapping acting from a Banach space into itself. We consider subsequently the case when T is strongly metrically subregular, metrically regular and strongly regular around a solution to the inclusion. Finally, we study the convergence of our algorithm under variational perturbations.     

Tikhonov regularization of metrically regular inclusions

We present a Tikhonov regularization method for inclusions of the form where T is a set-valued mapping defined on a Banach space that enjoys metric regularity properties. We investigate, subsequently, the case when the mapping T is metrically regular, strongly metrically regular, strongly subregular and Lipschitz continuous and show the strong convergence of the solutions of regularized problems to a solution to the original inclusion . We also prove that the method has finite termination under some special conditioning assumptions on T and we study its stability with respect to some variational perturbations. These authors are supported by Contract EA3591 (France).     

A Lyusternik–Graves theorem for the proximal point method

We consider a generalized version of the proximal point algorithm for solving the perturbed inclusion y∈T(x), where y is a perturbation element near 0 and T is a set-valued mapping acting from a Banach space X to a Banach space Y which is metrically regular around some point $({\bar{x}},0)$ in its graph. We study the behavior of the convergent iterates generated by the algorithm and we prove that they inherit the regularity properties of T, and vice versa. We analyze the cases when the mapping T is metrically regular and strongly regular.     

Regular F-Abundant Semigroups

ABSTRACT

The investigation of regular F-abundant semigroups is initiated. In fact, F-abundant semigroups are generalizations of regular cryptogroups in the class of abundant semigroups. After obtaining some properties of such semigroups, the construction theorem of the class of regular F-abundant semigroups is obtained. In addition, we also prove that a regular F-abundant semigroup is embeddable into a semidirect product of a regular band by a cancellative monoid. Our result is an analogue of that of Gomes and Gould on weakly ample semigroups, and also extends an earlier result of O'Carroll on F-inverse semigroups.     

Approximating Orders in Meet-Continuous Lattices and Regularity Axioms in Many Valued Topology

It is shown that in a meet-continuous lattice L endowed with a multiplicative auxiliary order ≺ the family of all members of L which satisfy the axiom of approximation, i.e. α = {β ∈ L : β ≺ α}, is closed under finite infs and arbitrary sups. This is a key ingredient of a meet-continuous lattice proof that both regularity and complete regularity of many valued topology have subbasic characterizations. As a consequence, the frame law can now be eliminated from some fundamental results on completely regular L-valued topological spaces (e.g., this is the case in regard to the Tychonoff embedding theorem). The grant MTM2006-14925-C02-02 from the Ministry of Education and Science of Spain and FEDER is gratefully acknowledged by the second named author.     

Perturbations and Metric Regularity

A point x is an approximate solution of a generalized equation b∈F(x) if the distance from the point b to the set F(x) is small. ‘Metric regularity’ of the set-valued mapping F means that, locally, a constant multiple of this distance bounds the distance from x to an exact solution. The smallest such constant is the ‘modulus of regularity’, and is a measure of the sensitivity or conditioning of the generalized equation. We survey recent approaches to a fundamental characterization of the modulus as the reciprocal of the distance from F to the nearest irregular mapping. We furthermore discuss the sensitivity of the regularity modulus itself, and prove a version of the fundamental characterization for mappings on Riemannian manifolds. Mathematics Subject Classifications 2000 Primary: 49J53; secondary: 90C31.     

On Some Properties of the Quaternionic Functional Calculus

In some recent works we have developed a new functional calculus for bounded and unbounded quaternionic operators acting on a quaternionic Banach space. That functional calculus is based on the theory of slice regular functions and on a Cauchy formula which holds for particular domains where the admissible functions have power series expansions. In this paper, we use a new version of the Cauchy formula with slice regular kernel to extend the validity of the quaternionic functional calculus to functions defined on more general domains. Moreover, we show some of the algebraic properties of the quaternionic functional calculus such as the S-spectral radius theorem and the S-spectral mapping theorem. Our functional calculus is also a natural tool to define the semigroup e ^tA when A is a linear quaternionic operator.      

On the Lipschitz Modulus of the Argmin Mapping in Linear Semi-Infinite Optimization

This paper is devoted to quantify the Lipschitzian behavior of the optimal solutions set in linear optimization under perturbations of the objective function and the right hand side of the constraints (inequalities). In our model, the set indexing the constraints is assumed to be a compact metric space and all coefficients depend continuously on the index. The paper provides a lower bound on the Lipschitz modulus of the optimal set mapping (also called argmin mapping), which, under our assumptions, is single-valued and Lipschitz continuous near the nominal parameter. This lower bound turns out to be the exact modulus in ordinary linear programming, as well as in the semi-infinite case under some additional hypothesis which always holds for dimensions n ? 3. The expression for the lower bound (or exact modulus) only depends on the nominal problem’s coefficients, providing an operative formula from the practical side, specially in the particular framework of ordinary linear programming, where it constitutes the sharp Lipschitz constant. In the semi-infinite case, the problem of whether or not the lower bound equals the exact modulus for n > 3 under weaker hypotheses (or none) remains as an open problem.     

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.     

F-Polynomials in Quantum Cluster Algebras

F-polynomials and g-vectors were defined by Fomin and Zelevinsky to give a formula which expresses cluster variables in a cluster algebra in terms of the initial cluster data. A quantum cluster algebra is a certain noncommutative deformation of a cluster algebra. In this paper, we define and prove the existence of analogous quantum F-polynomials for quantum cluster algebras. We prove some properties of quantum F-polynomials. In particular, we give a recurrence relation which can be used to compute them. Finally, we compute quantum F-polynomials and g-vectors for a certain class of cluster variables, which includes all cluster variables in type A_n\mbox{A}_{n} quantum cluster algebras.     

On Metric Pseudo-(sub)Regularity of Multifunctions and Optimality Conditions for Degenerated Mathematical Programs

This paper is devoted to the analysis of a special kind of regularity of a multifunction which we call metric pseudo-(sub)regularity, when the multifunction is not metrically (sub)regular at a given point but is metrically (sub)regular at certain points in a neighborhood with moduli possibly tending to infinity with a certain order. By using advanced techniques of generalized differentiation we derive conditions both necessary and sufficient for this property. As a byproduct we obtain a new sufficient condition for metric subregularity. Then we apply these results to multifunctions composed by a smooth mapping and a generalized polyhedral multifunction and obtain explicit formulas for this case. Finally we show how the theory can be used to obtain necessary optimality conditions when the constraint qualification condition of metric (sub)regularity is violated.     

Second-Order Epi-Derivatives of Composite Functionals

We compute two-sided second-order epi-derivatives for certain composite functionals f=gF where F is a C ¹ mapping between two Banach spaces X and Y, and g is a convex extended real-valued function on Y. These functionals include most essential objectives associated with smooth constrained minimization problems on Banach spaces. Our proof relies on our development of a formula for the second-order upper epi-derivative that mirrors a formula for a second-order lower epi-derivative from [7], and the two-sided results we obtain promise to support a more precise sensitivity analysis of parameterized optimization problems than has been previously possible.     

On the Grigorchuk–Kurchanov conjecture

 Let denote the free group of rank 2g. An automorphism φ? Aut(F _{2 g} ) is generating if N _a φ (N _b ) = F _{2 g} , where N _a is the normal closure of and N _b is defined analogously. We present a characterization of generating automorphisms in Aut(F ₂) and observe that there exists a unique (up to equivalence) epimorphism F ₂→Z×Z: this is a particular case of the Grigorchuk–Kurchanov conjecture. This leads to further investigations for splitting homomorphisms for the pairs (F _{2 g} , F _g) and (G _g, F _g) where G _g denotes the fundamental group of a closed orientable surface of genus g and a reformulation of the Poincaré and Grigorchuk–Kurchanov conjectures is derived. Received: 1 October 2001     

The Hahn-Banach Property and the Axiom of Choice

We work in set theory ZF without axiom of choice. Though the Hahn-Banach theorem cannot be proved in ZF, we prove that every Gateaux-differentiable uniformly convex Banach space E satisfies the following continuous Hahn-Banach property: if p is a continuous sublinear functional on E, if F is a subspace of E, and if f: F → ? is a linear functional such that f ≤ p|F then there exists a linear functional g : E → ? such that g extends f and g ≤ p. We also prove that the continuous Hahn-Banach property on a topological vector space E is equivalent to the classical geometrical forms of the Hahn-Banach theorem on E. We then prove that the axiom of Dependent choices DC is equivalent to Ekeland's variational principle, and that it implies the continuous Hahn-Banach property on Gateaux-differentiable Banach spaces. Finally, we prove that, though separable normed spaces satisfy the continuous Hahn-Banach property, they do not satisfy the whole Hahn-Banach property in ZF+DC.