Solving Reduced KKT Systems in Barrier Methods for Linear and Quadratic Programming

Abstract

In barrier methods for constrained optimization, the main work lies in solving large linear systems Kp = r, where K is symmetric and indefinite. We have implemented reduced KKT systems in a primal-dual algorithm for linear programming, based on the sparse indefinite solver MA27 from the Harwell Subroutine Library. Some features of the algorithm are presented, along with results on the netlib LP test set.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1991
Accession Number
ADA239191

Entities

People

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

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Civil Engineering
  • Computations
  • Computer Programming
  • Engineering
  • Evolutionary Algorithms
  • Industrial Engineering
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Operations Research
  • Optimization
  • Quadratic Programming
  • Simplex Method
  • Systems Engineering
  • Test Sets
  • United States

Fields of Study

  • Mathematics

Readers

  • Operations Research