In this paper, based on Darvay et al.’s strategy for linear optimization (LO) (Z. Darvay and P.R. Takács, Optim. Lett. 12 (2018) 1099–1116.), we extend Kheirfam et al.’s feasible primal-dual path-following interior point algorithm for LO (B. Kheirfam and A. Nasrollahi, Asian-Eur. J. Math. 1 (2020) 2050014.) to semidefinite optimization (SDO) problems in order to define a class of new search directions. The algorithm uses only full Nesterov-Todd (NT) step at each iteration to find an ε-approximated solution to SDO. Polynomial complexity of the proposed algorithm is established which is as good as the LO analogue. Finally, we present some numerical results to prove the efficiency of the proposed algorithm.
Keywords: Semidefinite optimization, interior point method, full Nesterov-Todd step, new search directions, algebraic equivalent transformation, polynomial complexity
@article{RO_2022__56_6_3955_0,
author = {Guerra, Loubna},
title = {A class of new search directions for {full-NT} step feasible interior point method in semidefinite optimization},
journal = {RAIRO. Operations Research},
pages = {3955--3971},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {6},
doi = {10.1051/ro/2022192},
mrnumber = {4513269},
zbl = {1539.90137},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2022192/}
}
TY - JOUR AU - Guerra, Loubna TI - A class of new search directions for full-NT step feasible interior point method in semidefinite optimization JO - RAIRO. Operations Research PY - 2022 SP - 3955 EP - 3971 VL - 56 IS - 6 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2022192/ DO - 10.1051/ro/2022192 LA - en ID - RO_2022__56_6_3955_0 ER -
%0 Journal Article %A Guerra, Loubna %T A class of new search directions for full-NT step feasible interior point method in semidefinite optimization %J RAIRO. Operations Research %D 2022 %P 3955-3971 %V 56 %N 6 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2022192/ %R 10.1051/ro/2022192 %G en %F RO_2022__56_6_3955_0
Guerra, Loubna. A class of new search directions for full-NT step feasible interior point method in semidefinite optimization. RAIRO. Operations Research, Tome 56 (2022) no. 6, pp. 3955-3971. doi: 10.1051/ro/2022192
[1] , A new primal-dual path-following method for convex quadratic programming. Comput. Appl. Math. 25 (2006) 97–110. | MR | Zbl | DOI
[2] and , A full Nesterov-Todd-step feasible primal-dual interior point algorithm for convex quadratic semi-definite optimization. Appl. Math. Comput. 231 (2014) 581–590. | MR | Zbl
[3] , Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5 (1995) 13–51. | MR | Zbl | DOI
[4] , New interior-point algorithms in linear optimization. Adv. Model. Optim. 5 (2003) 51–92. | MR | Zbl
[5] and , New method for determining search directions for interior-point algorithms in linear optimization. Optim. Lett. 12 (2018) 1099–1116. | MR | Zbl | DOI
[6] , and , Complexity analysis of a full-Newton step interior-point method for linear optimization. Period. Math. Hung. 73 (2016) 27–42. | MR | Zbl | DOI
[7] , Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands (2002). | MR | Zbl | DOI
[8] , and , On the convergence of the central path in semidefinite optimization. SIAM J. Optim. 12 (2002) 1090–1099. | MR | Zbl | DOI
[9] , and , Full Nesterov-Todd step infeasible interior- point method for symmetric optimization. Eur. J. Oper. Res. 214 (2011) 473–484. | MR | Zbl | DOI
[10] and , A parametric kernel function generating the best known iteration bound for large-update methods for CQSDO. Stat. Optim. Inf. Comput. 8 (2020) 876–889. | MR | DOI
[11] , New complexity analysis of a full Nesterov-Todd step interior-point method for semidefinite optimization. Asian-Eur. J. Math. 3 (2017) 1750070. | MR | Zbl | DOI
[12] and , An extension for identifying search directions for interior-point methods in linear optimization. Asian-Eur. J. Math. 1 (2020) 2050014. | MR | Zbl | DOI
[13] , and , Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Optim. 7 (1997) 86–125. | MR | Zbl | DOI
[14] and , A new full Newton-step infeasible interior-point algorithm for semidefinite optimization. Numer. Algorithms 52 (2009) 225–255. | MR | Zbl | DOI
[15] and , Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia, PA (1994). | MR | Zbl | DOI
[16] , and , Theory and algorithms for linear optimization. An interior point approach. John-Wiley, Sons, Chichester, UK (1997). | MR | Zbl
[17] , and , On the Nesterov-Todd direction in semidefinite programming. SIAM J. Optim. 8 (1998) 769–796. | MR | Zbl | DOI
[18] and , A new primal-dual path-following interior point algorithm for semidefinite programming. J. Math. Anal. Appl. 353 (2009) 339–349. | MR | Zbl | DOI
[19] and , A primal-dual path-following interior-point algorithm for second-order cone optimization with full Nesterov-Todd step. Appl. Math. Comput. 215 (2009) 1047–1061. | MR | Zbl
[20] and , A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization. J. Optim. Theory Appl. 154 (2012) 966–985. | MR | Zbl | DOI
[21] , and , Handbook of Semidefinite Programming, Theory, Algorithms, and Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands (2000). | MR | Zbl | DOI
[22] , and , Full Nesterov-Todd step primal-dual interior- point mathods for second-order cone optimization. J. Optim. Theory Appl. 158 (2013) 816–858. | MR | Zbl | DOI
Cité par Sources :
