On Steepest Descent Algorithms for Discrete Convex Functions
On Steepest Descent Algorithms for Discrete Convex Functions
复制标题
DOI：
10.1137/s1052623402419005
复制
发表时间：
2003-03
期刊：
影响因子：
--
通讯作者：
K. Murota
中科院分区：
文献类型：
--
作者：
K. Murota
本文研究了两类离散凸函数（M 凸函数和 L 凸函数）的最速下降算法的复杂性。简单的平局打破规则产生复杂性界限，该界限是变量维度和有效域大小的多项式。将当前结果与标准缩放方法相结合，得出一种用于 L 凸函数最小化的有效算法。
This paper investigates the complexity of steepest descent algorithms for two classes of discrete convex functions: M-convex functions and L-convex functions. Simple tie-breaking rules yield complexity bounds that are polynomials in the dimension of the variables and the size of the effective domain. Combining the present results with a standard scaling approach leads to an efficient algorithm for L-convex function minimization.