Smallest point of a polytope

DOI10.1007/BF00939458MaRDI QIDQ1117135zbMATH OpenFDO

Authors Achiya Dax

Publication date 1990

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00939458

zbMATH Keywords

active set methodconvex hullfacility locationlarge sparse problemsleast-distance problemlinear least-squares problempoint of smallest Euclidean normrow relaxation

Mathematics Subject Classification ID

Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Inequalities and extremum problems involving convexity in convex geometry (52A40) Polytopes and polyhedra (52Bxx) Numerical mathematical programming methods (65K05) Inventory, storage, reservoirs (90B05)

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.

Recommendations

• An algorithm for finding the minimum-norm point in the intersection of a convex polyhedron and a hyperplane
• An algorithm for solving the minimum-norm point problem over the intersection of a polytope and an affine set
• scientific article; zbMATH DE number 125273
• Computing the vector in the convex hull of a finite set of points having minimal length
• A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes

Cites work

• A note on optimality conditions for the Euclidean. Multifacility location problem
• Extensions of Hildreth’s Row-Action Method for Quadratic Programming
• Finding the nearest point in A polytope
• Finding the Point of a Polyhedron Closest to the Origin
• scientific article; zbMATH DE number 3561096 (Why is no real title available?)
• Row-Action Methods for Huge and Sparse Systems and Their Applications
• Successive Refinement of Large Multicell Models

Cited in

(16)

• Efficient computation of nonparametric survival functions via a hierarchical mixture formulation
• Modelling of count data using nonparametric mixtures
• Least squares estimation of a \(k\)-monotone density function
• A mixture model-based nonparametric approach to estimating a count distribution
• Minimum quadratic distance density estimation using nonparametric mixtures
• Fisher scoring: an interpolation family and its Monte Carlo implementations
• The distance between two convex sets
• Small min-cut polyhedra
• scientific article; zbMATH DE number 1342076 (Why is no real title available?)
• scientific article; zbMATH DE number 2102029 (Why is no real title available?)
• scientific article; zbMATH DE number 7583739 (Why is no real title available?)
• Density estimation using non-parametric and semi-parametric mixtures
• The least squares point of a quadrilateral
• scientific article; zbMATH DE number 5264906 (Why is no real title available?)
• Nonparametric multivariate density estimation using mixtures
• A nonparametric mixture approach to density and null proportion estimation in large‐scale multiple comparison problems

This page was built for publication: Smallest point of a polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1117135)