A wide neighborhood predictor-infeasible corrector interior-point algorithm for linear optimization
- PDF / 298,767 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 13 Downloads / 179 Views
A wide neighborhood predictor-infeasible corrector interior-point algorithm for linear optimization B. Kheirfam1 · A. Nasrollahi1 Received: 25 February 2019 / Accepted: 21 March 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract In this paper, we propose a theoretical framework of a predictor-corrector interior-point method for linear optimization based on the one-norm wide neighborhood of the central path, focusing on infeasible corrector steps. Here, we call the predictor-infeasible corrector algorithm. At each iteration, the proposed algorithm computes an infeasible corrector step in addition to the Ai-Zhang search directions and considers the Newton direction as a linear combination of these directions. We represent the complexity analysis of the algorithm and conclude that its iteration bound is O(n log ε−1 ). To our knowledge, this is the best complexity result up to now for infeasible interior-point methods based on these kinds of search directions. The complexity bound obtained here is the same as small neighborhood infeasible interior point algorithms. Keywords Linear optimization · Wide neighborhood · Predictor-corrector methods · Infeasible interior-point methods · Polynomial complexity
1 Introduction After the landmark paper of Karmarkar [6] for linear optimization (LO), interiorpoint methods (IPMs) become an active area of research. After decades, introducing a polynomial-time IPM with the best theoretical complexity results is yet the main challenge in this area of research. In order to see the desirable results in this field, we refer the reader to the books of Roos et al. [21], Wright [23] and Ye [26]. However, the IPMs can be classified in a variety of ways: the primal-dual path-following, affine scaling methods, potential reduction methods and etc. Meanwhile, path-following methods are of particular importance. These consider a target point on the central
B
B. Kheirfam [email protected] A. Nasrollahi [email protected]
1
Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, Iran
123
B. Kheirfam, A. Nasrollahi
path and use Newton’s method to closer to target at each iteration, while limiting each iterate to stay within a special neighborhood of the central path. In this case, we can talk about various types of these methods according to the choice of the step length, such as short-update methods, long-update methods and predictor-corrector methods. For a comprehensive study, we refer to the book of Wright [23]. The shortupdate methods, the so-called small-neighborhood algorithms, have the best iteration complexity in theory, while the large neighborhood algorithms are better in practice. Thus, it turns out that there is a vacuum between theory and practice. Peng et al. [18] the first used self-regular functions in order to reduce this gap. Predictor-corrector path-following methods play a special role among IPMs. The first l2 -neighborhood predictor-corrector algorithm was proposed by Sonnevend et al. [22], which included a predict
Data Loading...
