Accession Number:

ADA455264

Title:

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

Descriptive Note:

Technical rept.

Corporate Author:

RICE UNIV HOUSTON TX DEPT OF MATHEMATICAL SCIENCES

Personal Author(s):

Report Date:

1989-12-01

Pagination or Media Count:

13.0

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 signx 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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE