Search

This work derives upper bounds on the convergence rate of the moment-sum-of-squares hierarchy with correlative sparsity for global minimization of polynomials on compact basic semialgebraic sets. The main conclusion is that both sparse hierarchies based on the Schm\"udgen and Putinar Positivstellens\"atze enjoy a polynomial rate of convergence that depends on the size of the largest clique in the sparsity graph but not on the ambient dimension. Interestingly, the sparse bounds outperform the best currently available bounds for the dense hierarchy when the maximum clique size is sufficiently small compared to the ambient dimension and the performance is measured by the running time of an interior point method required to obtain a bound on the global minimum of a given accuracy., Comment: 23 pages

This work addresses the occupation measure relaxation of calculus of variations problems, which is an infinite-dimensional linear programming relaxation amenable to numerical approximation by a hierarchy of semidefinite optimization problems. We address the problem of equivalence of this relaxation to the original problem. Our main result provides sufficient conditions for this equivalence. These conditions, revolving around the convexity of the data, are simple and apply in very general settings that may be of arbitrary dimensions and may include pointwise and integral constraints, thereby considerably strengthening the existing results. Our conditions are also extended to optimal control problems. In addition, we demonstrate how these results can be applied in non-convex settings, showing that the occupation measure relaxation is at least as strong as the convexification using the convex envelope; in doing so, we prove that a certain weakening of the occupation measure relaxation is equivalent to the convex envelope. This opens the way to application of the occupation measure relaxation in situations where the convex envelope relaxation is known to be equivalent to the original problem, which includes problems in magnetism and elasticity.

Recent works have proposed linear programming relaxations of variational optimization problems subject to nonlinear PDE constraints based on the occupation measure formalism. The main appeal of these methods is the fact that they rely on convex optimization, typically semidefinite programming. In this work we close an open question related to this approach. We prove that the classical and relaxed minima coincide when the dimension of the codomain of the unknown function equals one, both for calculus of variations and for optimal control problems, thereby complementing analogous results that existed for the case when the dimension of the domain equals one. In order to do so, we prove a generalization of the Hardt-Pitts decomposition of normal currents applicable in our setting. We also show by means of a counterexample that, if both the dimensions of the domain and of the codomain are greater than one, there may be a positive gap. The example we construct to show the latter serves also to show that sometimes relaxed occupation measures may represent a more conceptually-satisfactory "solution" than their classical counterparts, so that -- even though they may not be equivalent -- algorithms rendering accessible the minimum in the larger space of relaxed occupation measures remain extremely valuable. Finally, we show that in the presence of integral constraints, a positive gap may occur at any dimension of the domain and of the codomain., Comment: 46 pages, 10 figures

This paper introduces a new method to tackle the issue of the almost sure convergence of stochastic approximation algorithms defined from a differential inclusion. Under the assumption of slowly decaying step-sizes, we establish that the set of essential accumulation points of the iterates belongs to the Birkhoff center associated with the differential inclusion. Unlike previous works, our results do not rely on the notion of asymptotic pseudotrajectories introduced by Bena\"im--Hofbauer--Sorin, which is the predominant technique to address the convergence problem. They follow as a consequence of Young's superposition principle for closed measures. This perspective bridges the gap between Young's principle and the notion of invariant measure of set-valued dynamical systems introduced by Faure and Roth. Also, the proposed method allows to obtain sufficient conditions under which the velocities locally compensate around any essential accumulation point., Comment: 20 pages

We show that the vanishing stepsize subgradient method -- widely adopted for machine learning applications -- can display rather messy behavior even in the presence of favorable assumptions. We establish that convergence of bounded subgradient sequences may fail even with a Whitney stratifiable objective function satisfying the Kurdyka-Lojasiewicz inequality. Moreover, when the objective function is path-differentiable we show that various properties all may fail to occur: criticality of the limit points, convergence of the sequence, convergence in values, codimension one of the accumulation set, equality of the accumulation and essential accumulation sets, connectedness of the essential accumulation set, spontaneous slowdown, oscillation compensation, and oscillation perpendicularity to the accumulation set., Comment: 27 pages, 4 figures

We consider the long-term dynamics of the vanishing stepsize subgradient method in the case when the objective function is neither smooth nor convex. We assume that this function is locally Lipschitz and path differentiable, i.e., admits a chain rule. Our study departs from other works in the sense that we focus on the behavoir of the oscillations, and to do this we use closed measures. We recover known convergence results, establish new ones, and show a local principle of oscillation compensation for the velocities. Roughly speaking, the time average of gradients around one limit point vanishes. This allows us to further analyze the structure of oscillations, and establish their perpendicularity to the general drift., Comment: 28 pages, 2 figures

We construct a weak KAM theory for higher-dimensional holonomic measures. We define their slices and curves of those slices. We find a weak KAM solution in that context, and we show that in many cases it corresponds to an exact form that satisfies a version of the Hamilton-Jacobi equation. Along the way, we give a characterization of minimizable Lagrangians, as well as some abstract weak KAM machinery., Comment: 19 pages. Full rewrite

