A Cubically Convergent Method for Locating a Nearby Vertex in Linear Programming

Abstract

Given a point sufficiently close to a nondegenerate basic feasible solution x* of a linear program, we show how to generate a sequence {p-superscript-k} that converges to the 0-1 vector sign(x*) at a Q-cubic rate. This extremely fast convergence enables us to determine, with a high degree of certainty, which variables will be zero and which will be nonzero at optimality and then construct x* from this information.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1989
Accession Number
ADA455264

Entities

People

  • Richard A. Tapia
  • Yin Zhang

Organizations

  • Rice University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Applied Mathematics
  • Computer Programming
  • Information Operations
  • Linear Programming
  • Mathematics
  • Operations Research
  • Sequences

Readers

  • Operations Research