tailieunhanh - A full-newton step infeasible-interior-point algorithm for P*(K)-horizontal linear complementarity problems

In this paper we generalize an infeasible interior-point method for linear optimization to horizontal linear complementarity problem (HLCP). This algorithm starts from strictly feasible iterates on the central path of a perturbed problem that is produced by suitable perturbation in HLCP problem. Then, we use so-called feasibility steps that serves to generate strictly feasible iterates for the next perturbed problem. | Yugoslav Journal of Operations Research 25 (2015), Number 1, 57–72 DOI: A FULL-NEWTON STEP INFEASIBLE-INTERIOR-POINT ALGORITHM FOR P ∗ (κ)-HORIZONTAL LINEAR COMPLEMENTARITY PROBLEMS Soodabeh ASADI Department of Applied Mathematics, Shahrekord University, Faculty of Mathematical Sciences, . Box 115, Shahrekord, Iran. sudabeasadi@ Hossein MANSOURI Department of Applied Mathematics, Shahrekord University, Faculty of Mathematical Sciences, . Box 115, Shahrekord, Iran. Mansouri@ Received: May 2013 / Accepted: August 2013 Abstract: In this paper we generalize an infeasible interior-point method for linear optimization to horizontal linear complementarity problem (HLCP). This algorithm starts from strictly feasible iterates on the central path of a perturbed problem that is produced by suitable perturbation in HLCP problem. Then, we use so-called feasibility steps that serves to generate strictly feasible iterates for the next perturbed problem. After accomplishing a few centering steps for the new perturbed problem, we obtain strictly feasible iterates close enough to the central path of the new perturbed problem. The complexity of the algorithm coincides with the best known iteration complexity for infeasible interiorpoint methods. Keywords: Horizontal Linear Complementarity Problem (HLCP), Infeasible-interiorpoint Method, Central Path. MSC: 90C33, 90C51. 1. INTRODUCTION This paper deals with the solution of the horizontal linear complementarity 58 S. Asadi, H. Mansouri / A Full-Newton Step problem (HLCP) that consists in finding a pair of vectors (x, s) ∈ R2n satisfying Qx + Rs = b, (x, s) ≥ 0, xT s = 0, (P ) where b is in Rn , Q and R are real n × n matrices. The standard (monotone) linear complementarity problem (LCP) is obtained by taking R = −I and Q positive semidefinite. There are other formulations of the HLCP as well, but, as shown in [1], all popular formulations are equivalent, and the behavior of

• Toán học
• Horizontal linear complementarity problem (HLCP)
• Infeasible interiorpoint method
• Central path
• Horizontal linear