A scaling technique for finding the weighted analytic center of a polytope

A scaling technique for finding the weighted analytic center of a polytope

0.00 Avg rating0 Votes
Article ID: iaor19931566
Country: Netherlands
Volume: 57
Issue: 2
Start Page Number: 163
End Page Number: 192
Publication Date: Nov 1992
Journal: Mathematical Programming
Authors: ,
Abstract:

Let a bounded full dimensional polytope be defined by the system equ1where A is an equ2matrix. Let equ3denote the ith row of the matrix A, and define the weighted analytic center of the polytope to be the point that minimizes the strictly convex barrier function equ4. The proper selection of weights equ5can 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 the authors assume that the weights are positive integers. If some of the equ6'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. The authors 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 equ7iterations, where m is the number of constraints defining the polytope and W 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.

Reviews

Required fields are marked *. Your email address will not be published.