A Polynomial Interior-Point Algorithm for Monotone Linear Complementarity Problems
- PDF / 414,620 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 83 Downloads / 211 Views
A Polynomial Interior-Point Algorithm for Monotone Linear Complementarity Problems H. Mansouri · M. Pirhaji
Received: 28 May 2012 / Accepted: 22 September 2012 / Published online: 11 October 2012 © Springer Science+Business Media New York 2012
Abstract In this paper, we propose an interior-point algorithm for monotone linear complementarity problems. The algorithm is based on a new technique for finding the search direction and the strategy of the central path. At each iteration, we use only full-Newton steps. Moreover, it is proven that the number of iterations of the algorithm coincides with the well-known best iteration bound for monotone linear complementarity problems. Keywords Monotone linear complementarity problem (MLCP) · Feasible interior-point method · Central path · Polynomial complexity 1 Introduction After the seminal work of Karmarkar [1], many researchers have proposed interiorpoint methods (IPMs) for linear optimization, convex quadratic optimization, linear complementarity problems and sufficient linear complementarity problems and achieved plentiful results [2–7]. It should be noted that most of the polynomial time IPMs use the so-called central path as a guideline to the optimal set, while some other versions of the well-known Newton method follow the central path approximately. Recently, Peng et al. [5, 8] introduced a class of primal–dual IPMs based on so-called self-regular functions for linear optimization (LO) and monotone linear complementarity problem (MLCP). The complexity bound obtained by these authors Communicated by Nobuo Yamashita. H. Mansouri () · M. Pirhaji Department of Applied Mathematics, Faculty of Mathematical Sciences, Shahrekord University, P.O. Box 115, Shahrekord, Iran e-mail: [email protected] M. Pirhaji e-mail: [email protected]
452
J Optim Theory Appl (2013) 157:451–461
is the best known iteration bound for MLCP. In very recently, Mansouri et al. [9, 10] presented the first full-Newton step infeasible IPM (IIPM) for MLCPs, which is an extension of the work for linear optimization [11–13]. In this paper, we present a new feasible IPM with full-Newton steps for MLCP. We prove that the complexity of our algorithm coincides with the best known iteration bound for feasible IPMs. The paper is organized as follows: in Sect. 2, we recall some tools in the analysis of a feasible IPM and we introduce the new search directions for MLCP. In Sect. 3, we present a new algorithm for solving linear complementarity problems. We will derive a complexity bound for our algorithm in Sect. 4. In Sect. 5, some numerical tests are presented to demonstrate the effectiveness and efficiency of the proposed algorithm. Finally, some concluding remarks follow in Sect. 6.
2 Preliminaries In this section, we first introduce some notations used all along this paper. Scalars and indices are denoted by lowercase Latin letters, vectors by lowercase boldface Latin letters, matrices by capital Latin letters, and sets by capital calligraphic letters. Rn+ (Rn++ ) is the non-negative (positi
Data Loading...
