Cutting Plane Algorithms for Maximum Problems

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1991
Accession Number
ADA245788

Entities

People

  • Donald W. Hearn
  • Siriphong Lawphongpanich

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Convex Programming
  • Equations
  • Evolutionary Algorithms
  • Heuristic Methods
  • Inequalities
  • Integer Programming
  • Iterations
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • New York
  • Nonlinear Programming
  • Operations Research
  • Optimization
  • Systems Engineering

Readers

  • Operations Research