Convex kernel underestimation of functions with multiple local minima

Convex kernel underestimation of functions with multiple local minima

0.00 Avg rating0 Votes
Article ID: iaor2007436
Country: Netherlands
Volume: 34
Issue: 1
Start Page Number: 35
End Page Number: 45
Publication Date: May 2006
Journal: Computational Optimization and Applications
Authors: , ,
Abstract:

A function on Rn with multiple local minima is approximated from below, via linear programming, by a linear combination of convex kernel functions using sample points from the given function. The resulting convex kernel underestimator is then minimized, using either a linear equation solver for a linear–quadratic kernel or by a Newton method for a Gaussian kernel, to obtain an approximation to a global minimum of the original function. Successive shrinking of the original search region to which this procedure is applied leads to fairly accurate estimates, within 0.0001% for a Gaussian kernel function, relative to global minima of synthetic nonconvex piecewise-quadratic functions for which the global minima are known exactly. Gaussian kernel underestimation improves by a factor of ten the relative error obtained using a piecewise-linear underestimator, while cutting computational time by an average factor of over 28.

Reviews

Required fields are marked *. Your email address will not be published.