Duality in Nonlinear Programming: A Simplified Applications-Oriented Development
This report has yet to be scanned by Contrails staff
Report Number: RM-6314-PR
Author(s): Geoffrion, A. M.
Corporate Author(s): The Rand Corporation
Date of Publication: 1970-06
Contract: F44620-67-C-0045
DoD Task:
Identifier: AD0709184
Abstract:
This study extends and reworks much of what is known about duality theory for nonlinear programming. In the Air Force, such problems as allocating scarce resources and long-term program planning are becoming more complex, and techniques such as those described here offer potentially useful mathematical possibilities for solving them. Duality theory gives "prices" for scarce resources, and sop it is useful for studying the effects of changing resource availability. Certain planning problems are more easily solved by passing to an equivalent dual problem. for instance, such issues arise in scheduling models (J. L. Midler and R. D. Wollmer, A Flight Planning Model for the Military Airlift Command , The Rand Coporation, RM-5722-PR, October 1968) and in inventory applications (B. Fox and D. M. Landi, Optimization Problems with One Constraint , The Rand Corporation, RM-5791-PR, October 1968). The number of computational or theoretical applications of nonlinear duality theory is small compared to the number of theoretical papers on this subject over the last decade. It is hoped the work described here will diminish the existing obstacles to successful application. New results are given for important but usually neglected questions concerning the computational solution of a program via its dual. Several applications are made to the general theory of convex systems.The general approach exploits the powerful concept of a perturbation function, thus permitting simplified proofs (no conjugate functions or fixed-point theorems are needed) and useful geometric and mathematical insights. Consideration is limited to finite dimensional space.The author carried out this work as a consultant to The Rand Corporation and also under the auspices of National Science Foundation Grant GP-8740.
Author(s): Geoffrion, A. M.
Corporate Author(s): The Rand Corporation
Date of Publication: 1970-06
Contract: F44620-67-C-0045
DoD Task:
Identifier: AD0709184
Abstract:
This study extends and reworks much of what is known about duality theory for nonlinear programming. In the Air Force, such problems as allocating scarce resources and long-term program planning are becoming more complex, and techniques such as those described here offer potentially useful mathematical possibilities for solving them. Duality theory gives "prices" for scarce resources, and sop it is useful for studying the effects of changing resource availability. Certain planning problems are more easily solved by passing to an equivalent dual problem. for instance, such issues arise in scheduling models (J. L. Midler and R. D. Wollmer, A Flight Planning Model for the Military Airlift Command , The Rand Coporation, RM-5722-PR, October 1968) and in inventory applications (B. Fox and D. M. Landi, Optimization Problems with One Constraint , The Rand Corporation, RM-5791-PR, October 1968). The number of computational or theoretical applications of nonlinear duality theory is small compared to the number of theoretical papers on this subject over the last decade. It is hoped the work described here will diminish the existing obstacles to successful application. New results are given for important but usually neglected questions concerning the computational solution of a program via its dual. Several applications are made to the general theory of convex systems.The general approach exploits the powerful concept of a perturbation function, thus permitting simplified proofs (no conjugate functions or fixed-point theorems are needed) and useful geometric and mathematical insights. Consideration is limited to finite dimensional space.The author carried out this work as a consultant to The Rand Corporation and also under the auspices of National Science Foundation Grant GP-8740.