Effective computation of the analytic center of the solution set in linear programming using primal-dual interior-point methods

[摘要] The centrality property satisfied by the analytic center of the solution set makes its computation very valuable for some linear programming applications. One such application coming from the economic and management sciences is Data Envelopment Analysis (DEA). In DEA one desires a solution of the underlying linear programming model that is in the relative interior of the solution set and one that is in some sense as far away as possible from the relative boundary. In this way the solution is robust and not affected by small changes in the data. In this work we study the effective computation of the analytic center solution by the use of primal-dual interior-point methods. We present a unified study of existing theoretical results for primal-dual interior-point algorithms as they concern the convergence of the iteration sequence and the convergence of the iteration sequence to the analytic center. These theoretical results are evaluated from the point of view of the practical computation of the analytic center. We propose a primal-dual interior-point algorithm for effectively computing the analytic center of the solution set. The algorithm proposed combines good theoretical and numerical properties and its ability to solve real world problems from the DEA application is demonstrated.

[发布机构] Rice University

[效力级别] Operations