Search

International audience; We construct an example of a smooth convex function on the plane with a strict minimum at zero, which is real analytic except at zero, for which Thom's gradient conjecture fails both at zero and infinity. More precisely, the gradient orbits of the function spiral around zero and at infinity. Besides, the function satisfies the Lojasiewicz gradient inequality at zero.

Rademacher theorem asserts that Lipschitz continuous functions between Euclidean spaces are differentiable almost everywhere. In this work we extend this result to set-valued maps using an adequate notion of set-valued differentiability relating to convex processes. Our approach uses Rademacher theorem but also recovers it as a special case.

In [9], the celebrated K{\L}-inequality has been extended from definable functions $f:\mathbb{R}^{n}\rightarrow\mathbb{R} $ to definable multivalued maps $S:\mathbb{R}\rightrightarrows\mathbb{R}^{n}$, by establishing that the co-derivative mapping $D^{\ast}S$ admits a desingularization around every critical value. As was the case in the gradient dynamics, this desingularization yields a uniform control of the lengths of all bounded orbits of the corresponding sweeping process $-\dot{\gamma}(t)\in N_{S(t)}(\gamma(t))$. In this paper, working outside the framework of o-minimal geometry, we characterize the existence of a desingularization for the coderivative in terms of the behaviour of the sweeping process orbits and the integrability of the talweg function. These results are close in spirit with the ones in [3], where characterizations for the desingularization of the (sub)gradient of functions had been obtained., Comment: 21 pages

Vegeu el resum a l'inici del document del fitxer adjunt

We show that in a metric space, any continuous function with compact sublevel sets and finite metric slope is uniquely determined by the slope and its critical values.

Continuity of set-valued maps is hereby revisited: after recalling some basic concepts of variational analysis and a short description of the State-of-the-Art, we obtain as by-product two Sard type results concerning local minima of scalar and vector valued functions. Our main result though, is inscribed in the framework of tame geometry, stating that a closed-valued semialgebraic set-valued map is almost everywhere continuous (in both topological and measure-theoretic sense). The result -depending on stratification techniques- holds true in a more general setting of o-minimal (or tame) set-valued maps. Some applications are briefly discussed at the end.

We introduce the notion of trace convexity for functions and respectively, for subsets of a compact topological space. This notion generalizes both classical convexity of vector spaces, as well as Choquet convexity for compact metric spaces. We provide new notions of trace-convexification for sets and functions as well as a general version of Krein-Milman theorem. We show that the class of upper semicontinuous convex-trace functions attaining their maximum at exactly one Choquet-boundary point is residual and we obtain several enhanced versions of the maximum principle which generalize both the classical Bauer's theorem as well as its abstract version in the Choquet theory. We illustrate our notions and results with concrete examples of three different types.

In this work we show that various algorithms, ubiquitous in convex optimization (e.g. proximal-gradient, alternating projections and averaged projections) generate self-contracted sequences $\{x_{k}\}_{k\in\mathbb{N}}$. As a consequence, a novel universal bound for the \emph{length} ($\sum_{k\ge 0}\Vert x_{k+1}-x_k\Vert$) can be deduced. In addition, this bound is independent of both the concrete data of the problem (sets, functions) as well as the stepsize involved, and only depends on the dimension of the space.

The ordinary differential equation $\dot{x}(t)=f(x(t)), \; t \geq 0 $, for $f$ measurable, is not sufficiently regular to guarantee existence of solutions. To remedy this we may relax the problem by replacing the function $f$ with its Filippov regularization $F_{f}$ and consider the differential inclusion $\dot{x}(t)\in F_{f}(x(t))$ which always has a solution. It is interesting to know, inversely, when a set-valued map $\Phi$ can be obtained as the Filippov regularization of a (single-valued, measurable) function. In this work we give a full characterization of such set-valued maps, hereby called Filippov representable. This characterization also yields an elegant description of those maps that are Clarke subdifferentials of a Lipschitz function.

The convex cone $SC_{\mathrm{SLip}}^1(\mathcal{X})$ of real-valued smooth semi-Lipschitz functions on a Finsler manifold $\mathcal{X}$ is an order-algebraic structure that captures both the differentiable and the quasi-metric feature of $\mathcal{X}$. In this work we show that the subset of smooth semi-Lipschitz functions of constant strictly less than $1$, denoted $SC_{1^{-}}^1(\mathcal{X})$, can be used to classify Finsler manifolds and to characterize almost isometries between them, in the lines of the classical Banach-Stone and Mykers-Nakai theorems., Comment: 17 pages

