MODIFIED PREDICTOR-CORRECTOR ALGORITHM FOR LOCATING WEIGHTED CENTERS IN LINEAR-PROGRAMMING

被引:2
作者
ZHANG, Y
ELBAKRY, A
机构
[1] UNIV MARYLAND,CTR RES PARALLEL COMPUTAT,BALTIMORE,MD 21201
[2] RICE UNIV,DEPT MATH SCI,HOUSTON,TX 77251
关键词
PREDICTOR-CORRECTOR ALGORITHM; WEIGHTED CENTER OF THE SOLUTION SET; LINEAR PROGRAMMING;
D O I
10.1007/BF02192939
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
In certain applications of linear programming, the determination of a particular solution, the weighted center of the solution set, is often desired, giving rise to the need for algorithms capable of locating such center. In this paper, we modify the Mizuno-Todd-Ye predictor-corrector algorithm so that the modified algorithm is guaranteed to converge to the weighted center for given weights. The key idea is to ensure that iterates remain in a sequence of shrinking neighborhoods of the weighted central path. The modified algorithm also possesses polynomiality and superlinear convergence.
引用
收藏
页码:319 / 331
页数:13
相关论文
共 9 条
[1]  
Charnes A., 1991, J PROD ANAL, V2, P197, DOI [10.1007/BF00159732, DOI 10.1007/BF00159732]
[2]   PATH-FOLLOWING METHODS FOR LINEAR-PROGRAMMING [J].
GONZAGA, CC .
SIAM REVIEW, 1992, 34 (02) :167-224
[3]   ON APPROXIMATE SOLUTIONS OF SYSTEMS OF LINEAR INEQUALITIES [J].
HOFFMAN, AJ .
JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS, 1952, 49 (04) :263-265
[5]  
Megiddo N., 1989, PROGR MATH PROGRAMMI, P131, DOI DOI 10.1007/978-1-4613-9617-8_8
[6]  
MIZUNO S, 1990, 944 CORN U SCH ORIE
[7]  
THRALL RM, 1991, COMMUNICATION
[8]  
YE Y, 1991, TR9126 RIC U DEP MAT
[9]  
Zhang Y., 1991, TR9130 RIC U DEP MAT