The long-step method of analytic centers for fractional problems

The long-step method of analytic centers for fractional problems

0.00 Avg rating0 Votes
Article ID: iaor19981392
Country: Netherlands
Volume: 77
Issue: 2
Start Page Number: 191
End Page Number: 224
Publication Date: May 1997
Journal: Mathematical Programming
Authors:
Keywords: interior point methods
Abstract:

We develop a long-step surface-following version of the method of analytic centers for the fractional-linear problem min{t0 | t0B(x) – A(x) ∈ H, B(x) ∈ K, xG}, 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 mappings. Tracing a two-dimensional surface of analytic centers rather than the usual path of centers allows us 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 complexity bounds for the method and, at the same time, seems to be more attractive computationally than the short-step policy, which was previously the only one giving good complexity bounds.

Reviews

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