An optimal bound for d.c. programs with convex constraints

A well-known strategy for obtaining a lower bound on the minimum of a d.c. function f - g over a compact convex set S subset of R-n consists of replac ing the convex function f by a linear minorant at x(0) is an element of S. In this note we show that the x(0)* giving the optimal bound can be obtaine d by solving a convex minimization program, which corresponds to a Lagrangi an decomposition of the problem. Moreover, if S is a simplex, the optimal L agrangian multiplier can be obtained by solving a system of n + 1 linear eq uations.