A DUAL ALGORITHM FOR FINDING THE MINIMUM-NORM POINT IN A POLYTOPE

• Fujishige Satoru

  Institute of Socio-Economic Planning, University of Tsukuba

• Zhan Ping

  Institute of Socio-Economic Planning, University of Tsukuba

Abstract

We 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. Our 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 our algorithm.

Journal

• Journal of the Operations Research Society of Japan

  Journal of the Operations Research Society of Japan 33 (2), 188-195, 1990

  The Operations Research Society of Japan

Keywords

• Management Science and Operations Research
• General Decision Sciences

Details

• CRID: 1390282679087494400
• NII Article ID: 110001184304
• DOI: 10.15807/jorsj.33.188
• ISSN: 21888299
• ISSN: 04534514
• Web Site: https://www.jstage.jst.go.jp/article/jorsj/33/2/33_KJ00001202729/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
• Abstract License Flag: Disallowed