 |
||||||||||||||||||||||||||||||||||||||||||||||||||
| Volume 5, Number 2, May 2009, pp. 227-236 | ||||||||||||||||||||||||||||||||||||||||||||||||||
| Satoko Moriguchi and Nobuyuki Tsuchimura | ||||||||||||||||||||||||||||||||||||||||||||||||||
| Key words: | ||||||||||||||||||||||||||||||||||||||||||||||||||
| discrete optimization, discrete convex function, submodular function, algorithm | ||||||||||||||||||||||||||||||||||||||||||||||||||
| Mathematices Subject Classification: 52A41, 90C27 | ||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||
| Volume 5, Number 2, May 2009, pp. 227-236 | ||||||||||||||||||||||||||||||||||||||||||||||||||
| Satoko Moriguchi and Nobuyuki Tsuchimura | ||||||||||||||||||||||||||||||||||||||||||||||||||
| Key words: | ||||||||||||||||||||||||||||||||||||||||||||||||||
| discrete optimization, discrete convex function, submodular function, algorithm | ||||||||||||||||||||||||||||||||||||||||||||||||||
| Mathematices Subject Classification: 52A41, 90C27 | ||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||
| Abstract: | |||
We consider the problem of minimizing a nonlinear discrete function with  -convexity proposed in the theory of discrete convex analysis. For this problem, a steepest descent algorithm and a steepest descent scaling algorithm are known. In this paper, we propose a continuous relaxation approach which first minimizes the continuous variable version in order to find a good initial solution of the steepest descent algorithm. For discrete -convex functions, we give a proximity theorem showing that a discrete global minimizer exists in a neighborhood of a continuous global minimizer. This proximity theorem affords a theoretical guarantee for the efficiency of the proposed algorithm. |
|||
| Discrete L-convex function minimization based on continuous relaxation | ||