A wide neighborhood interior-point algorithm based on the trigonometric kernel function
- PDF / 312,064 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 64 Downloads / 172 Views
A wide neighborhood interior-point algorithm based on the trigonometric kernel function B. Kheirfam1 · M. Haghighi1 Received: 4 February 2020 © Korean Society for Informatics and Computational Applied Mathematics 2020
Abstract In this paper, a wide neighborhood path-following interior point algorithm for linear optimization (LO) is proposed that uses a trigonometric kernel function to get search directions. The method treats the Newton direction as the sum of two other directions, according to the negative and positive parts of the right-hand-side based on the kernel function. By choosing different and appropriate step sizes for these two directions, the iterates stop in the Ai–Zhang’s wide neighborhood. By an elegant analysis, we show 0 T 0 √ that the method enjoys the low iteration bound of O( n log (x )ε s ), where n is the dimension of the problem and (x 0 , s 0 ) the initial interior point with ε the required precision. In our knowledge, this result is the first instance of a wide neighborhood interior point method for LO which involving the trigonometric kernel function. Keywords Linear optimization · Wide neighborhood · Kernel function · Interior-point method · Polynomial complexity Mathematics Subject Classification 90C05 · 90C51
1 Introduction Interior Point Methods (IPMs) which initiated activity after the landmark paper of Karmarkar [6] not only have provided polynomial time algorithms but are also more efficient in practical problems. Several efficient IPMs for solving LO and a large number of results have been proposed in [18,20,22]. A fundamental notion in the literature of IPMs is the central path that has been introduced independently by Sonnevend [19] and by Megiddo [15]. Kojima et al. [11] used Megiddo’s idea to present a primal-
B
B. Kheirfam [email protected] M. Haghighi [email protected]
1
Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, Iran
123
B. Kheirfam, M. Haghighi
dual√algorithm that traces the central path. Path-following IPM with a complexity of O( n L)-iteration was first proposed by Kojima et al. [12]. These methods use different strategies to track the central path. Two different approaches in the analysis and implementation of IPMs are the so-called small-update and large-update methods. The essential feature of the large-update methods is that work in a wide neighborhood of the central path, while the short-update versions generate the new iterates of the algorithm in a smaller neighborhood. However, it turned out that there is a gap between the theory and the practical performance of primal-dual path-following methods concerning these two strategies; small-update methods work very poor in practice but have the best theoretical iteration bound, while the large-update methods have weaker theoretical results but perform much better in practical problems. Many researchers have tried to reduce this gap. The first attempt in this regard is related to Peng et al. [16]. They used the so-called self-regular barrier function instead of the
Data Loading...
