-

 

 

 




Optimization Online





 

The condition of a function relative to a polytope

David H. Gutman(dgutman***at***andrew.cmu.edu)
Javier Pena(jfp***at***andrew.cmu.edu)

Abstract: The condition number of a smooth 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 precisely the square of the diameter-to-width 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 minimization. We propose a condition number of a smooth convex function relative to a reference polytope. This relative condition number is defined as the ratio of a relative smooth constant to a relative strong convexity constant of the function, where both constants are relative to the reference polytope. The relative condition number extends the main properties of the traditional condition number. In particular, we show that the condition number of a quadratic convex function relative to a polytope is precisely the square of the diameter-to-facial-distance ratio of a scaled polytope for a canonical scaling induced by the function. Furthermore, we illustrate how the relative condition number of a function bounds the linear rate of convergence of first-order methods for minimization of the function over the polytope.

Keywords: Condition, facial distance, linear convergence

Category 1: Convex and Nonsmooth Optimization

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Technical Report. Carnegie Mellon University

Download: [PDF]

Entry Submitted: 02/02/2018
Entry Accepted: 02/02/2018
Entry Last Modified: 02/02/2018

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
Mathematical Optimization Society