A primal-dual interior-point algorithm for absolute value equation based on a novel parametric kernel function
Résumé
In this work, we provide a primal-dual interior point algorithm based on a novel parametric kernel function for the absolute value equation Ay − |y| = b. We may describe the NP-hard absolute value equation as a monotone linear complementarity problem when the singular values of the matrix A are greater than 1, demonstrating that the previous assumption guarantees the existence and uniqueness of the solution to the monotone linear complementarity problem, which is equivalent to the existence and uniqueness of the solution to the absolute value equation. The new algorithm has the best known iteration for large- and small-update methods with a given value of its parameter p. Finally, we provide some numerical results to clarify the usefulness of the suggested algorithm.
Téléchargements
Références
M.Achache, Complexity analysis of an interior point algorithm for the semidefinite optimization based on a new kernel function with a double barrier term. Acta Mathematica Sinica, English Series, 31 (3) : 543-556, (2015).
M. Achache and N. Hazzam, Solving absolute value equations via linear complementarity and interior-point methods. Journal of Nonlinear Functional Analysis. Article. ID 39: 1-10 (2018).
M. Achache and N. Tabchouche, A full-Newton step feasible interior-point algorithm for monotone horizontal linear complementarity problems, Optimization Letters. 1-19: (2018).
Y.Q.Bai, M.El Ghami, C. Roos, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization, SIAM J. Optim, 101-128 (2004).
Y.Q.Bai, M.El Ghami, C. Roos, A new efficient large-update primal-dual interior-point method based on a finite barrier, SIAM journal on optimization. 13 (3) : 766-782, (2003).
N.Boudjellal, H.Roumili & D.J.Benterki, A primal-dual interior point algorithm for convex quadratic programming based on a new parametric kernel function. A Journal of Mathematical Programming and Operations Research, (2020).
B.Bounibane , El.a.Djeffal, Kernel function-based interior-point algorithms for linear optimisation, Int. J. Mathematical Modelling and Numerical Optimisation, Vol. 9, No. 2, pp 158-177 (2019).
L.Caccetta, B.Qu, G.Zhou, A globally and quadratically convergent method for absolute value equations. Comput. Optim. Appl. 48 (2011), 45–58.
S.J.Chung, NP-completeness of the linear complementarity problem. J. Optim. Theory Appl. 60, 393–399 (1989).
R.W.Cottle, G.Dantzig, Complementary pivot theory of mathematical programming. Linear Algebra and its Applications, 103-125 (1968).
R.W.Cottle, J.S.Pang, R.E.Stone, The linear complementarity problem, Academic Press, New York, (1992).
El.A.Djeffal, M.Laouar, A primal-dual interior-point method based on a new kernel function for linear complementarity problem, Asian-European, (2018).
J-M.Feng, S-Y.Liu, A Three-Step Iterative Method for Solving Absolute Value Equations. (2020).
R.A.Horn and C.R.Johnson, Matrix Analysis, Cambridge University Press, Cambridge, (1985).
S.-L.Hu, Z.-H.Huang, A note on absolute value equations. Optim. Lett. 4, 417–424 (2010).
X.Jiang, Y.Zhang, A smoothing-type algorithm for absolute value equations. J. Ind. Manag. Optim. 9, 789–798 (2013).
M.Kojima, M.Shindoh , S.Hara, Interior point methods for the monotone semidefinite linear complementarity in symmetric matrices. SIAM J Optim. (1997); 7:86–125.
O.L.Mangasarian, Absolute value programming. Comput. Optim Appl. 36, 43-53 (2007).
O.L.Mangasarian, Absolute value equation solution via concave minimization. Optim. Lett. 1, 3–5 (2007).
O.L.Mangasarian, A generalized Newton method for absolute value equations. Optim. Let. 3, 101–108 (2009).
O.L.Mangasarian, R.R.Meyer, Absolute value equations. Linear Algebra Appl. 419, 359–367 (2006).
M.A.Noor, J.Iqbal, K.I.Noor, E.Al-Said, On an iterative method for solving absolute value equations. Optim. Lett.6(5), 1027–1033 (2012).
J.Peng, C.Roos & T.Terlaky, Self-regular functions and new search directions for linear and semidefinite optimization. Mathematical Programming, vol.93 : 129-171, (2002).
J. Peng, C. Roos, and T. Terlaky, Self-Regularity A New Paradigm for Primal-Dual Interior-Point Algorithms, Princeton University Press, Princeton, NJ, (2002).
J.Rohn, A theorem of the alternatives for the equation Ax + B|x| = b, Linear Multilinear Algebra, 421-426 52 (2004).
J.Rohn, V.Hooshyarbarkhsh, R.Farhadsefat, An iterative method for solving absolute value equations and sufficient conditions for unique solvability. Optim. Lett. 8(1), 35–44 (2014).
C.Roos, T.Terlaky, J.-Ph.Vial, Theory and Algorithms for Linear Optimization. An Interior-Point Approach, John Wiley & Sons, Chichester, UK, (1997), 2nd Ed, Springer, (2006).
L.Yong, S.Zhang, F.Deng, W.Xiong, Feasible interior point method for absolute value equation, Fourth International Conference on Information and Computing, (2011).
M.W.Zhang, A large-update interior-point algorithm for convex quadratic semidefinite optimization based on a new kernel function. Acta Mathematica Sinica, English Series, vol.28 : 2313-2321, (2012).
Copyright (c) 2025 Boletim da Sociedade Paranaense de Matemática
Ce travail est disponible sous la licence Creative Commons Attribution 4.0 International .
When the manuscript is accepted for publication, the authors agree automatically to transfer the copyright to the (SPM).
The journal utilize the Creative Common Attribution (CC-BY 4.0).
