THE LONG-STEP METHOD OF ANALYTIC CENTERS FOR FRACTIONAL PROBLEMS

We develop a long-step surface-following version of the method of anal ytic centers for the fractional-linear problem min{to \ t(0)B(x) - A(x ) is an element of H, B(x) is an element of K, x is an element of G}, where H is a closed convex domain, K is a convex cone contained in the recessive cone of H, G is a convex domain and B(.), A(.) are affine m appings. Tracing a two-dimensional surface of analytic centers rather than the usual path of centers allows to skip the initial ''centering' ' phase of the path-following scheme. The proposed long-step policy of tracing the surface fits the best known overall polynomial-time compl exity bounds for the method and, at the same time, seems to be more at tractive computationally than the short-step policy, which was previou sly the only one giving good complexity bounds. (C) 1997 The Mathemati cal Programming Society, Inc. Published by Elsevier Science B.V.