{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T20:23:48Z","timestamp":1773347028259,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T00:00:00Z","timestamp":1686268800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T00:00:00Z","timestamp":1686268800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Ministry of Culture and Innovation of Hungary from the National Research, Development and Innovation Fund","award":["PD_22, nr. 142154"],"award-info":[{"award-number":["PD_22, nr. 142154"]}]},{"name":"Ministry for Culture and Innovation from the source of the National Research, Development and Innovation","award":["\u00daNKP-22-4"],"award-info":[{"award-number":["\u00daNKP-22-4"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose new short-step interior-point algorithms (IPAs) for solving <jats:inline-formula><jats:alternatives><jats:tex-math>$$P_*(\\kappa )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>P<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mrow\/>\n                        <mml:mo>\u2217<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>\u03ba<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-linear complementarity problems (LCPs). In order to define the search directions, we use the algebraic equivalent transformation (AET) technique of the system describing the central path. A novelty of the paper is that we introduce a whole, new class of AET functions for which a unified complexity analysis of the IPAs is presented. This class of functions differs from the ones used in the literature for determining search directions, like the class of concave functions determined by Haddou, Migot and Omer, self-regular functions, eligible kernel and self-concordant functions. We prove that the IPAs using any member <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varphi $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c6<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of the new class of AET functions have polynomial iteration complexity in the size of the problem, in starting point\u2019s duality gap, in the accuracy parameter and in the parameter <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\kappa $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03ba<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s10957-023-02232-1","type":"journal-article","created":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T20:29:39Z","timestamp":1686342579000},"page":"27-49","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Unified Approach of Interior-Point Algorithms for $$P_*(\\kappa )$$-LCPs Using a New Class of Algebraically Equivalent Transformations"],"prefix":"10.1007","volume":"202","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8789-6211","authenticated-orcid":false,"given":"Tibor","family":"Ill\u00e9s","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3867-0304","authenticated-orcid":false,"given":"Petra Ren\u00e1ta","family":"Rig\u00f3","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roland","family":"T\u00f6r\u00f6k","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,6,9]]},"reference":[{"key":"2232_CR1","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1080\/10556788.2020.1734803","volume":"3","author":"S Asadi","year":"2022","unstructured":"Asadi, S., Mahdavi-Amiri, N., Darvay, Z., Rig\u00f3, P.R.: Full-NT step feasible interior-point algorithm for symmetric cone horizontal linear complementarity problem based on a positive-asymptotic barrier function. Optim. Methods Softw. 3, 192\u2013213 (2022)","journal-title":"Optim. Methods Softw."},{"key":"2232_CR2","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/s11075-012-9628-0","volume":"63","author":"S Asadi","year":"2013","unstructured":"Asadi, S., Mansouri, H.: Polynomial interior-point algorithm for $${P}_*(\\kappa )$$ horizontal linear complementarity problems. Numer. Algorithms 63, 385\u2013398 (2013)","journal-title":"Numer. Algorithms"},{"key":"2232_CR3","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1137\/S1052623403423114","volume":"15","author":"YQ Bai","year":"2004","unstructured":"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\u2013128 (2004)","journal-title":"SIAM J. Optim."},{"key":"2232_CR4","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/BF00940344","volume":"60","author":"S-J Chung","year":"1989","unstructured":"Chung, S.-J.: NP-completeness of the linear complementarity problem. J. Optim. Theory Appl. 60, 393\u2013399 (1989)","journal-title":"J. Optim. Theory Appl."},{"key":"2232_CR5","volume-title":"The Linear Complementarity Problem. Computer Science and Scientific Computing","author":"RW Cottle","year":"1992","unstructured":"Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Computer Science and Scientific Computing. Academic Press, Boston (1992)"},{"key":"2232_CR6","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0024-3795(89)90463-1","volume":"114","author":"RW Cottle","year":"1989","unstructured":"Cottle, R.W., Pang, J.-S., Venkateswaran, V.: Sufficient matrices and the linear complementarity problem. Linear Algebra Appl. 114, 231\u2013249 (1989)","journal-title":"Linear Algebra Appl."},{"key":"2232_CR7","first-page":"51","volume":"5","author":"Z Darvay","year":"2003","unstructured":"Darvay, Z.: New interior point algorithms in linear programming. Adv. Model. Optim. 5, 51\u201392 (2003)","journal-title":"Adv. Model. Optim."},{"key":"2232_CR8","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s11590-020-01612-0","volume":"15","author":"Z Darvay","year":"2021","unstructured":"Darvay, Z., Ill\u00e9s, T., Majoros, C.: Interior-point algorithm for sufficient LCPs based on the technique of algebraically equivalent transformation. Optim Lett. 15, 357\u2013376 (2021)","journal-title":"Optim Lett."},{"key":"2232_CR9","doi-asserted-by":"publisher","first-page":"2628","DOI":"10.1137\/19M1248972","volume":"30","author":"Z Darvay","year":"2020","unstructured":"Darvay, Z., Ill\u00e9s, T., Povh, J., Rig\u00f3, P.R.: Feasible corrector-predictor interior-point algorithm for $${P}_{*} (\\kappa )$$-linear complementarity problems based on a new search direction. SIAM J. Optim. 30, 2628\u20132658 (2020)","journal-title":"SIAM J. Optim."},{"key":"2232_CR10","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.ejor.2021.08.039","volume":"298","author":"Z Darvay","year":"2022","unstructured":"Darvay, Z., Ill\u00e9s, T., Rig\u00f3, P.R.: Predictor-corrector interior-point algorithm for $$P_*(\\kappa )$$-linear complementarity problems based on a new type of algebraic equivalent transformation technique. Eur. J. Oper. Res. 298, 25\u201335 (2022)","journal-title":"Eur. J. Oper. Res."},{"key":"2232_CR11","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s10998-016-0119-2","volume":"73","author":"Z Darvay","year":"2016","unstructured":"Darvay, Z., Papp, I.-M., Tak\u00e1cs, P.-R.: Complexity analysis of a full-Newton step interior-point method for linear optimization. Period. Math. Hung. 73, 27\u201342 (2016)","journal-title":"Period. Math. Hung."},{"key":"2232_CR12","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s10107-011-0465-z","volume":"129","author":"E de Klerk","year":"2011","unstructured":"de Klerk, E., Nagy, M.E.: On the complexitiy of computing the handicap of a sufficient matrix. Math. Program. 129, 383\u2013402 (2011)","journal-title":"Math. Program."},{"key":"2232_CR13","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1137\/S0036144595285963","volume":"39","author":"M Ferris","year":"1997","unstructured":"Ferris, M., Pang, J.: Engineering and economic applications of complementarity problems. SIAM Rev. 39, 669\u2013713 (1997)","journal-title":"SIAM Rev."},{"issue":"224","key":"2232_CR14","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0024-3795(93)00271-Z","volume":"223","author":"S-M Guu","year":"1995","unstructured":"Guu, S.-M., Cottle, R.: On a subclass of $${P}_0$$. Linear Algebra Appl. 223(224), 325\u2013335 (1995)","journal-title":"Linear Algebra Appl."},{"key":"2232_CR15","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s11590-018-1241-2","volume":"13","author":"M Haddou","year":"2019","unstructured":"Haddou, M., Migot, T., Omer, J.: A generalized direction in interior point method for monotone linear complementarity problems. Optim. Lett. 13, 35\u201353 (2019)","journal-title":"Optim. Lett."},{"key":"2232_CR16","doi-asserted-by":"publisher","first-page":"1097","DOI":"10.1016\/j.ejor.2005.08.031","volume":"181","author":"T Ill\u00e9s","year":"2007","unstructured":"Ill\u00e9s, T., Nagy, M.: A Mizuno\u2013Todd\u2013Ye type predictor-corrector algorithm for sufficient linear complementarity problems. Eur. J. Oper. Res. 181, 1097\u20131111 (2007)","journal-title":"Eur. J. Oper. Res."},{"key":"2232_CR17","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s10898-008-9348-0","volume":"47","author":"T Ill\u00e9s","year":"2010","unstructured":"Ill\u00e9s, T., Nagy, M., Terlaky, T.: A polynomial path-following interior point algorithm for general linear complementarity problems. J. Global Optim. 47, 329\u2013342 (2010)","journal-title":"J. Global Optim."},{"key":"2232_CR18","first-page":"1","volume":"5","author":"T Ill\u00e9s","year":"2010","unstructured":"Ill\u00e9s, T., Nagy, M., Terlaky, T.: Polynomial interior point algorithms for general linear complementarity problems. Alg. Oper. Res. 5, 1\u201312 (2010)","journal-title":"Alg. Oper. Res."},{"key":"2232_CR19","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1137\/S1052623498336590","volume":"11","author":"T Ill\u00e9s","year":"2000","unstructured":"Ill\u00e9s, T., Peng, J., Roos, C., Terlaky, T.: A strongly polynomial rounding procedure yielding a maximally complementary solution for $$P_*(\\kappa )$$ linear complementarity problems. SIAM J. Optim. 11, 320\u2013340 (2000)","journal-title":"SIAM J. Optim."},{"key":"2232_CR20","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-642-59073-3_9","volume-title":"Recent Adv. Optim.","author":"T Ill\u00e9s","year":"1997","unstructured":"Ill\u00e9s, T., Roos, C., Terlaky, T.: Polynomial affine-scaling algorithms for $$P_*(\\kappa )$$ linear complementary problems. In: Gritzmann, P., Horst, R., Sachs, E., Tichatschke, R. (eds.) Recent Adv. Optim., pp. 119\u2013137. Springer, Berlin (1997)"},{"key":"2232_CR21","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s11075-013-9738-3","volume":"66","author":"B Kheirfam","year":"2014","unstructured":"Kheirfam, B.: A predictor-corrector interior-point algorithm for $${P}_*(\\kappa )$$-horizontal linear complementarity problem. Numer. Algorithms 66, 349\u2013361 (2014)","journal-title":"Numer. Algorithms"},{"key":"2232_CR22","doi-asserted-by":"publisher","first-page":"277","DOI":"10.17535\/crorr.2016.0019","volume":"7","author":"B Kheirfam","year":"2016","unstructured":"Kheirfam, B., Haghighi, M.: A full-Newton step feasible interior-point algorithm for $${P}_{*}(\\kappa )$$-LCP based on a new search direction. Croat. Oper. Res. Rev. 7, 277\u2013290 (2016)","journal-title":"Croat. Oper. Res. Rev."},{"key":"2232_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-54509-3","volume-title":"A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems","author":"M Kojima","year":"1991","unstructured":"Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems. Lecture Notes in Computer Science, vol. 538. Springer, Berlin (1991)"},{"key":"2232_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01587074","volume":"44","author":"M Kojima","year":"1989","unstructured":"Kojima, M., Mizuno, S., Yoshise, A.: A polynomial-time algorithm for a class of linear complementarity problems. Math. Program. 44, 1\u201326 (1989)","journal-title":"Math. Program."},{"key":"2232_CR25","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0112033","volume":"12","author":"CE Lemke","year":"1964","unstructured":"Lemke, C.E., Howson, J.T.: Equilibrium points of bimatrix games. SIAM J. Appl. Math. 12, 413\u2013423 (1964)","journal-title":"SIAM J. Appl. Math."},{"key":"2232_CR26","doi-asserted-by":"crossref","unstructured":"Le$${\\check{s}}$$aja, G., Roos, C.: Unified analysis of kernel-based interior-point methods for $$P_*(\\kappa )$$-linear complementarity problems. SIAM J. Optim. 20, 3014\u20133039 (2010)","DOI":"10.1137\/090766735"},{"key":"2232_CR27","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s10957-012-0195-2","volume":"157","author":"H Mansouri","year":"2013","unstructured":"Mansouri, H., Pirhaji, M.: A polynomial interior-point algorithm for monotone linear complementarity problems. J. Optim. Theory Appl. 157, 451\u2013461 (2013)","journal-title":"J. Optim. Theory Appl."},{"key":"2232_CR28","unstructured":"Nagy, M.E., Varga, A.: A family of Ai-Zhang type interior point algorithms for linear complementarity problems (session talk). In: KOI 2022\u201419th International Conference on Operational Research (2022), Sibenik, Croatia"},{"key":"2232_CR29","doi-asserted-by":"crossref","unstructured":"Nesterov, Y.E., Nemirovskii., A.: Interior-point polynomial algorithms in convex programming, vol 13. Society for Industrial and Applied Mathematics (1994)","DOI":"10.1137\/1.9781611970791"},{"key":"2232_CR30","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1016\/j.jmaa.2005.04.028","volume":"314","author":"S Pan","year":"2006","unstructured":"Pan, S., Li, S., He, S.: An infeasible primal-dual interior-point algorithm for linear programs based on logarithmic equivalent transformation. J. Math. Anal. Appl. 314, 644\u2013660 (2006)","journal-title":"J. Math. Anal. Appl."},{"key":"2232_CR31","volume-title":"Self-Regular Functions: A New Paradigm for Primal-Dual Interior-Point Methods","author":"J Peng","year":"2002","unstructured":"Peng, J., Roos, C., Terlaky, T.: Self-Regular Functions: A New Paradigm for Primal-Dual Interior-Point Methods. Princeton University Press, Princeton (2002)"},{"key":"2232_CR32","unstructured":"Rig\u00f3, P.R.: New trends in algebraic equivalent transformation of the central path and its applications. PhD thesis, Budapest University of Technology and Economics, Institute of Mathematics, Hungary (2020)"},{"key":"2232_CR33","volume-title":"Theory and Algorithms for Linear Optimization","author":"C Roos","year":"2005","unstructured":"Roos, C., Terlaky, T., Vial, J.-P.: Theory and Algorithms for Linear Optimization. Springer, New York (2005)"},{"key":"2232_CR34","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1287\/moor.2019.0996","volume":"45","author":"E Sloan","year":"2020","unstructured":"Sloan, E., Sloan, O.N.: Quitting games and linear complementarity problems. Math. Methods Oper. Res. 45, 434\u2013454 (2020)","journal-title":"Math. Methods Oper. Res."},{"key":"2232_CR35","first-page":"103","volume":"239","author":"H V\u00e4liaho","year":"1996","unstructured":"V\u00e4liaho, H.: $${P}_*$$-matrices are just sufficient. Linear Algebra Appl. 239, 103\u2013108 (1996)","journal-title":"Linear Algebra Appl."},{"key":"2232_CR36","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971453","volume-title":"Primal-Dual Interior-Point Methods","author":"S Wright","year":"1997","unstructured":"Wright, S.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997)"},{"key":"2232_CR37","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032701","volume-title":"Interior Point Algorithms, Theory and Analysis","author":"Y Ye","year":"1997","unstructured":"Ye, Y.: Interior Point Algorithms, Theory and Analysis. Wiley, Chichester (1997)"},{"key":"2232_CR38","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/s10107-006-0065-5","volume":"111","author":"Y Ye","year":"2008","unstructured":"Ye, Y.: A path to the Arrow\u2013Debreu competitive market equilibrium. Math. Program. 111, 315\u2013348 (2008)","journal-title":"Math. Program."}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-023-02232-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-023-02232-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-023-02232-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,21]],"date-time":"2024-07-21T08:04:16Z","timestamp":1721549056000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-023-02232-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,9]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["2232"],"URL":"https:\/\/doi.org\/10.1007\/s10957-023-02232-1","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,9]]},"assertion":[{"value":"26 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}