2023/08/01 by Streeter, Matthew, Dillon, Joshua V.
#Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2308.00679
It is often useful to have polynomial upper or lower bounds on a one-dimensional function that are valid over a finite interval, called a trust region. A classical way to produce polynomial bounds of degree k involves bounding the range of the kth derivative over the trust region, but this produces suboptimal bounds. We improve on this by deriving sharp polynomial upper and lower bounds for a wide variety of one-dimensional functions. We further show that sharp bounds of degree k are at least k+1 times tighter than those produced by the classical method, asymptotically as the width of the trust region approaches zero. We discuss how these sharp bounds can be used in majorization-minimization optimization, among other applications.