Technical Note—Sharper Bounds on Nonconvex Programs

Recently it was pointed out that the generalized Lagrange-multiplier method provides a sharper bound on a nonconvex program than does the solution of the program formed by taking convex envelopes of all functions involved in the original problem. This note points out that the bounds are the same if the original problem has only linear constraints, or if the problem is separable with certain properties, and give an example in which the bounds differ. The better bound is currently being used in locating global solutions of nonconvex, separable, piecewise-linear problems.