An elementary survey of general duality theory in mathematical programming |
| |
Authors: | Jorgen Tind Laurence A Wolsey |
| |
Institution: | 1. Institute for Operations Research, Aarhus University, Aarhus, Denmark 2. CORE, Université Catholique de Louvain, Louvain-la-Neuve, Belgium
|
| |
Abstract: | We survey some recent developments in duality theory with the idea of explaining and unifying certain basic duality results in both nonlinear and integer programming. The idea of replacing dual variables (prices) by price functions, suggested by Everett and developed by Gould, is coupled with an appropriate dual problem with the consequence that many of the results resemble those used in linear programming. The dual problem adopted has a (traditional) economic interpretation and dual feasibility then provides a simple alternative to concepts such as conjugate functions or subdifferentials used in the study of optimality. In addition we attempt to make precise the relationship between primal, dual and saddlepoint results in both the traditional Lagrangean and the more general duality theories and to see the implications of passing from prices to price functions. Finally, and perhaps surprisingly, it appears that all the standard algorithms terminate by constructing primal and dual feasible solutions of equal value, i.e., by satisfying generalised optimality conditions. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|