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

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Fujishige Satoru

  Institute of Policy and Planning Sciences University of Tsukuba

• Fujishige Satoru

  Institute Of Socio-economic Planning University Of Tsukuba

• Fujishige S

  Division Of Systems Science Department Of Systems And Human Science Graduate School Of Enginecring S

• Zhan P

  Edogawa Univ.

• Zhan Ping

  Institute of Socio-Economic Planning, University of Tsukuba

• Zhan Ping

  Institute Of Socio-economic Planning University Of Tsukuba

関連論文

• THE MINIMUM-WEIGHT IDEAL PROBLEM FOR SIGNED POSETS
• A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER A FINITE JUMP SYSTEM
• An Almost-Linear-Time Algorithm for Solving the Graph-Realization Problem (Graphs and Combinatorics III)
• A DUAL ALGORITHM FOR FINDING THE MINIMUM-NORM POINT IN A POLYTOPE
• A DUAL ALGORITHM FOR FINDING A NEAREST PAIR OF POINTS IN TWO POLYTOPES
• AN EFFICIENT COST SCALING ALGORITHM FOR THE INDEPENDENT ASSIGNMENT PROBLEM

スポンサーリンク