Convexity and global optimization: a theoretical link

Here we propose a characterization of the subsets of R-n which are the sets of local optima of the restriction of some convex function to some discret e subset, and we prove that, under some conditions, recognizing these subse ts can be done in polynomial time. We discuss eventual applications of thes e results to global optimization problems. (C) 2001 Elsevier Science BN. Al l rights reserved.