Fast computation of Lipschitz constants on hyperrectangles using sparse codelists

摘要

We propose and compare methods for the efficient calculation of Lipschitz constants of differentiable functions on hyperrectangular sets. Two new approaches are presented here that are inspired by techniques for the calculation of Hessian spectral bounds for czBB, a method that Professor Christodoulos A. Floudas proposed as a young researcher and continuously refined over his entire career.We compare the new approaches to existing ones with respect to two features, their computational cost, and the tightness of the resulting constants. The new algorithms are designed to require fewer operations than the existing ones. Not surprisingly, they result in fairly conservative Lipschitz constants. We show, however, that this conservatism can be mitigated considerably by incorporating structural information. More specifically, all methods considered here use codelists that are extended by first order derivatives. Extended codelists involve sparse intermediate gradients, since early codelist lines depend on very few variables by construction (for any nontrivial function, not just in special cases). This sparsity can be used to improve the Lipschitz constants.We compare the computational cost and tightness of the existing and new approaches from a theoretical point of view and corroborate the results with a large number of computational experiments involving several hundred sample functions on random hyperrectangular sets. We claim that one of the new sparse methods is an attractive option for algorithms that require Lipschitz constants on many hyperrectangular sets (such as global branch and bound Lipschitz optimization), since it is less computationally expensive than existing approaches and provides similar Lipschitz constants. (C) 2018 Elsevier Ltd. All rights reserved.