A Path-Following Full Newton-Step Infeasible Interior-Point Algorithm for $$P_*(\kappa )$$
- PDF / 523,192 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 82 Downloads / 157 Views
A Path-Following Full Newton-Step Infeasible Interior-Point Algorithm for P∗ (κ)-HLCPs Based on a Kernel Function Soodabeh Asadi1 · Hossein Mansouri1 · Maryam Zangiabadi1
Received: 31 July 2015 / Revised: 28 October 2015 / Accepted: 21 December 2015 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg 2016
Abstract In this paper, we present a path-following infeasible interior-point method for P∗ (κ) horizontal linear complementarity problems (P∗ (κ)-HLCPs). The algorithm is based on a simple kernel function for finding the search directions and defining the neighborhood of the central path. The algorithm follows the central path related to some perturbations of the original problem, using the so-called feasibility and centering steps, along with only full such steps. Therefore, it has the advantage that the calculation of the step sizes at each iteration is avoided. The complexity result shows that the full-Newton step infeasible interior-point algorithm based on the simple kernel function enjoys the best-known iteration complexity for P∗ (κ)-HLCPs. Keywords Horizontal linear complementarity problem · Infeasible interior-point method · Central path · Kernel function Mathematics Subject Classification
90C33 · 90C51
The authors were financially supported by Shahrekord Univeristy and also partially supported by the Center of Excellence for Mathematics, University of Shahrekord, Shahrekord, Iran.
B
Hossein Mansouri [email protected] Soodabeh Asadi [email protected] Maryam Zangiabadi [email protected]
1
Department of Applied Mathematics, Faculty of Mathematical Sciences, Shahrekord University, P.O. Box 115, Shahrekord, Iran
123
S. Asadi et al.
1 Introduction Given two n × n real matrices Q and R and a vector b in Rn where n 2. Consider the horizontal linear complementarity problem (HLCP): find a pair of vectors (x, s) ∈ R2n satisfying (P) : Qx + Rs = b,
(x, s) 0,
x T s = 0.
Linear complementarity problem (LCP) is obtained by taking R = −I . We say that HLCP is P∗ (κ) if Qu + Rv = 0 ⇒ u T v −4κ
u i vi ∀u, v ∈ Rn ,
(1.1)
i∈I +
where κ is a nonnegative constant and I + = {i : u i vi > 0} . If the above condition is satisfied, then we say that the pair (Q, R) is a P∗ (κ)-pair and write (Q, R) ∈ P∗ (κ). For κ = 0, P∗ (0)-HLCP is called the monotone HLCP. The P∗ (κ)-HLCP is a comprehensive problem containing linear programming (LP), LCP, and convex quadratic programming (CQP) as special cases. Therefore, handling this problem with an optimization method removes the necessity for dealing with many other ones. Interior-point methods (IPMs) that are initiated by Karmarkar [1] for LP play an important role in modern mathematical programming. They have been widely used to obtain strong theoretical results for solving other problems. In the past few years, there have been numerous proposals of interior-point algorithms for P∗ (κ)-HLCPs. Under certain assumptions, these algorithms can solve a given P∗ (κ)
Data Loading...
