A Build-Up Interior Method for Linear Programming: Affine Scaling Form

Abstract

We proposed a build-up interior method for solving an m equation n variable linear program which has the same convergence properties as their well known analogues in dual affine and projective forms but requires less computational effort. The algorithm has three forms, an affine scaling form, a projective scaling form, and an exact form (that used pivot steps). In this paper, we present the first of these. It differs from Dikin's algorithm of dual affine form in that the ellipsoid chosen to generate the improving directions in dual space is constructed from only a subset of the dual constraints. (KR)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1990
Accession Number
ADA221802

Entities

People

  • George Bernard Dantzig
  • Yinyu Ye

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Computations
  • Computer Programming
  • Convergence
  • Ellipsoids
  • Iterations
  • Linear Programming
  • Military Research
  • Operations Research
  • Optimization
  • Procedures (Computers)
  • United States
  • United States Government

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Space