LAGRANGE DUALITY AND PARTITIONING TECHNIQUES IN NONCONVEX GLOBAL OPTIMIZATION

It is shown that, for very general classes of nonconvex global optimiz ation problems, the duality gap obtained by solving a corresponding La grangian dual in reduced to zero in the limit when combined with suita bly refined partitioning of the feasible set. A similar result holds f or partly convex problems where exhaustive partitioning is applied onl y in the space of nonconvex variables. Applications include branch-and -bound approaches for linearly constrained problems where convex envel opes can be computed, certain generalized bilinear problems, linearly constrained optimization of the sum of ratios of affine functions, and concave minimization under reverse convex constraints.