Second Order Conditions to Decompose Smooth Functions as Sums of Squares

DOI10.1137/22M1480914MaRDI QIDQ6202760zbMATH OpenOpenAlexWikidataFDO

Authors Francis Bach, Alessandro Rudi

Publication date 27 February 2024

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.13729

zbMATH Keywords

global optimizationmanifoldssecond ordersum of squaresnonnegative functions

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Classical differential geometry (53A99) Derivative-free methods and methods using generalized derivatives (90C56) Sums of squares and representations by other particular quadratic forms (11E25) Real-valued functions on manifolds (58C05)

Abstract: We consider the problem of decomposing a regular non-negative function as a sum of squares of functions which preserve some form of regularity. In the same way as decomposing non-negative polynomials as sum of squares of polynomials allows to derive methods in order to solve global optimization problems on polynomials, decomposing a regular function as a sum of squares allows to derive methods to solve global optimization problems on more general functions. As the regularity of the functions in the sum of squares decomposition is a key indicator in analyzing the convergence and speed of convergence of optimization methods, it is important to have theoretical results guaranteeing such a regularity. In this work, we show second order sufficient conditions in order for a $p$ times continuously differentiable non-negative function to be a sum of squares of $p-2$ differentiable functions. The main hypothesis is that, locally, the function grows quadratically in directions which are orthogonal to its set of zeros. The novelty of this result, compared to previous works is that it allows sets of zeros which are continuous as opposed to discrete, and also applies to manifolds as opposed to open sets of $R^d$. This has applications in problems where manifolds of minimizers or zeros typically appear, such as in optimal transport, and for minimizing functions defined on manifolds.

Recommendations

• Sums of squares. I: Scalar functions
• scientific article; zbMATH DE number 2161529
• Sums of squares. II: Matrix functions
• Sommes de carrés de fonctions dérivables
• Low-Rank Univariate Sum of Squares Has No Spurious Local Minima

Cites work

• scientific article; zbMATH DE number 527343 (Why is no real title available?)
• A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
• An introduction to differential manifolds. Translated from the 2nd French edition by Jonathan Upjohn
• Exponential Convergence of Sum-of-Squares Hierarchies for Trigonometric Polynomials
• Hypoelliptic second order differential equations
• Moments, positive polynomials and their applications
• Morse Theory. (AM-51)
• Nonnegative functions as squares or sums of squares
• ON THE FEFFERMAN–PHONG INEQUALITY AND RELATED PROBLEMS
• On Hilbert's 17th problem and real Nullstellensatz for global analytic functions
• On positivity of pseudo-differential operators
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Optimality conditions and finite convergence of Lasserre's hierarchy
• Representations of non-negative polynomials having finitely many zeros
• Semidefinite programming relaxations for semialgebraic problems
• Sommes de carrés de fonctions dérivables
• The K-moment problem for compact semi-algebraic sets
• The analysis of linear partial differential operators. III: Pseudo-differential operators
• Theory of Reproducing Kernels
• Topics in global real analytic geometry

Cited in

(1)

• Sums of squares. II: Matrix functions

This page was built for publication: Second Order Conditions to Decompose Smooth Functions as Sums of Squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202760)