Abstract
In this paper, a full-Newton step feasible interior-point algorithm is proposed for solving \(P_*(\kappa )\)-linear complementarity problems. We prove that the full-Newton step to the central path is local quadratically convergent and the proposed algorithm has polynomial iteration complexity, namely, \(O\left( (1+4\kappa )\sqrt{n}\log {\frac{n}{\varepsilon }}\right) \), which matches the currently best known iteration bound for \(P_*(\kappa )\)-linear complementarity problems. Some preliminary numerical results are provided to demonstrate the computational performance of the proposed algorithm.
Similar content being viewed by others
References
Bai, Y.Q., Lesaja, G., Roos, C.: A new class of polynomial interior-point algorithms for \(P_*(\kappa )\) linear complementarity problems. Pac. J. Optim. 4(1), 19–41 (2008)
Cho, G., Kim, M.: A new large-update interior point algorithm for \(P_*(\kappa )\)-LCPs based on kernel functions. Appl. Math. Comput. 182(1), 1169–1183 (2006)
Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, Boston (1992)
de Klerk, E.: Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Kluwer, Dordrecht (2002)
Fathi, Y.: Computational complexity of LCPs associated with positive definite matrices. Math. Program. 17(1), 335–344 (1979)
Gurtuna, F., Petra, C., Potra, F.A., Olena Shevchenko, O., Vancea, A.: Corrector-predictor methods for sufficient linear complementarity problems. Comput. Optim. Appl. 48(3), 453–485 (2011)
Illés, T., Nagy, M.: A Mizuno-Todd-Ye type predictor corrector algorithm for sufficient linear complementarity problems. Eur. J. Oper. Res. 181(3), 1097–1111 (2007)
Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity problems. Lecture Notes in Computer Science 538. Springer, New York (1991)
Lesaja, G., Roos, C.: Unified analysis of kernel-based interior-point methods for \(P_*(\kappa )\)-linear complementarity problems. SIAM J. Optim. 20(6), 3014–3039 (2010)
Liu, X., Potra, F.A.: Corrector-predictor methods for sufficient linear complementarity problems in a wide neighborhood of the central path. SIAM J. Optim. 17(3), 871–890 (2006)
Liu, H.W., Liu, X.Z., Liu, C.H.: Mehrotra-type predictor-corrector algorithms for sufficient linear complementarity problem. Appl. Numer. Math. 62(12), 1685–1700 (2012)
Miao, J.: A quadratically convergent \(O((1+\kappa )\sqrt{n}L)\)-iteration algorithm for the \(P_*(\kappa )\)-matrix linear complementarity problem. Math. Program. 69(1–3), 355–368 (1995)
Murty, K.G.: Linear Complementarity, Linear and Nonlinear Programming. Helderman-Verlag, Berlin (1988)
Peng, J., Roos, C., Terlaky, T.: Self-regular proximities and new search directions for nonlinear \(P_*\) complementarity problems. Technical Report, Faculty of Technical Mathematics and Informatics, Delft University of Technology, The Netherlands (2000)
Potra, F.A., Sheng, R.Q.: Predictor-corrector algorithms for solving \(P_*(\kappa )\)-matrix LCP from arbitrary positive starting points. Math. Program. 76(1), 223–244 (1996)
Potra, F.A., Sheng, R.Q.: A large-step infeasible-interior-point method for the \(P_*\)-matrix LCP. SIAM J. Optim. 7(2), 318–335 (1997)
Potra, F.A., Liu, X.: Predictor-corrector methods for sufficient linear complementarity problems in a wide neighborhood of the central path. Optim. Methods Softw. 20(1), 145–168 (2005)
Potra, F.A., Stoer, J.: On a class of superlinearly convergent polynomial time interior point methods for sufficient LCP. SIAM J. Optim. 20(3), 1333–1363 (2009)
Roos, C., Terlaky, T., Vial, J-Ph: Theory and Algorithms for Linear Optimization. An Interior-Point Approach. Wiley, Chichester (1997)
Roos, C.: A full-Newton step \(O(n)\) infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16(4), 1110–1136 (2006)
Vliaho, H.: \(P_*\)-matrices are just sufficient. Linear Algebra Appl. 239, 103–108 (1996)
Wang, G.Q., Bai, Y.Q.: Polynomial interior-point algorithms for \(P_*(\kappa )\) horizontal linear complementarity problem. J. Comput. Appl. Math. 233(2), 248–263 (2009)
Watson, L.T.: Solving the nonlinear complementarity problem by a homotopy method. SIAM J. Optim. 17(1), 36–46 (1979)
Ye, Y.: On homogeneous and self-dual algorithm for LCP. Math. Program. 76(1), 211–222 (1997)
Ye, Y.: Interior Point Algorithms, Theory and Analysis. Wiley, Chichester (1997)
Zhao, Y.B., Han, J.Y.: Two interior-point methods for nonlinear \(P_*(\tau )\)-complementarity problems. J. Optim. Theory Appl. 102(3), 659–679 (1999)
Zhao, Y.B., Li, D.: A globally and locally convergent non-interior-point algorithm for \(P_0\) LCPs. SIAM J. Optim. 13(4), 1195–1221 (2003)
Zhao, Y.B.: A new path-following algorithm for nonlinear \(P_*\) complementarity problems. Comput. Optim. Appl. 34(2), 183–214 (2005)
Acknowledgments
The authors would like to thank the referees for their useful suggestions which improve the presentation of this paper. This research was supported by National Natural Science Foundation of China (No. 11001169), China Postdoctoral Science Foundation funded project (Nos. 2012T50427, 20100480604), Research Grant of Shanghai University of Engineering Science (No. 2013–21), Connotative Construction Project of Shanghai University of Engineering Science (No. NHKY-2012–13), and a Discovery Grant from the Australian Research Council.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, G.Q., Yu, C.J. & Teo, K.L. A full-Newton step feasible interior-point algorithm for \(P_*(\kappa )\)-linear complementarity problems. J Glob Optim 59, 81–99 (2014). https://doi.org/10.1007/s10898-013-0090-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-013-0090-x