Primal-Dual Methods for Linear Programming

Abstract

Many interior-point methods for linear programming are based on the properties of the logarithmic barrier function. We first give a convergence proof for the (primal) projected Newton barrier method. We then analyze three types of barrier method that can be categorized as primal, dual and primal-dual. All three approaches may be derived from the application of Newton's method to different variants of the same system of nonlinear equations. A fourth variant of the same equations leads to a new primal-dual algorithm. In each of the methods discussed, covergence is demonstrated without the need for a nondegeneracy assumption. In particular, convergence is established for a primal-dual algorithm that allows a different step in the primal and dual variables. Finally, we describe a new method for treating free variables.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1991
Accession Number
ADA237418

Entities

People

  • Dulce B. Ponceleon
  • Michael Saunders
  • Philip Edward Gill
  • Walter Murray

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Civil Engineering
  • Computer Programming
  • Convergence
  • Engineering
  • Equations
  • Evolutionary Algorithms
  • Linear Programming
  • Linear Systems
  • Mathematical Programming
  • Mathematics
  • New York
  • Nonlinear Programming
  • Operations Research
  • Optimization
  • Quadratic Programming
  • Sequences

Fields of Study

  • Mathematics

Readers

  • Operations Research