  


The condition number of a function relative to a set
David Gutman (dgutmanandrew.cmu.edu) 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 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 firstorder methods for constrained convex minimization. Keywords: condition number, firstorder methods, strong convexity, smoothness Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Working Paper, Tepper School of Business, Carnegie Mellon University, January 2019 Download: [PDF] Entry Submitted: 01/24/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  