The set of closed (or holonomic) measures provides a useful setting for studying optimization problems because it contains all curves, while also enjoying good compactness and convexity properties. We study the way to do variational calculus on the set of closed measures. Our main result is a full description of the distributions that arise as the derivatives of variations of such closed measures. We give examples of how this can be used to extract information about the critical closed measures. The condition of criticality with respect to variations leads, in certain circumstances, to the Euler-Lagrange equations. To understand when this happens, we characterize the closed measures that are invariant under the Euler-Lagrange flow. Our result implies Ricardo Ma\~n\'e's statement that all minimizers are invariant., Comment: 22 pages

In this paper we consider convex subsets of locally-convex topological vector spaces. Given a fixed point in such a convex subset, we show that there exists a curve completely contained in the convex subset and leaving the point in a given direction if and only if the direction vector is contained in the sequential closure of the tangent cone at that point. We apply this result to the characterization of the existence of weakly differentiable families of probability measures on a smooth manifold and of the distributions that can arise as their derivatives. This gives us a way to consider the mass transport equation in a very general context, in which the notion of direction turns out to be given by an element of a Colombeau algebra., Comment: 13 pages

We show that a necessary and sufficient condition for a smooth function on the tangent bundle of a manifold to be a Lagrangian density whose action can be minimized is, roughly speaking, that it be the sum of a constant, a nonnegative function vanishing on the support of the minimizers, and an exact form. We show that this exact form corresponds to the differential of a Lipschitz function on the manifold that is differentiable on the projection of the support of the minimizers, and its derivative there is Lipschitz. This function generalizes the notion of subsolution of the Hamilton-Jacobi equation that appears in weak KAM theory, and the Lipschitzity result allows for the recovery of Mather's celebrated 1991 result as a special case. We also show that our result is sharp with several examples. Finally, we apply the same type of reasoning to an example of a finite horizon Legendre problem in optimal control, and together with the Lipschitzity result we obtain the Hamilton-Jacobi-Bellman equation and the Maximum Principle. This version contains errata correcting an issue in the published version., Comment: 24 pages. Contains errata for the published version

We define holonomic measures to be certain analogues of varifolds that keep track of the local parameterization and orientation of the submanifold they represent. They are Borel measures on the direct sum of several copies of the tangent bundle. We show that there is an approximation to these by smooth singular chains whose boundaries and Lagrangian actions are controlled. As an illustration of the usefulness of this result, we show how this can be applied to study foliations on the torus. We give other applications elsewhere., Comment: 27 pages. Corrected some typos, added some applications and illustrations. Changed the title. Comments are very welcome

Roughly speaking, holonomic measures are parametric varifolds without boundary. They provide a setting appropriate for the analysis of many variational problems. In this paper, we characterize the space of variations for these objects, and we use the characterization to formulate stability conditions that are strictly more general than the Euler-Lagrange equations. We also use this characterization to deduce higher-dimensional analogues of energy conservation and weak KAM. Along the way, we characterize the distributions that arise as derivatives of families of Borel probability measures on smooth manifolds., Comment: 35 pages. Corrected a few typos, added illustrations, examples. Incorporated arXiv:1408.3683. Comments are very welcome

We characterize the distributions that arise as derivatives of families of probabilities and of positive and signed measures on smooth manifolds., Comment: The paper has been withdrawn by the author because its contents have been incorporated to arXiv:1408.5785

After a quick review of the representation theory of the symmetric group, we give an exposition of the tools brought about by the so-called half-infinite wedge representation of the infinite symmetric group. We show how these can be applied to find the limit shapes of several distributions on partitions. We also briefly review the variational methods available to compute these limit shapes., Comment: 41 pages. Workshop: "Taller de vinculacion: matematicos mexicanos jovenes en el mundo." Second version

In the context of the Eskin-Okounkov approach to the calculation of the volumes of the different strata of the moduli space of quadratic differentials, the important ingredients are the pillowcase weight probability distribution on the space of Young diagrams, and the asymptotic study of characters of permutations that near-involutions. In this paper we present various new results for these objects. Our results give light to unforeseen difficulties in the general solution to the problem, and they simplify some of the previous proofs., Comment: This paper elaborates on some of the results of the author's PhD thesis (arXiv:1209.4333). This is the published version, http://ejp.ejpecp.org/article/view/3626

In the context of A. Eskin and A. Okounkov's approach to the calculation of the volumes of the different strata of the moduli space of quadratic differentials, two objects have a prominent role. Namely, the characters of near-involutions and the pillowcase weights. For the former we give a fairly explicit formula. On the other hand, the pillowcase weights induce a distribution on the space of Young diagrams. We analyze this distribution and prove several facts, including that its limit shape corresponds to the one induced by the uniform distribution, that the probability concentrates on the set of partitions with very similar 2-quotients, and that there is no hope for a full Central Limit Theorem. This is a reformatted version of the author's Ph.D. thesis, advised by Professor Andrei Okounkov. The results will be published in a forthcoming paper., Comment: PhD thesis, Princeton University, 2012. Reformatted version. The results will be published in a forthcoming paper