出版社：Japan Science and Technology Information Aggregator, Electronic
摘要：The concept of M-convex function gives a unified framework for discrete optimization problems with nonlinear objective functions such as the minimum convex cost flow problem and the convex resource allocation problem. M-convex function minimization is one of the most fundamental problems concerning M-convex functions. It is known that a minimizer of an M-convex function can be found by a steepest descent algorithm in a finite number of iterations. Recently, the exact number of iterations required by a basic steepest descent algorithm was obtained. Furthermore, it was shown that the trajectory of the solutions generated by the basic steepest descent algorithm is a geodesic between the initial solution and the nearest minimizer. In this paper, we give a simpler and shorter proof of this claim by refining the minimizer cut property. We also consider the minimization of a jump M-convex function, which is a generalization of M-convex function, and analyze the number of iterations required by the basic steepest descent algorithm. In particular, we show that the trajectory of the solutions generated by the algorithm is a geodesic between the initial solution and the nearest minimizer.
关键词：Discrete optimization;discrete convex function;steepest descent method;analysis of algorithm
