More virtuous smoothing

L Xu, J Lee, D Skipper�- SIAM Journal on Optimization, 2019 - SIAM
SIAM Journal on Optimization, 2019SIAM
In the context of global optimization of mixed-integer nonlinear optimization formulations, we
consider smoothing univariate functions f that satisfy f(0)=0, f is increasing and concave on
0,+∞), f is twice differentiable on all of (0,+∞), but f'(0) is undefined or intolerably large. The
canonical examples are root functions f(w):=w^p for 0<p<1. We consider the earlier
approach of defining a smoothing function g that is identical with f on (δ,+∞), for some
chosen δ>0, then replacing the part of f on 0,δ with the unique homogeneous cubic�…
In the context of global optimization of mixed-integer nonlinear optimization formulations, we consider smoothing univariate functions that satisfy , is increasing and concave on , is twice differentiable on all of , but is undefined or intolerably large. The canonical examples are root functions for . We consider the earlier approach of defining a smoothing function that is identical with on , for some chosen , then replacing the part of on with the unique homogeneous cubic, matching , , and at . The parameter is used to control (i.e., upper bound) the derivative at 0 (which controls it on all of when is concave). Our main results are as follows: (i) we weaken an earlier sufficient condition to give a necessary and sufficient condition for the piecewise function to be increasing and concave; (ii) we give a general sufficient condition for to be decreasing in the smoothing parameter , and under the same condition we demonstrate that the worst-case error of as an estimate of is increasing in ; (iii) we give a general sufficient condition for to underestimate ; (iv) we give a general sufficient condition for to dominate the simple “shift smoothing” () when the parameters and are chosen “fairly,” i.e., so that . In doing so, we solve two natural open problems of Lee and Skipper [J. Global Optim., 69 (2017), pp. 677--697] concerning (iii) and (iv) for root functions.
Society for Industrial and Applied Mathematics