The condition number of a function relative to a set

DOI10.1007/S10107-020-01510-4MaRDI QIDQ2039239zbMATH OpenOpenAlexFDO

Authors David H. Gutman, Javier Peña

Publication date 2 July 2021

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Convex programming (90C25) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Methods of reduced gradient type (90C52)

Abstract: The condition number of a differentiable convex function, namely the ratio of its smoothness to strong convexity constants, is closely tied to fundamental properties of the function. In particular, the condition number of a quadratic convex function is the square of the aspect ratio of a canonical ellipsoid associated to the function. Furthermore, the condition number of a function bounds the linear rate of convergence of the gradient descent algorithm for unconstrained convex minimization. We propose a condition number of a differentiable convex function relative to a reference convex set and distance function pair. This relative condition number is defined as the ratio of a relative smoothness to a relative strong convexity constants. We show that the relative condition number extends the main properties of the traditional condition number both in terms of its geometric insight and in terms of its role in characterizing the linear convergence of first-order methods for constrained convex minimization. When the reference set $X$ is a convex cone or a polyhedron and the function $f$ is of the form $f=gcircA$, we provide characterizations of and bounds on the condition number of $f$ relative to $X$ in terms of the usual condition number of $g$ and a suitable condition number of the pair $(A,X)$.

Recommendations

• Condition numbers and error bounds in convex programming
• On condition number theorems in mathematical programming
• A condition number theorem in convex programming
• Optimizing condition numbers
• Some results on condition numbers in convex multiobjective optimization

Cites work

• A conditional gradient method with linear rate of convergence for solving convex linear systems
• A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
• A new condition measure, preconditioners, and relations between different measures of conditioning for conic linear systems
• A new condition number for linear programming
• A simplified view of first order methods for optimization
• An optimal first order method based on optimal quadratic averaging
• Complexity of convex optimization using geometry-based measures and a reference point
• Computational Experience and the Explanatory Value of Condition Measures for Linear Optimization
• Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system
• Condition-Based Complexity of Convex Optimization in Conic Linear Form via the Ellipsoid Algorithm
• Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
• Enhanced basic procedures for the projection and rescaling algorithm
• Gradient methods for minimizing composite functions
• Ill-conditioned convex processes and conic linear systems.
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• Introductory lectures on convex optimization. A basic course.
• Linear convergence of first order methods for non-strongly convex optimization
• Linear programming, complexity theory and elementary functional analysis
• Linearly convergent away-step conditional gradient for non-strongly convex functions
• New characterizations of Hoffman constants for systems of linear constraints
• Polytope conditioning and linear convergence of the Frank-Wolfe algorithm
• Relatively smooth convex optimization by first-order methods, and applications
• Some comments on Wolfe's ‘away step’
• The radius of metric regularity
• Towards a deeper geometric, analytic and algorithmic understanding of margins
• Understanding the Geometry of Infeasible Perturbations of a Conic Linear System

Cited in

(8)

• Condition numbers and error bounds in convex programming
• Faster first-order primal-dual methods for linear programming using restarts and sharpness
• Frank--Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
• Kissing polytopes
• scientific article; zbMATH DE number 3048369 (Why is no real title available?)
• Generalized self-concordant analysis of Frank-Wolfe algorithms
• On the geometric convergence of Byzantine-resilient distributed optimization algorithms
• Frank-Wolfe and friends: a journey into projection-free first-order optimization methods

This page was built for publication: The condition number of a function relative to a set

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