Smallest point of a polytope
type: Item
instance of: scholarly article
title: Smallest point of a polytope
zbMATH Open document ID: 0666.90031
DOI: 10.1007/BF00939458
author: Achiya Dax
published in: Journal of Optimization Theory and Applications
publication date: 1990-01-01T00:00:00Z
review text: This note suggests new ways for calculating the point of smallest Euclidean norm in the convex hull of a given set of points in \(R^ n\). It is shown that the problem can be formulated as a linear least-squares problem with nonnegative variables or as a least-distance problem. Numerical experiments illustrate that the least-squares problem is solved efficiently by the active set method. The advantage of the new approach lies in the solution of large sparse problems. In this case, the new formulation permits the use of row relaxation methods. In particular, the least-distance problem can be solved by Hildreth's method.
Mathematics Subject Classification ID: 90B05
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 52A40
Mathematics Subject Classification ID: 52A20
Mathematics Subject Classification ID: 52Bxx
zbMATH DE Number: 4091161
zbMATH Keywords: facility location
zbMATH Keywords: point of smallest Euclidean norm
zbMATH Keywords: convex hull
zbMATH Keywords: linear least-squares problem
zbMATH Keywords: least-distance problem
zbMATH Keywords: active set method
zbMATH Keywords: large sparse problems
zbMATH Keywords: row relaxation
MaRDI profile type: Publication
cites work: Q4132018
cites work: Finding the nearest point in A polytope
cites work: Finding the Point of a Polyhedron Closest to the Origin
cites work: Successive Refinement of Large Multicell Models
cites work: A note on optimality conditions for the Euclidean. Multifacility location problem
cites work: Extensions of Hildreth’s Row-Action Method for Quadratic Programming
cites work: Row-Action Methods for Huge and Sparse Systems and Their Applications
description: scientific article; zbMATH DE number 4091161