Abstract
Let a bounded full dimensional polytope be defined by the systemAx ⩾b whereA is anm × n matrix. Leta i denote theith row of the matrixA, and define theweighted analytic center of the polytope to be the point that minimizes the strictly convex barrier function −∑ mi=1 w i ln(a Ti x −b i ). The proper selection of weightsw i can make any desired point in the interior of the polytope become the weighted analytic center. As a result, the weighted analytic center has applications in both linear and general convex programming. For simplicity we assume that the weights are positive integers.
If some of thew i 's are much larger than others, then Newton's method for minimizing the resulting barrier function is very unstable and can be very slow. Previous methods for finding the weighted analytic center relied upon a rather direct application of Newton's method potentially resulting in very slow global convergence. We present a method for finding the weighted analytic center that is based on the scaling technique of Edmonds and Karp and is an enhancement of Newton's method. The scaling algorithm runs in\(O(\sqrt m \log W)\) iterations, wherem is the number of constraints defining the polytope andW is the largest weight given on any constraint. Each iteration involves taking a step in the Newton direction and its complexity is dominated by the time needed to solve a system of linear equations.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. Edmonds and R.M. Karp, “Theoretical improvements in algorithmic efficiency for network flow problems,”Journal of the ACM 19 (1972) 248–264.
R. Freund, “Projective transformations for interior-point algorithms, and a superlinearly convergent algorithm for the w-center problem,” Working Paper, Alfred P. Sloan School of Management, MIT (Cambridge, MA, 1989).
R. Freund and K. Tan, “A method for the parametric center problem, with a strictly monotone polynomial-time algorithm for linear programming,” to appear in:Mathematics of Operations Research.
H.N. Gabow, “Scaling algorithms for network problems,”Journal of Computer and System Sciences 31 (1985) 148–168.
C. Gonzaga, “An algorithm for solving linear programming problems in O(n 3 L) operations,” in: N. Megiddo, ed.,Progress in Mathematical Programming: Interior Point and Related Methods (Springer, Berlin, 1989) pp. 1–28.
M. Grötschel, L. Lovász and A. Schrijver,Geometric Algorithms and Combinatorial Optimization (Springer, Berlin, 1988).
N. Karmarkar, “A new polynomial time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
Y. Nesterov and A. Nemirovsky, “Self-concordant functions and polynomial time methods in convex programming,” manuscript, USSR Academy of Sciences (Moscow, 1989).
J. Renegar, “A polynomial-time algorithm, based on Newton's method, for linear programming,”Mathematical Programming 40 (1988) 59–93.
G. Sonnevend, “An analytic center for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming,” preprint, Department of Numerical Analysis, Institute of Mathematics, Eötvös University (Budapest, 1989).
K. Tan and R. Freund, “Newton's method for the general parametric center problem with applications,” Technical Report No. 457, Department of Mathematics, National University of Singapore (Singapore, 1991).
P. Vaidya, “An algorithm for linear programming which requires O(((m+n)n 2+(m+n) 1.5 n)L) arithmetic operations,”Mathematical Programming 47 (1990) 175–201.
P. Vaidya, “A new algorithm for minimizing convex functions over convex sets,” in:Proceedings of 30th Annual IEEE Symposium on Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1989) pp. 338–343, to appear in:Mathematical Programming.
P. Vaidya, “A locally well-behaved potential function and a simple Newton-type method for finding the center of a polytope,” in: N. Megiddo, ed.,Progress in Mathematical Programming: Interior Point and Related Methods (Springer, Berlin, 1989) pp. 81–90.
Author information
Authors and Affiliations
Additional information
Supported by the Campus Research Board, University of Illinois at Urbana-Champaign.
Supported by the National Science Foundation under Grants CCR-9057481 and CCR-9007195.
Rights and permissions
About this article
Cite this article
Atkinson, D.S., Vaidya, P.M. A scaling technique for finding the weighted analytic center of a polytope. Mathematical Programming 57, 163–192 (1992). https://doi.org/10.1007/BF01581079
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01581079