Variable Metric Relaxation Methods. Part I. A Conceptual Algorithm.

Abstract

A variable metric, maximal ellipsoidal distance, relaxation method for solving systems of linear, inequalities is described and its rate of convergence analyzed. This algorithm, with a termination routine appended to it, is polynomial if the ellipsoid matrix approximates an inverse 'Hessian,' which may be defined through the largest ellipsoid contained in a perturbation cum compactification of the feasible set. This so called inverse Hessian is given by a positive linear combination of symmetric rank one matrices built on the vectors given by the facets of the perturbation cum compactification of the feasible set. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1981
Accession Number
ADA107461

Entities

People

  • Jean-louis Goffin

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Convergence
  • Convex Sets
  • Ellipsoids
  • Inequalities
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Numbers
  • Numerical Analysis
  • Operations Research
  • Optimization
  • Perturbations
  • Polynomials
  • Simplex Method
  • Theorems

Fields of Study

  • Mathematics

Readers

  • Computational Modeling and Simulation
  • Electromagnetic Wave Scattering and Antenna Radiation Engineering
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)