Abstract
In this paper, we propose interior-point algorithms for \(P_* (\kappa )\)-linear complementarity problem based on a new class of kernel functions. New search directions and proximity measures are defined based on these functions. We show that if a strictly feasible starting point is available, then the new algorithm has \(\mathcal{O }\bigl ((1+2\kappa )\sqrt{n}\log n \log \frac{n\mu ^0}{\epsilon }\bigr )\) and \(\mathcal{O }\bigl ((1+2\kappa )\sqrt{n} \log \frac{n\mu ^0}{\epsilon }\bigr )\) iteration complexity for large- and small-update methods, respectively. These are the best known complexity results for such methods.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Amini, K., Haseli, A.: A new proximity function generating the best known iteration bounds for both large-update and small-update interior-point methods. ANZIAM J. 49, 259–270 (2007)
Amini, K., Peyghami, M.R.: Exploring complexity of large update interior-point methods for \(P_*(\kappa )\) linear complementarity problem based on kernel function. Appl. Math. Comput. 207, 501–513 (2009)
Bai, Y.Q., El Ghami, M., Roos, C.: A new efficient large-update primal-dual interior-point method based on a finite barrier. SIAM J. Optim. 13, 766–782 (2003)
Bai, Y.Q., El Ghami, M., Roos, C.: A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15, 101–128 (2004)
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, 19–41 (2008)
Cho, G.M.: A new large-update interior point algorithm for \(P_*(\kappa )\) linear complementarity problems. J. Comput. Appl. Math. 216, 256–278 (2008)
Cho, G.M., Kim, M.K.: A new large-update interior point algorithm for \(P_*(\kappa )\) LCPs based on kernel functions. Appl. Math. Comput. 182, 1169–1183 (2006)
Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, San Diego (1992)
Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, vol. 538. Lecture Notes in Computer Science. Springer, Berlin, Germany (1991)
Lesaja, G., Roos, C.: Unified analysis of kernel-based interior-point methods for \(P_*(\kappa )\)-linear complementarity problems. SIAM J. Optim. 20, 3014–3039 (2010)
Peng, J., Roos, C., Terlaky, T.: Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program. 93, 129–171 (2002)
Peng, J., Roos, C., Terlaky, T.: Primal-dual interior-point methods for second-order conic optimization based on self-regular proximities. SIAM J. Optim. 13, 179–203 (2002)
Peng, J., Roos, C., Terlaky, T.: Self-Regularity. A New Paradigm for Primal-dual Interior-Point Algorithms. Princeton University Press, Princeton (2002)
Roos, C., Terlaky, T.: Theory and Algorithms for Linear Optimization. An Interior Approach. Wiley, Chichester (1997)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education, Science and Technology (2011-0003133).
Rights and permissions
About this article
Cite this article
Lee, YH., Cho, YY. & Cho, GM. Interior-point algorithms for \(P_{*}(\kappa )\)-LCP based on a new class of kernel functions. J Glob Optim 58, 137–149 (2014). https://doi.org/10.1007/s10898-013-0072-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-013-0072-z