M-Convex Function Minimization by Continuous Relaxation Approach: Proximity Theorem and Algorithm
Satoko Moriguchi, Akiyoshi Shioura, Nobuyuki Tsuchimura · SIAM Journal on Optimization · 2011
The concept of M-convexity for functions in integer variables, introduced by Murota [Adv. Math., 124 (1996), pp. 272–311], plays a primary role in the theory of discrete convex analysis. In this paper, we consider the problem of minimizing an M-convex function, which is a natural generalization of the separable convex resource allocation problem under a submodular constraint and contains some classes of nonseparable convex function minimization on integer lattice points. We propose a new approach for M-convex function minimization based on continuous relaxation. By establishing proximity theorems we develop a new algorithm based on continuous relaxation. We apply the approach to some special cases of the separable convex quadratic resource allocation problem and the convex quadratic tree resource allocation problem to obtain faster algorithms.