A Practical Anti-Cycling Procedure for Linear and Nonlinear Programming

Abstract

A new method is given for preventing the simplex method from cycling. Key features are that a positive step is taken at every iteration, and nonbasic variables are allowed to be slightly infeasible. There is no additional work per iteration. Computational results are given for the first 53 test problems in netlib, indicating reliable performance in all cases. The method may be applied to active-set methods for solving nonlinear programs with linear constraints. Keywords: EXPAND procedure, EXPAND(Expanding Tolerance Anti-Degeneracy), Optimization.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1988
Accession Number
ADA198943

Entities

People

  • Philip Edward Gill
  • Walter Murray

Organizations

  • Stanford University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Computations
  • Computer Programming
  • Evolutionary Algorithms
  • Linear Programming
  • Mathematical Programming
  • New York
  • Nonlinear Programming
  • Numerical Analysis
  • Operations Research
  • Optimization
  • Quadratic Programming
  • Simplex Method
  • Surface Plasmons
  • United States

Readers

  • Operations Research