The long-step method of analytic centers for fractional problems |
| |
Authors: | A. Nemirovski |
| |
Affiliation: | (1) Faculty of Industrial Engineering and Management, Technion — The Israel Institute of Technology, 3200 Technion City, Haifa, Israel |
| |
Abstract: | We develop a long-step surface-following version of the method of analytic centers for the fractional-linear problem min{t 0 |t 0 B(x) −A(x) εH, B(x) εK, x εG}, whereH is a closed convex domain,K is a convex cone contained in the recessive cone ofH, G is a convex domain andB(·),A(·) are affine mappings. 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 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. The research was partly supported by the Israeli-American Binational Science Foundation (BSF). |
| |
Keywords: | Fractional programming Generalized eigenvalue problem Interior point methods Analytic centers |
本文献已被 SpringerLink 等数据库收录! |
|