A Duality Theory with Zero Duality Gap for Nonlinear Programming

Duality is an important notion for constrained optimization which provides a theoretical foundation for a number of constraint decomposition schemes such as separable programming and for deriving lower bounds in space decomposition algorithms such as branch and bound. However, the conventional duality theory has the fundamental limit that it leads to duality gaps for nonconvex optimization problems, especially discrete and mixed-integer problems where the feasible sets are nonconvex. In this paper, we propose a novel extended duality theory for nonlinear optimization that overcomes some limitations of previous dual methods. Based on a new dual function, the extended duality theory leads to zero duality gap for general nonconvex problems defined in discrete, continuous, and mixed-integer spaces under mild conditions.