A dual algorithm for finding the minimum-norm point in a polytope

A dual algorithm for finding the minimum-norm point in a polytope

0.00 Avg rating0 Votes
Article ID: iaor19921165
Country: Japan
Volume: 33
Issue: 2
Start Page Number: 188
End Page Number: 195
Publication Date: Jun 1990
Journal: Journal of the Operations Research Society of Japan
Authors: ,
Keywords: programming: convex, programming: quadratic
Abstract:

The authors give a dual algorithm for the problem of finding the minimum-norm point in the convex hull of a given finite set of points in a Euclidean space. The present algorithm repeatedly rotates a separating supporting-hyperplane and in finitely many steps finds the farthest separating supporting-hyperplane, whose minimum-norm point is the desired minimum-norm point in the polytope. During the execution of the algorithm the distance of the separating supporting-hyperplane monotonically increases. The algorithm is closely related to P. Wolfe’s primal algorithm which finds a sequence of norm-decreasing points in the given polytope. Computational experiments are carried out to show the behavior of the present algorithm.

Reviews

Required fields are marked *. Your email address will not be published.