A Nontangential Cutting Plane Algorithm

Abstract

The cutting plane algorithm typically generates cuts that are tangential, or nearly so, to the Lagrangian dual function of the underlying optimization problem. This paper demonstrates that the algorithm still converges to an optimal solution when cuts are nontangential. These cuts are generated by not solving the subproblems to optimality or nearly so. Computational results from randomly generated linear and quadratic programming problems indicate that nontangential cuts can lead to a more efficient algorithm.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 2001
Accession Number
ADA392399

Entities

People

  • Siriphong Lawphongpanich

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Convergence
  • Evolutionary Algorithms
  • Heuristic Methods
  • Iterations
  • Linear Programming
  • Mathematical Programming
  • Nonlinear Programming
  • Operating Systems
  • Operations Research
  • Optimization
  • Quadratic Programming
  • Schools
  • Sequences
  • Simplex Method

Readers

  • Operations Research