Convergence of projection-based methods for nonconvex set feasibility problems has been established for sets with ever weaker regularity assumptions. What has not kept pace with these developments is analogous results for convergence of optimization problems with correspondingly weak assumptions on the value functions. Indeed, one of the earliest classes of nonconvex sets for which convergence results were obtainable, the class of so-called super-regular sets introduced by Lewis, Luke and Malick (2009), has no functional counterpart. In this work, we amend this gap in the theory by establishing the equivalence between a property slightly stronger than super-regularity, which we call Clarke super-regularity, and subsmootheness of sets as introduced by Aussel, Daniilidis and Thibault (2004). The bridge to functions shows that approximately convex functions studied by Ngai, Luc and Th\'era (2000) are those which have Clarke super-regular epigraphs. Further classes of regularity of functions based on the corresponding regularity of their epigraph are also discussed., Comment: 15 pages, 2 figures

International audience; We give a simple alternative proof for the $C^{1,1}$--convex extension problem which has been introduced and studied by D. Azagra and C. Mudarra [2]. As an application, we obtain an easy constructive proof for the Glaeser-Whitney problem of $C^{1,1}$ extensions on a Hilbert space. In both cases we provide explicit formulae for the extensions. For the Gleaser-Whitney problem the obtained extension is almost minimal, that is, minimal up to a factor $\frac{1+\sqrt{3}}{2}$ in the sense of Le Gruyer [15].

International audience; In this work we are interested in the Demyanov-Ryabova conjecture for a finite family of polytopes. The conjecture asserts that after a finite number of iterations (successive dualizations), either a 1-cycle or a 2-cycle eventually comes up. In this work we establish a strong version of this conjecture under the assumption that the initial family contains "enough minimal polytopes" whose extreme points are "well placed".

FONDECYT FONDECYT

We disclose an interesting connection between the gradient flow of a $\mathcal{C}^2$-smooth function $\psi$ and evanescent orbits of the second order gradient system defined by the square-norm of $\nabla\psi$, under adequate convexity assumption. As a consequence, we obtain the following surprising result for two $\mathcal{C}^2$, convex and bounded from below functions $\psi_1$, $\psi_2$: if $||\nabla\psi_1||=||\nabla\psi_2||$, then $\psi_1=\psi_2 + k$, for some $k\in \mathbb{R}$.

We consider random perturbations of a given domain. The characteristic amplitude of these perturbations is assumed to be small. We are interested in quantities of interest which depend on the random domain through a boundary value problem. We derive asymptotic expansions of the first moments of the distribution of this output function. A simple and efficient method is proposed to compute the coefficients of these expansions provided that the random perturbation admits a low- rank spectral representation. By numerical experiments, we compare our expansions with Monte-Carlo simulations. Mathematics Subject Classification. 60G35, 65N75, 65N99.

In this work we prove that every locally symmetric smooth submanifold gives rise to a naturally defined smooth submanifold of the space of symmetric matrices, called spectral manifold, consisting of all matrices whose ordered vector of eigenvalues belongs to the locally symmetric manifold. We also present an explicit formula for the dimension of the spectral manifold in terms of the dimension and the intrinsic properties of the locally symmetric manifold.

In this work we prove that every locally symmetric smooth submanifold gives rise to a naturally defined smooth submanifold of the space of symmetric matrices, called spectral manifold, consisting of all matrices whose ordered vector of eigenvalues belongs to the locally symmetric manifold. We also present an explicit formula for the dimension of the spectral manifold in terms of the dimension and the intrinsic properties of the locally symmetric manifold.

We consider linear optimization over a nonempty convex semi-algebraic feasible region F. Semidefinite programming is an example. If F is compact, then for almost every linear objective there is a unique optimal solution, lying on a unique \active" manifold, around which F is \partly smooth", and the second-order sufficient conditions hold. Perturbing the objective results in smooth variation of the optimal solution. The active manifold consists, locally, of these perturbed optimal solutions; it is independent of the representation of F, and is eventually identified by a variety of iterative algorithms such as proximal and projected gradient schemes. These results extend to unbounded sets F.

