A Very Simple Polynomial-Time Algorithm for Linear Programming

Abstract

This document proposes a polynomial-time algorithm for linear programming. This algorithm augments the objective by a logarithmic penalty function and then solves a sequence of quadratic approximations of this program. This algorithms has a complexity of iterations and arithmetic operations, where m is a number of variables and L is the size of the problem encoding in binary. This algorithm does not require knowledge of the optimal value and generates a sequence of primal (Dual) feasible solutions that converges to an optimal primal (dual) solution (the latter property provides a particularly simple stopping criterion). Moreover, this algorithm is simple and intuitive, both in the description and in the analysis - in contrast to existing polynomial-time algorithms. It works exclusively in the original space. Keywords: Karmarkar methods; Quadratic approximation; Logarithmic penalty functions.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1988
Accession Number
ADA202502

Entities

People

  • Paul Tseng

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Arithmetic
  • Coding
  • Computer Programming
  • Control Systems
  • Convex Sets
  • Evolutionary Algorithms
  • Inequalities
  • Interdisciplinary Science
  • Linear Programming
  • Mathematical Analysis
  • Military Research
  • Notation
  • Polynomials
  • Sequences
  • Symbols

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Operations Research

Technology Areas

  • Space