Iranian Journal of Numerical Analysis and Optimization

Iranian Journal of Numerical Analysis and Optimization

An improved search direction based on algebraic equivalent transformation technique for convex quadratic optimization

Document Type : Research Article

Authors
Laboratory of Fundamental and Numerical Mathematics, Department of Mathematics, Faculty of Sciences, Setif 1 University-Ferhat Abbas, Setif, 19000, Algeria.
Abstract
This work presents an improved interior point algorithm with full Newton step for convex quadratic optimization. Based on the technique of algebraic equivalent transformation, we first propose a new search direction for convex quadratic optimization with the aim of improving the algorithmic complexity of the proposed algorithm. We then perform a complete theoretical study of convergence and complexity, proving that our algorithm is well-defined, converge quadratically and achieves the best known polynomial complexity bounds established for primal-dual interior point methods. Following this, we conduct comparative numerical tests to evaluate the efficiency of the algorithm. The theoretical and numerical results are encouraging and clearly confirm our purpose.
Keywords
Subjects

[1] Abbaszadehpeivasti, H., de Klerk, E. and Zamani, M. On the rate of convergence of the
difference-of-convex algorithm (DCA), J. Optim. Theory. Appl., 202 (2024), 475–496.
[2] Achache, M. A new primal-dual path-following method for convex quadratic programming,
Comput. Appl. Math., 25(1) (2006), 97–110.
[3] Asadi, S. and Mansouri, H. A new full-Newton step O(n) infeasible interior-point algorithm
for P∗(κ)-horizontal linear complementarity problems, Comput. Sci. J. Mold., 64 (2014),
37–61.
[4] Asadi, S., Mansouri, H. and Darvay, Z. An infeasible full-NT step IPM for horizontal linear
complementarity problem over Cartesian product of symmetric cones, Optim., 66(2) (2016),
225–250.
[5] Bai, Y.Q., El Ghami, M. and Roos, C. A new efficient large-update primal-dual interior-point
method based on a finite barrier, SIAM J. Optim., 13(3) (2002), 766–782.
[6] Bouafia, M., Benterki, D. and Yassine, A. Complexity analysis of interior point methods for
linear programming based on a parameterized kernel function, RAIRO Oper. Res., 50(4-5)
(2016), 935–949.
[7] Boudjellal, N. and Benterki, D. A new full-Newton step feasible interior point method for
convex quadratic programming, Optimization, 73 (2024), 1571–1588.
[8] Boudjellal, N., Roumili, H. and Benterki, D. Complexity analysis of interior point methods
for convex quadratic programming based on a parameterized kernel function, Bol. Soc. Parana.
Mat., 40 (2022), 1–16.
[9] Chinchilla, R., Yang, G. and Hespanha, J.P. Newton and interior-point methods for (con-
strained) nonconvex–nonconcave minmax optimization with stability and instability guaran-
tees, Math. Control Signals Syst., 36 (2024), 381–421.
[10] Darvay, Z. A new algorithm for solving self-dual linear optimization problems, Studia Univ.
Babeș-Bolyai Informatica, 47 (2002), 15–26.
[11] Darvay, Z. New interior point algorithms in linear programming, Adv. Model. Optim., 5(1)
(2003), 51–92.
[12] Darvay, Z., Papp, I.M. and Takács, P.R. An infeasible full-Newton step algorithm for linear
optimization with one centering step in major iteration, Studia Univ. Babes-Bolyai Infor-
matica, 59 (1) (2014), 28–45.
[13] Darvay, Z., Papp, I. M. and Takács P. R. Complexity analysis of a full-Newton step interior-
point method for linear optimization, Period. Math. Hungar., 73 (2016), 27–42.
[14] Darvay, Z. and Takács, P. R. New method for determining search directions for interior-point
algorithms in linear optimization, Optim. Lett., 12 (2018), 1099–1116.
[15] Grimes, W. and Achache, M. A path-following interior-point algorithm for monotone LCP
based on a modified Newton search direction, RAIRO Oper. Res., 57(3) (2023), 1059–1073.
[16] Hock, W. Test examples for nonlinear programming codes. Springer Berlin, Heidelberg, 1981.
[17] Kheirfam, B. A new infeasible interior-point method based on Darvay’s technique for sym-
metric optimization, Ann. Oper. Res., 211 (2013), 209–224.
[18] Kheirfam, B. New complexity analysis of a full Nesterov–Todd step interior-point method
for semidefinite optimization, Asian-Eur. J. Math., 10(4) (2017), 1750070.
[19] Kheirfam, B. and Nasrollahi, A. An extension for identifying search directions for interior-
point methods in linear optimization, Asian-Eur. J. Math., 13 (2020), 2050014.
[20] LeThi, H.A., Le, H.M., Phan, D.N. and Tran, B. Novel DCA based algorithms for a special
class of nonconvex problems with application in machine learning, Appl. Math. Comput., 409
(2021), 125904.
[21] Li, X. and Zhang, M. Interior-point algorithm for linear optimization based on a new trigono-
metric kernel function, Oper. Res. Lett., 43(5) (2015), 471–475.
[22] Lukšan, L., Matonoha. C. and Vlček, J. Interior-point method for non-linear non-convex
optimization, Numerical linear algebra with applications, 11(5-6) (2004), 431–453.
[23] Mansouri, H. and Pirhaji, M. A polynomial interior-point algorithm for monotone linear
complementarity problems, J. Optim. Theory Appl., 157 (2013), 451–461.
[24] Maros, I. and Mészáros, C. A repository of convex quadratic programming problems, Opti-
mization methods and software, 11(1-4) (1999), 671–681.
[25] Phan, D.N. and Thi, H.A. Difference-of-convex algorithm with extrapolation for nonconvex,
nonsmooth optimization problems, Math. Oper. Res., 49(3) (2024), 1973–1985.
[26] Roumili, H. and Kebbiche, Z. A weighted target-following algorithm for linearly constrained
convex optimization, Int. J. Open Problems Compt. Math., 5(4) (2012), 25–33.
[27] Tahmasebzadeh, S., Navidi, H. and Malek, A. Novel interior point algorithms for solving
nonlinear convex optimization problems, Adv. Oper. Res., 2015 (2015).
[28] Vanderbei, R.J. and Shanno, D.F. An interior-point algorithm for nonconvex nonlinear
programming, Comput. Optim. Appl., 13 (1999) , 231–252.
[29] Wang, G.Q. A new polynomial interior-point algorithm for the monotone linear comple-
mentarity problem over symmetric cones with full NT-steps, Asia-Pac. J. Oper. Res., 29(2)
(2012), 1250015.
[30] Zaoui, B., Benterki, D. and Khelladi, S. New efficient descent direction of a primal-dual path-
following algorithm for linear programming, Stat. Optim. Inf. Comput., 12 (2024), 1098–1112.
[31] Zaoui, B., Benterki, D. and Khelladi, S. Efficient descent direction of a primal-dual interior
point algorithm for convex quadratic optimization, J. Inf. Optim. Sci., (2025). Available online.
[32] Zaoui, B., Benterki, D., Kraria, A. and Raouache, H. Interior-point algorithm for linear
programming based on a new descent direction, RAIRO Oper. Res., 57 (2023), 2473–2491.
[33] Zhang, M., Bai Y.Q. and Wang G.Q. A new primal-dual path-following interior-point algo-
rithm for linearly constrained convex optimization, Journal of Shanghai University (English
Edition), 12 (2008), 475–480.
[34] Zhang, M., Huang K., Li M. and Lv Y. A new full-Newton step interior-point method
for P∗(κ)-LCP based on a positive-asymptotic kernel function, J. Appl. Math. Comput., 64
(2020), 313–330.
Send comment about this article
Enter Name.
Enter a valid email address.
Enter a vaid affiliation.
Enter comments (At leaset 10 words)
CAPTCHA Image
Enter Security Code Correctly.