The condition number of a function relative to a set

DOI10.1007/S10107-020-01510-4zbMATH Open1470.90077arXiv1901.08359OpenAlexW3023412291MaRDI QIDQ2039239FDOQ2039239

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)

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)$.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

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
• Title not available (Why is that?)
• 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)