Expected Number of Steps of the Simplex Method for a Linear Program with a Convexity Constraint.

Abstract

When there is a convexity constraint, (Sigma)(lambda sub j) = 1, each iteration t of the simplex method provides a value z sub t for the objective and also a lower bound z sub t to w sub t. The paper studies (1) the expected behavior of (w sub t/w sub 0); (2) probability of termination on the t to th iteration; and (3) the expected number of steps, xi ITER, when the columns are drawn from a distribution from a three parameter class of distributions.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1980
Accession Number
ADA096130

Entities

People

  • George Bernard Dantzig

Organizations

  • Stanford University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Center Of Gravity
  • Convex Sets
  • Equations
  • Geometry
  • Heuristic Methods
  • Iterations
  • Linear Programming
  • Operations Research
  • Probability
  • Simplex Method
  • Statistical Samples
  • Systems Engineering
  • United States
  • United States Government

Readers

  • Graph Algorithms and Convex Optimization.
  • Pulsed Power and Plasma Physics.
  • Regression Analysis.