Cutting plane algorithms for maximum problems
Loading...
Authors
Lawphongpanich, Siriphong
Hearn, Donald W.
Subjects
Cutting plane algorithm; variational inequalities; Lagrangian dual; Bender's decomposition
Advisors
Date of Issue
1991-12
Date
1991-12
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
This paper unifies the development of the cutting plane algorithm for mathematical programs and variational inequalities by providing one common framework for establishing convergence. strategies for generating cuts are provided for cases in which the algorithm yields easy and difficult subproblems. When the subproblem is easy to solve, a line search is added and a deep cut is selected to accelerate the algorithm. On the other hand, when the subproblem is difficult to solve, the problem is only solved approximately during the early iterations. This corresponds to generating cuts which are nontangential to the underlying objective function. Moreover, in the case of variational inequalities, it is shown further that the subproblem can be eliminated entirely from the algorithmic steps, thereby making the resulting algorithm especially advantageous
Type
Technical Report
Description
Series/Report No
Department
Organization
Identifiers
NPS Report Number
NPS-OR-92-008
Sponsors
National Science Foundation, Washington, DC
Funding
O&MN Direct Funding
Format
Citation
Distribution Statement
Approved for public release; distribution is unlimited.