International Journal of Nonlinear Analysis and Applications
Complexity analysis of interior-point methods yielding the best known iteration bound for semidefinite optimization
Document Type : Review articles
Authors
1 LMFN, Fundamental and Numerical Mathematics Laboratory, Department of Mathematics, Faculty of Science, Ferhat Abbas University, Setif, Algeria
2 LMAH, FR-CNRS-3335, ISCN, 7600 Le Havre, France, University of 8 May 1945 Guelma. BP 401, 24000 Guelma, Algeria
Abstract
The purpose of this paper is to obtain new complexity results for solving the semidefinite optimization (SDO) problem. We define a new proximity function for the SDO by a new kernel function with an efficient logarithmic barrier term. Furthermore, we formulate an algorithm for the large and small-update primal-dual interior-point method (IPM) for the SDO. It is shown that the best result of iteration bounds for large-update methods and small-update methods can be achieved, namely $\mathcal{O}\left(qn^{\frac{q+1}{2q}}\log \frac{n}{\epsilon }\right) $\ for large-update and $\mathcal{O}(q^{2}\sqrt{n}\log \frac{n}{\epsilon })$ for small-update methods, where $q>1.$ The analysis in this paper is new and different from the one using for LO. Several new tools and techniques are derived in this paper. Furthermore, numerical tests to investigate the behavior of the algorithm so as to be compared with other approaches.
Keywords
[3] Y.Q. Bai, M. El Ghami and C. Roos, A comparative study of kernel function for primal-dual interior point algorithms in linear optimization, SIAM J. Optim. 15 (2004), no. 1, 101–128.
[4] H. Barsam and H. Mohebi, Characterizations of upward and downward sets in semimodules by using topical functions, Numer. Funct. Anal. Optim. 37 (2016), no. 11, 1354-1377.
[5] A. Benhadid, K. Saoudi and F. Merahi, An interior point approach for linear complementarity problem using new parametrized kernel function, Optimization 71 (2022), no. 15, 4403–4422.
[6] A. Benhadid and F. Merahi, Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term, Numer. Algebra Control Optim. 13 (2023), no. 2, 224–238.
[7] M. Bouafia, D. Benterki and A. Yassine, An efficient parameterized logarithmic kernel function for linear optimization, Optim. Lett. 12 (2018), no. 5, 1079-1097.
[8] E. De Klerk, Aspects of Semidefinite Programming, Applied Optimization. vol. 65. Kluwer Academic, Dordrecht, 2002.
[9] L. Derbal and Z Kebbiche, Theoretical and numerical result for linear optimization problem based on a new kernel function, J. Sib. Federal Univer. Math. Phys. 12 (2019), no. 2, 160–172.
[10] M. El Ghami, Primal-dual algorithms for semidefinite optimization problems based on generalized trigonometric barrier function, Int. J. Pure Appl. Math. 114 (2017), no. 4, 797–818.
[11] R.A. Horn and R.J. Charles, Matrix Analysis, Compridge University Press, UK, 1986.
[12] J. Peng, C. Roos and T. Terlaky, Self-regularity: A New Paradigm for Primal-dual Interior-point Algorithms, New Jersey, Princeton University Press, 2002.
[13] J. Peng, C. Roos and T. Terlaky, Self-regular proximities and new search directions for linear and semidefinite optimization, Math. Program.. 93 (2002), no. A, 129–171.
[14] C. Roos, T. Terlaky and J.P. Vial, Theory and algorithms for linear optimization: An interior point approach, John Wiley & Sons, Chichester, UK, 1997.
[15] M.J. Todd, K.C. Toh and R.H. T¨ut¨unc¨u, The Nesterov-Todd direction in semidefinite programming, mathematical programming, SIAM J. Optim. 8 (1998), no. 3, 769–796.
[16] M.J. Todd, A study of search directions in primal-dual interior-point methods for semidefinite programming, Optim. Meth. Softw. 11 (1999), 1–46.
[17] G.Q. Wang, Y.Q. Bai and C. Roos, Primal-dual interior point algorithms for semidefinite optimization based on a simple kernel function, J. Math. Model. Algorithms 4 (2005), no. 4, 409–433.
[18] G.Q. Wang and Y.Q. Bai, A class of polynomial primal-dual interior-point algorithms for semidefinite optimization, J. Shanghai University (English Edition) 10 (2006), no. 3, 198–207.
[19] H. Wolkowicz, R. Saigal and L. Vandenberghe, Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, Dordrecht, Kluwer Academic Publishers, 2000.
[20] M.W. Zhang, A large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function, Acta Math. Sinica English Ser. 28 (2012), no. 11, 2313–2328.
)
Volume 14, Issue 5
May 2023Pages 287-301
- Receive Date: 17 December 2022
- Revise Date: 20 February 2023
- Accept Date: 22 February 2023