Title

A Duality Theory with Zero Duality Gap for Nonlinear Programming

Authors

Yixin Chen, Washington University in St LouisFollow

Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2007

Filename

wucse-2007-12.pdf

DOI:

10.7936/K7610XJS

Technical Report Number

WUCSE-2007-12

Abstract

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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7610XJS

Recommended Citation

Chen, Yixin, "A Duality Theory with Zero Duality Gap for Nonlinear Programming" Report Number: WUCSE-2007-12 (2007). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/117