Scaling, proximity, and optimization of integrally convex functions
成果类型：
Article
署名作者：
Moriguchi, Satoko; Murota, Kazuo; Tamura, Akihisa; Tardella, Fabio
署名单位：
Tokyo Metropolitan University; Keio University; Sapienza University Rome
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-018-1234-z
发表日期：
2019
页码：
119-154
关键词：
摘要：
In discrete convex analysis, the scaling and proximity properties for the class of L?-convex functions were established more than a decade ago and have been used to design efficient minimization algorithms. For the larger class of integrally convex functions of n variables, we show here that the scaling property only holds when n2, while a proximity theorem can be established for any n, but only with a superexponential bound. This is, however, sufficient to extend the classical logarithmic complexity result for minimizing a discrete convex function of one variable to the case of integrally convex functions of any fixed number of variables.