TIME BOUNDS OF BASIC STEEPEST DESCENT ALGORITHMS FOR M-CONVEX FUNCTION MINIMIZATION AND RELATED PROBLEMS

DOI Web Site Web Site 21 References

Search this article

Abstract

<p>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.</p>

Journal

References(21)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top