We consider linear optimization over a nonempty convex semi-algebraic feasible region F. Semidefinite programming is an example. If F is compact, then for almost every linear objective there is a unique optimal solution, lying on a unique \active" manifold, around which F is \partly smooth", and the second-order sufficient conditions hold. Perturbing the objective results in smooth variation of the optimal solution. The active manifold consists, locally, of these perturbed optimal solutions; it is independent of the representation of F, and is eventually identified by a variety of iterative algorithms such as proximal and projected gradient schemes. These results extend to unbounded sets F.

Continuity of set-valued maps is hereby revisited: after recalling some basic concepts of variational analysis and a short description of the State-of-the-Art, we obtain as by-product two Sard type results concerning local minima of scalar and vector valued functions. Our main result though, is inscribed in the framework of tame geometry, stating that a closed-valued semialgebraic set-valued map is almost everywhere continuous (in both topological and measure-theoretic sense). The result, depending on stratification techniques, holds true in a more general setting of o-minimal (or tame) set-valued maps. Some applications are briefly discussed at the end., 21 pages, 2 figures

Continuity of set-valued maps is hereby revisited: after recalling some basic concepts of variational analysis and a short description of the State-of-the-Art, we obtain as by-product two Sard type results concerning local minima of scalar and vector valued functions. Our main result though, is inscribed in the framework of tame geometry, stating that a closed-valued semialgebraic set-valued map is almost everywhere continuous (in both topological and measure-theoretic sense). The result –depending on stratification techniques– holds true in a more general setting of o-minimal (or tame) set-valued maps. Some applications are briefly discussed at the end.

The classical Lojasiewicz inequality and its extensions for partial differential equation problems (Simon) and to o-minimal structures (Kurdyka) have a considerable impact on the analysis of gradient-like methods and related problems: minimization methods, complexity theory, asymptotic analysis of dissipative partial differential equations, tame geometry. This paper provides alternative characterizations of this type of inequalities for nonsmooth lower semicontinuous functions defined on a metric or a real Hilbert space. In a metric context, we show that a generalized form of the Lojasiewicz inequality (hereby called the Kurdyka- Lojasiewicz inequality) relates to metric regularity and to the Lipschitz continuity of the sublevel mapping, yielding applications to discrete methods (strong convergence of the proximal algorithm). In a Hilbert setting we further establish that asymptotic properties of the semiflow generated by -∂f are strongly linked to this inequality. This is done by introducing the notion of a piecewise subgradient curve: such curves have uniformly bounded lengths if and only if the Kurdyka- Lojasiewicz inequality is satisfied. Further characterizations in terms of talweg lines -a concept linked to the location of the less steepest points at the level sets of f- and integrability conditions are given. In the convex case these results are significantly reinforced, allowing in particular to establish the asymptotic equivalence of discrete gradient methods and continuous gradient curves. On the other hand, a counterexample of a convex C2 function in R2 is constructed to illustrate the fact that, contrary to our intuition, and unless a specific growth condition is satisfied, convex functions may fail to fulfill the Kurdyka- Lojasiewicz inequality.

"Vegeu el resum a l'inici del document del fitxer adjunt".

"Vegeu el resum a l'inici del document del fitxer adjunt."

Vegeu el resum a l'inici del document del fitxer adjunt

We prove that any subanalytic locally Lipschitz function has the Sard property. Such functions are typically nonsmooth and their lack of regularity necessitates the choice of some generalized notion of gradient and of critical point. In our framework these notions are defined in terms of the Clarke and of the convex-stable subdifferentials. The main result of this note asserts that for any subanalytic locally Lipschitz function the set of its Clarke critical values is locally finite. The proof relies on Pawlucki's extension of the Puiseuxlemma. In the last section we give an example of a continuous subanalytic function which is not constant on a segment of "broadly critical" points, that is, points for which we can find arbitrarily short convex combinations of gradients at nearby points.

An updated version of this paper has appeared in Systems & Control Letters, 55, (2006), pp 45-51, DOI 10.1016/j.sysconle.2005.04.015; In this note we prove the equivalence, under appropriate conditions, between several dynamical formalisms: projected dynamical systems, two types of unilateral differential inclusions, and a class of complementarity dynamical systems. Each of these dynamical systems can also be considered as a hybrid dynamical system. This work is of interest since it both generalises some previous results and sheds new light on the relationship between known formalisms.

Rapporteurs : R. Deville (Bordeaux) D.T. Luc (Avignon) J.-E. Martinez-Legaz (Barcelone, Espagne) Examinateurs : J.-P. Crouzeix (Clermont-Ferrand) (President du jury) S. Gautier (Pau) N. Hadjisavvas (Samos, Grece) J.-P. Penot (Pau) L. Thibault (Montpellier); This document is a research contribution on Convex Analysis, on Generalized Convexity and on their applications in Optimization Theory. The first part deals with several fundamental questions concerning continuity, differentiability and criteria of coincidence for the class of convex functions. Convexification processes for lower semicontinuous functions are also studied. For the class of quasiconvex functions two approaches are used: an analytic approach, in the spirit of non-smooth analysis, and a geometric one, based on the notion of normal cones to sublevel sets. The second part is devoted to applications to the integration of multivalued operators, to Variational Inequality Problems and to finite and infinite dimensional multicriteria optimization problems. Among the concepts that are introduced for the first time in this work are: the notion of strong cyclic monotonicity, which characterizes the subdifferential of a convex function with a continuous restriction on its domain; the notion of cyclic quasimonotonicity, an intrinsic property of the subdifferentials of quasiconvex functions with important applications in Mathematical Economics; and the notion of proper quasimonotonicity, which characterizes the class of operators for which the associated Minty Variational Inequality problem has at least one solution on every nonempty convex and weakly compact subset of their domains. Let us finally mention a new characterization of the Radon-Nikodym property, and an extension to infinite dimensions of a result of Janin concerning the integration of the class of maximal cyclically submonotone operators, which generalizes a classical result of Rockafellar for maximal cyclically monotone operators.; Ce document de synthèse s'articule autour de l'analyse convexe, de l'analyse quasi-convexe et des applications en optimisation. Dans le premier domaine on aborde les thèmes de la continuité, de la différentiabilité et des critères de coïncidence pour les fonctions convexes, puis la convexification des fonctions semi-continues inférieurement. Pour l'étude des fonctions quasi-convexes deux approches sont adoptées : une approche analytique, via un sous-différentiel généralisé, et une approche géométrique, basée sur les normales aux tranches. La dernière partie est consacrée à des applications à l'intégration d'opérateurs multivoques, aux inéquations variationnelles et à des problèmes d'optimisation multicritères en dimension finie et infinie. Parmi les nouveautés de ce travail, on trouve la notion de monotonie fortement cyclique, qui caractérise le sous-différentiel d'une fonction convexe dont la restriction à son domaine est continue, la quasi-monotonie cyclique, qui est une propriété intrinsèque du sous-différentiel d'une fonction quasi-convexe avec des applications importantes en économie mathématique, et la notion de quasi-monotonie propre, qui caractérise les opérateurs pour lesquels l'inéquation variationnelle associée a toujours des solutions sur toute sous-partie convexe et faiblement compacte de leur domaine. Notons encore une nouvelle caractérisation de la propriété de Radon-Nikodym, et une extension à la dimension infinie d'un résultat de Janin concernant l'intégration d'un opérateur maximal cycliquement sous-monotone, résultat qui généralise le théorème classique de Rockafellar pour les opérateurs maximaux cycliquement monotones.

Final version has appeared under the title "On a primal-proximal heuristic in discrete optimization", in Math. Program., Ser. A 104, pp 105-128 (2005), DOI 10.1007/s10107-004-0571-2; Lagrangian relaxation is useful to bound the optimal value of a given optimization problem, and also to obtain relaxed solutions. To obtain primal solutions, it is conceivable to use a convexification procedure suggested by D.P. Bertsekas in 1979, based on the proximal algorithm in the primal space. The present paper studies the theory assessing the approach in the framework of combinatorial optimization. Our results indicate that very little can be expected in theory, even though fairly good practical results have been obtained for the unit-commitment problem.

International audience; We consider the question of integration of a multivalued operator $T$, that is the question of finding a function $f $such that $T⊑∂f$. If $∂ $ is the Fenchel–Moreau subdifferential, the above problem has been completely solved by Rockafellar, who introduced cyclic monotonicity as a necessary and sufficient condition. In this article we consider the case where $f$ is quasiconvex and $∂ $ is the lower subdifferential $∂