Complexity of Full-Newton Step Algorithm for Linear Complementarity Problem
In this paper, we analyze the effect of making equivalent transformations for the central path from \( xs=\mu e \) to \( xs=\mu v \) , so we obtain a new search direction. For a full-Newton step interior-point algorithm based on this search direction, we
- PDF / 92,291 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 12 Downloads / 193 Views
Complexity of Full-Newton Step Algorithm for Linear Complementarity Problem Xiaoyu Gong, Zhenpeng Hu, and Xianjia Wang
Abstract In this paper, we analyze the effect of making equivalent transformations for the central path from xs ¼ μe to xs ¼ μv, so we obtain a new search direction. For a full-Newton step interior-point algorithm based on this search direction, pffiffiffi we have the best known complexity bound is Oð n lon ε=nÞ . Which coincides with the best known iteration bound for feasible interior-point method(IPM). Finally, we concentrate on its numerical implementation where a strategy on the update barrier parameter is made for its numerical performances. Keywords Interior-point algorithm • Full-Newton step • Linear complementarity problem • Central path complexity analysis
160.1
Introduction
In this paper, we consider the following linear complementarity problem (LCP): s ¼ Mx þ q, xT s ¼ 0, ðx; sÞ 0
(P)
where q 2 Rn and M is an n n matrix supposed positive semi-definite. Complementarity is ubiquitous in the natural and social sciences. In a primal-dual X. Gong (*) School of Water Resources and Hydropower, Wuhan University, Wuhan 430072, China College of Science, Guangdong University of Petrochemical Technology, Maoming 525000, China e-mail: [email protected] Z. Hu School of Water Resources and Hydropower, Wuhan University, Wuhan 430072, China X. Wang School of Political Science and Public Management, Wuhan University, Wuhan 430072, China S. Zhong (ed.), Proceedings of the 2012 International Conference on Cybernetics 1255 and Informatics, Lecture Notes in Electrical Engineering 163, DOI 10.1007/978-1-4614-3872-4_160, # Springer Science+Business Media New York 2013
1256
X. Gong et al.
description of a system, it means that either the primal or the corresponding dual component of the solution vector must vanish. It is a fundamental principle underlying equilibrium. There are many problems that can be naturally modeled as complementarity problems. Applications of complementarity problems are prevalent, especially in economics and engineering. A major source of complementarity problems arises from the optimality conditions of general constrained optimization problems. In particular, linear programming (LP) and convex quadratic programming (QP) can be written as linear complementarity problems. The linear complementarity problem(LCP) has played an important unifying role in operations research since its introduction more than three decades ago [1], For example, interior-point methods(IPMs) initially developed for linear programming have been generalized early on to linear complementarity problems and has been successful in many cases [2–4]. In this paper, we present a new feasible primal-dual IPM with full-Newton step pffiffiffi for LCP and prove the complexity of our algorithm is Oð n lon ε=nÞ . Which coincides with the best known iteration bound for feasible IPMs [5]. Finally, we concentrate on its numerical implementation where a strategy on the update barrier parameter is made for its numerical performances
Data Loading...
