On the properties of the subsets of a discrete domain defined by the local optimae of a function endowed with some geometrical properties Original Research Article

We propose here a characterization of the subsets of Rn which may be considered as the sets of the local optima of the restriction of some convex function to some discrete subset, and we prove that, under some conditions, recognizing these subsets can be done in polynomial time. We discuss eventual applications of these results to global optimization problems.