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⊂ℝ<Superscript>n</Superscript> consists of replacing the convex function f by a linear minorant at x <Subscript>0</Subscript>∈S. In this note we show that the x <Subscript>0</Subscript> <Superscript>*</Superscript> giving the optimal bound can be obtained by solving a convex minimization program, which corresponds to a Lagrangian decomposition of the problem. Moreover, if S is a simplex, the optimal Lagrangian multiplier can be obtained by solving a system of n + 1 linear equations. Copyright Springer-Verlag Berlin Heidelberg 2001