A constructive approach to strengthen algebraic descriptions of function and operator classes

2025/04/19 by Rubbens, Anne, Hendrickx, Julien M., Taylor, Adrien
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2504.14377

Abstract

It is well known that functions (resp. operators) satisfying a property~p on a subset Q⊂ ℝ^d cannot necessarily be extended to a function (resp. operator) satisfying~p on the whole of~ℝ^d. Given Q ⊆ ℝ^d, this work considers the problem of obtaining necessary and ideally sufficient conditions to be satisfied by a function (resp. operator) on Q, ensuring the existence of an extension of this function (resp. operator) satisfying p on ℝ^d. More precisely, given some property p, we present a refinement procedure to obtain stronger necessary conditions to be imposed on Q. This procedure can be applied iteratively until the stronger conditions are also sufficient. We illustrate the procedure on a few examples, including the strengthening of existing descriptions for the classes of smooth functions satisfying a Łojasiewicz condition, convex blockwise smooth functions, Lipschitz monotone operators, strongly monotone cocoercive operators, and uniformly convex functions. In most cases, these strengthened descriptions can be represented, or relaxed, to semi-definite constraints, which can be used to formulate tractable optimization problems on functions (resp. operators) within those classes.

Citations

• On the Worst-Case Analysis of Cyclic Block Coordinate Descent type Algorithms
• Performance Estimation for Smooth and Strongly Convex Sets
• A constraint-based approach to function interpolation, with application to performance estimation for weakly convex optimisation
• On Fundamental Proof Structures in First-Order Optimization
• Interpolation Conditions for Linear Operators and Applications to Performance Estimation Problems
• Convergence rate analysis of randomized and cyclic coordinate descent for convex optimization through semidefinite programming
• On the Worst-Case Analysis of Cyclic Coordinate-Wise Algorithms on Smooth Convex Functions
• Optimal first-order methods for convex functions with a quadratic upper bound
• Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalities
• Conditions for linear convergence of the gradient method for non-convex optimization
• PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python
• Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity
• Optimal Complexity and Certification of Bregman First-Order Methods
• Regularity as Regularization: Smooth and Strongly Convex Brenier Potentials in Optimal Transport
• On the Properties of Convex Functions over Open Sets
• Operator Splitting Performance Estimation: Tight contraction factors and optimal parameter selection
• Explicit formulas for C^1,1 Glaeser-Whitney extensions of 1-fields in Hilbert spaces
• Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition
• Interpolation of data by smooth non-negative functions
• An Extension Theorem for convex functions of class C^1,1 on Hilbert spaces
• Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
• From error bounds to the complexity of first-order descent methods for convex functions
• From error bounds to the complexity of first-order descent methods for convex functions
• Whitney Extension Theorems for convex functions of the classes C¹ and C^1,ω
• Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods
• Smooth convex extensions of convex functions
• Extension of Convex Function
• Performance of first-order methods for smooth convex minimization: a\n novel approach
• Multivariate convex regression with adaptive partitioning
• Primal-dual subgradient methods for minimizing uniformly convex functions
• Algorithms in Real Algebraic Geometry
• Gradient methods for the minimisation of functionals

Related

• Some methods for constructing new operator monotone functions from old ones
• A remark on the extension of a class of linear functionals
• General Resolvents for Monotone Operators: Characterization and Extension
• Restrictions of continuous functions
• Extension criteria for homogeneous Sobolev space of functions of one variable