Abstract
In this paper, we introduce for the first time a new eligible kernel function with a hyperbolic barrier term for semidefinite programming (SDP). This add a new type of functions to the class of eligible kernel functions. We prove that the interior-point algorithm based on the new kernel function meets \({\cal O}({n^{{3 \over 4}}}\log {n \over \varepsilon })\) iterations as the worst case complexity bound for the large-update method. This coincides with the complexity bound obtained by the first kernel function with a trigonometric barrier term proposed by El Ghami et al. in 2012, and improves with a factor \({n^{{1 \over 4}}}\) the obtained iteration bound based on the classic kernel function. We present some numerical simulations which show the effectiveness of the algorithm developed in this paper.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bai, Y.Q., Roos, C. A primal-dual interior-point method based on a new kernel function with linear growth rate. Proceedings of Industrial Optimization Symposium and Optimization Day, Australia, 2002
Bai, Y.Q., EL Ghami, M. Roos, C. A new efficient large-update primal-dual interior-point method based on a finite barrier. SIAM J. Optim., 13(3): 766–782 (2003)
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(1): 101–128 (2004)
Bai, Y.Q., Guo, J. Roos, C. A new kernel function yielding the best known iteration bounds for primal-dual interior-point algorithms. Acta Math. Sin. (Engl. Ser.), 25(12): 2169–2178 (2009)
Bouafia, M., Benterki, D., Yassine, A. An efficient primal-dual interior point method for linear programming problems based on a new kernel function with a trigonometric barrier term. J. Optim. Theory Appl., 170(2): 528–545 (2016)
Bouafia, M., Benterki, D. Yassine, A. Complexity analysis of interior point methods for linear programming based on a parameterized kernel function. RAIRO-Oper. Res., 50: 935–949 (2016)
Bouafia, M. Yassine, A. An efficient twice parameterized trigonometric kernel function for linear optimization. Optim. Eng., 21: 651–672 (2020)
Boudjellal, N., Roumili, H. Benterki, Dj. A primal-dual interior point algorithm for convex quadratic programming based on a new kernel function with an exponential barrier term. Optim., https://doi.org/10.1080/02331934.2020.1751156 (2020)
Cai, X.Z., Wang, G.Q., El Ghami, M. Yue, Y.J. Complexity analysis of primal-dual interior-point methods for linear optimization based on a new parametric kernel function with a trigonometric barrier term. Abstr. Appl. Anal.: 2014, 11 (2014). Art. ID 710158
Choi, B.K. Lee, G. M. On complexity analysis of the primal-dual interior point method for semidefinite optimization problem based on a new proximity function. Nonlinear Anal.: 71(12): 2540–2550 (2009)
El Ghami, M., Ivanov, I.D., Roos, C., Steihaug, T. A polynomial-time algorithm for LO based on generalized logarithmic barrier functions. Int. J. Appl. Math., 21: 99–115 (2008)
El Ghami, M., Guennoun, Z.A., Bouali, S. Steihaug, T. Interior point methods for linear optimization based on a kernel function with a trigonometric barrier term. J. Comput. Appl. Math.: 236 3613–3623 (2012)
Fathi-Hafshejani, S. Fakharzadeh, J.A. An interior-point algorithm for semidefinite optimization based on a new parametric kernel function. J. Nonlinear. Funct. Anal., 2018: 1–24 (2018) Art. ID 14
Fathi-Hafshejani, S., Peyghami, M.R. Fakharzadeh, J.A. An interior-point method for linear optimization based on a trigonometric kernel function. J. Nonlinear. Funct. Anal.: 2019 1–17 (2019) Art. ID 46
Helmberg, C., Rendl, F., Vanderbei, R.J., Wolkowicz, H. An interior-point method for semidefinite programming. SIAM. J. Optim., 6: 342–361 (1996)
Horn, R.A. Johnson, C.R. Topics in matrix analysis. Cambridge University Press, Cambridge, 1991
Karmarkar, N.K. A new polynomial-time algorithm for linear programming. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing, 4: 373–395 (1984)
Kheirfam, B. Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term. Numer. Algorithms., 61: 659–680 (2012)
Li, X., Zhang, M. Interior-point algorithm for linear optimization based on a new trigonometric kernel function. Oper. Res. Lett., 43: 471–475 (2015)
Li, M., Zhang, M., Huang, K., Huang, Z. A new primal-dual interior-point method for semidefinite optimization based on a parameterized kernel function. Optim. Eng., 22: 293–319 (2021)
Lütkepohl H. Handbook of matrices. Humboldt-Universität zu, Berlin, Germany, 1996
Fathi-Hafshejani, S. Moaberfard, Z. A generic kernel function for interior point methods. Optim. Eng., 22: 261–291 (2021)
Monteiro, R.D.C. Zanjácomo, P.R. A note on the existence of Alizadeh-Heaberly-Overton direction for semidefinite programming. Math. Program., 78(3): 393–396 (1997)
Peng, J., Roos, C. Terlaky, T. A new and efficient large-update interior point method for linear optimization. J. Comput. Technol., 6: 61–80 (2001)
Peng, J., Roos, C. Terlaky, T. Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program., 93: 129–171 (2002)
Peng, J., Roos, C. Terlaky, T. Self-regularity: A new paradigm for primal-dual interior-point algorithms. Princeton University Press, Princeton, 2002
Peyghami, M.R., Hafshejani, S.F. Complexity analysis of an interior point algorithm for linear optimization based on a new proximity function. Numer. Algorithms., 67: 33–48 (2014)
Peyghami, M.R., Fathi-Hafshejani, S. Chen, S. A primal-dual interior-point method for semidefinite optimization based on a class of trigonometric barrier functions. Oper. Res. Lett., 44(3): 319–323 (2016)
Peyghami, M.R., Hafshejani, S.F. Shirvani, L. Complexity of interior point methods for linear optimization based on a new trigonometric kernel function. J. Comput. Appl. Math., 255: 74–85 (2014)
Qian, Z.G., Bai, Y.Q. Wang, G.Q. Complexity analysis of interior-point algorithm based on a new kernel function for semidefinite optimization. J. Shanghai Univ.(Engl. Ed.), 12: 388–394 (2008)
Roos, C., Terlaky, T. Vial, J.Ph. Theory and Algorithms for Linear Optimization, An interior point approach. Wiley, Chichester, 1997
Sturm, J.F. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw., 11(12): 625–653 (1999)
Todd, M.J., Toh, K.C. Tütüncü, R.H. On the Nestrov-Todd direction in semidefinite programming. SIAM J. Optim., 8(3): 769–796 (1998)
Touil, I., Benterki, D. Yassine, A. A feasible primal-dual interior point method for linear semidefinite programming. J. Comput. Appl. Math., 312: 216–230 (2017)
Touil, I. Benterki, D. A primal-dual interior point method for the semidefinite programming problem based on a new kernel function. J Nonlinear. Funct. Anal., 2019: 1–17 (2019) Art. ID 25
Wang, G.Q., Bai, Y.Q., Roos, C. Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function. J. Math. Model. Algor., 4: 409–433 (2005)
Wolkowicz, H., Saigal. R. Vandenberghe. L. Handbook of semidefinite programming, Theory, Algorithms, and Applications. Kluwer Academic Publishers, 2000
Wright, S.J. Primal-dual interior point methods. SIAM Philadelphia USA, 1997
Ye, Y. Interior Point Algorithms. Theory and Analysis. Wiley, Chichester, 1997
Zhang, M.W. A large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function. Acta. Math. Sin.-English Ser. 28: 2313–2328 (2012)
Zhang, Y. On extending some primal-dual algorithms from linear programming to semidefinite programming. SIAM J. Optim., 8(2): 365–386 (1998)
Acknowledgments
The authors are very grateful and would like to thank the Editor-in-Chief and the anonymous referees for their suggestions and helpful comments which significantly improved the presentation of this paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Touil, I., Chikouche, W. Novel Kernel Function With a Hyperbolic Barrier Term to Primal-dual Interior Point Algorithm for SDP Problems. Acta Math. Appl. Sin. Engl. Ser. 38, 44–67 (2022). https://doi.org/10.1007/s10255-022-1061-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10255-022-1061-0
Keywords
- Linear Semidefinite Programming
- Primal-Dual Interior Point Methods
- Hyperbolic Kernel Function
- Complexity Analysis
- Large and small-update methods