A DUAL ALGORITHM FOR FINDING A NEAREST PAIR OF POINTS IN 2 POLYTOPES

被引：7

作者：

FUJISHIGE, S ^{[1
]}

ZHAN, P ^{[1
]}

机构：

[1] UNIV TSUKUBA,INST SOCIOECON PLANNING,TSUKUBA,IBARAKI 305,JAPAN

来源：

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN | 1992年 / 35卷 / 04期

关键词：

D O I：

10.15807/jorsj.35.353

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We propose a separating-hyperplane algorithm for finding a nearest pair of points in two polytopes, where each polytope is expressed as the convex hull of given points in a Euclidian space. The proposed algorithm is an extension of the authors dual algorithm for finding the minimum-norm point in a polytope.

引用

页码：353 / 365

页数：13

共 9 条

[1]

BARBOSA LC, 1967, 1ST P ANN PRINC C IN, P86

[2] A DUAL ALGORITHM FOR FINDING THE MINIMUM-NORM POINT IN A POLYTOPE [J].

FUJISHIGE, S ;

ZHAN, P .

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, 1990, 33 (02) :188-195

[3]

Fujishige S., 1991, ANN DISCRETE MATH, V47

[4] LINEARLY CONSTRAINED ESTIMATION BY MATHEMATICAL-PROGRAMMING [J].

KLAFSZKY, E ;

MAYER, J ;

TERLAKY, T .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1989, 42 (03) :254-267

[5]

Rockafellar R.T., 1970, CONVEX ANAL

[6]

SEKITANI K, IN PRESS MATH PROGRA

[7]

STOER J, 1970, CONVEXITY OPTIMIZATI, V1

[8]

TAKEHARA H, 1991, MTEC T911 WORK PAP

[9] FINDING NEAREST POINT IN A POLYTOPE [J].

WOLFE, P .

MATHEMATICAL PROGRAMMING, 1976, 11 (02) :128-149

← 1 →