A unified complexity analysis of interior point methods for semidefinite problems based on trigonometric kernel functions

References

• Peng J, Roos C, Terlaky T. Self-regularity: a new paradigm for primal-dual interior-point algorithms. Princeton (NJ): Princeton University Press; 2002.
   Google Scholar
• Karmarkar NK. New polynomial-time algorithm for linear programming. Combinatorica. 1984;4:373–395.
   Web of Science ®Google Scholar
• Kojima M, Mizuno S, Yoshise A. A primal-dual interior point algorithm for linear programming. In: Megiddo N, editor. Progress in mathematical programming: interior point and related methods. New York (NY): Springer; 1989. p. 29–47.
   Google Scholar
• Megiddo N. Pathways to the optimal set in linear programming. In: Megiddo N, editor. Progress in mathematical programming: interior-point and related methods. New York (NY): Springer-Verlag; 1989. p. 131–158.
   Google Scholar
• Alizadeh F. Combinatorial optimization with interior-point methods and semidefinite matrices [PhD thesis]. Minneapolis (MN): Computer Science Department, University of Minnesota; 1991.
   Google Scholar
• Alizadeh F, Haeberly JA, Overton M. Primal-dual interior-point methods for semidefinite programming. New York (NY): Courant Institute of Mathematical Sciences, New York University; 1996. ( Convergence rates, stability and numerical results; Tech. Report 721).
   Google Scholar
• Nesterov YE, Nemirovskii AS. Interior point polynomial algorithms in convex programming. Vol. 13, SIAM studies in applied mathematics. Philadelphia (PA): SIAM; 1994.
   Google Scholar
• Bai YQ, El Ghami M, Roos C. A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J Optim. 2004;15(1):101–128.
   Web of Science ®Google Scholar
• Peyghami MR, Fathi-Hafshejani S. An interior point algorithm for solving convex quadratic semidefinite optimization problems using a new kernel function. Iranian J Math Sci Inform. 2017;12(1):131–152.
   Google Scholar
• Wang GQ, Bai YQ. Primal-dual interior-point algorithm for convex quadratic semidefinite optimization. Nonlinear Anal. 2009;71:3389–3402.
   Web of Science ®Google Scholar
• Wang GQ, Zhu D. A unified kernel function approach to primal-dual interior-point algorithms for convex quadratic SDO. Numer Algorithms. 2011;57(4):537–558.
   Web of Science ®Google Scholar
• Zhang MW. A large-update interior-point algorithm for convex quadratic semidefinite optimization based on a new kernel function. Acta Math Sinica (Engl Ser). 2012;28(11):2313–2328.
   Web of Science ®Google Scholar
• Peyghami MR. An interior-point approach for semidefinite optimization using new proximity functions. Asia Pac J Oper Res. 2009;26:365–382.
   Web of Science ®Google Scholar
• Qian ZG, Bai YQ, Wang GQ. Complexity analysis of interior-point algorithm based on a new kernel function for semidefinite optimization. J Shanghai Univ (Engl Ed). 2008;12(5):388–394.
   Google Scholar
• Wang GQ, Bai YQ. A class of polynomial primal-dual interior-point algorithms for semidefinite optimization.J Shanghai Univ (Engl Ed). 2006;10(3):198–207.
   Google Scholar
• Amini K, Peyghami MR. An interior-point algorithm for linear optimization based on a new kernel function. Southeast Asian Bull Math. 2005;29:651–667.
   Google Scholar
• Bai YQ, El Ghami M, Roos C. A new efficient large-update primal-dual interior-point methods based on a finite barrier. SIAM J Optim. 2003;13(3):766–782 (electronic).
   Web of Science ®Google Scholar
• Li X, Zhang M. Interior-point algorithm for linear optimization based on a new trigonometric kernel function. Oper Res Lett. 2015;43:471–475.
   Web of Science ®Google Scholar
• Mansouri H, Roos C. A new full-Newton step O(n) infeasible interior-point algorithm for semidefinite optimization. Numer Algorithms. 2009;52(2):225–255.
   Web of Science ®Google Scholar
• Wang GQ, Bai YQ, Gao XY, Wang DZ. Improved complexity analysis of full Nesterov-Todd step interior-point methods for semidefinite optimization. J Optim Theory Appl. 2015;165(1):242–262.
   Web of Science ®Google Scholar
• Kheirfam B. Simplified infeasible interior-point algorithm for SDO using full Nesterov Todd step. Numer Algorithms. 2012;59(4):589–606.
   Web of Science ®Google Scholar
• El Ghami M, Guennoun ZA, Boula S, Steihaug T. Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term. J Comput Appl Math. 2012;236:3613–3623.
   Web of Science ®Google Scholar
• Fathi-Hafshejani S, Fatemi M, Peyghami MR. An interior-point method for P*(κ)-linear complementarity problem based on a trigonometric kernel function. J Appl Math Comput. 2015;48:111–128.
   Web of Science ®Google Scholar
• Lesaja G, Roos C. Unified analysis of kernel-based interior-point methods for P*(κ)-linear complementarity problems. SIAM J Optim. 2010;20:3014–3039.
   Web of Science ®Google Scholar
• El Ghami M. Primal-dual algorithms for P*(κ) linear complementarity problems based on a kernel-function with trigonometric barrier term. Theory Decis Mak Oper Res Appl. 2013;31:331–349.
   Google Scholar
• Kheirfam B. Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term. Numer Algorithms. 2012;61:659–680.
   Web of Science ®Google Scholar
• Peyghami MR, Fathi-Hafshejani S. Complexity analysis of an interior point algorithm for linear optimization based on a new poriximity function. Numer Algorithms. 2014;67:33–48.
   Web of Science ®Google Scholar
• Peyghami MR, Fathi-Hafshejani S, Shirvani L. Complexity of interior-point methods for linear optimization based on a new trigonometric kernel function. J Comput Appl Math. 2014;255:74–85.
   Web of Science ®Google Scholar
• 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. 2016;170:528–545.
   Web of Science ®Google Scholar
• El Ghami M. Primal-dual Algorithms for semidefinit optimization problems based on generalized trigonometric barrier function. Int J Pure Appl Math. 2017;114(4):797–818.
   Google Scholar
• Fathi-Hafshejani S, Mansouri H, Peyghami MR. A large-update primal dual interior-point algorithm for second-order cone optimization based on a new proximity function. Optimization. 2016;65:1477–1496.
   Web of Science ®Google Scholar
• Cai XZ, Wang GQ, El Ghami M, Yue YJ. Complexity analysis of primal-dual interior-point methods for linear optimization based on a new parametric kernel function with a trigonometric barrier term. Abstract Appl Anal. 2014;2014: Article ID 710158, 11p.
   Google Scholar
• Li X, Zhang M, Chen Y. An interior-point algorithm for P*(κ)-LCP based on a new trigonometric kernel function with a double barrier term. J Appl Math Comput. 2017;53(1):487–506.
   Web of Science ®Google Scholar
• Peyghami MR, 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. 2016;44:319–323.
   Web of Science ®Google Scholar
• Wolkowicz H, Saigal R, Vandenberghe L. Handbook of semidefinite programming: theory, algorithms and applications. Boston (MA): Kluwer Academic; 2000.
   Google Scholar
• McLinden L. The analogue of Moreau’s proximation theorem, with applications to the nonlinear complementarity problems. Pac J Math. 1980;88:101–161.
   Web of Science ®Google Scholar
• Gonzaga CC. Path-following methods for linear programming. SIAM J Optim. 1992;34(2):167–224.
   Web of Science ®Google Scholar
• Sonnevend G. An analytic center for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. In: Prakopa A, Szelezsan J, Strazicky B, editors, System modelling and optimization, Vol. 84, Lecture notes in control and information sciences; 2006. p. 866–876.
   Google Scholar
• Todd MJ. A study of search directions in primal-dual interior-point methods for semidefinite programming. Optim Methods Softw. 1999;11:1–46.
   Web of Science ®Google Scholar
• De Klerk E. Aspects of semidefinite programming: interior point algorithms and selected applications. Dordrecht: Kluwer Academic; 2002.
   Google Scholar
• Horn RA, Johnson CR. Topics in matrix analysis. Cambridge: Cambridge University Press; 1991.
   Google Scholar
• Lütkepohl H. Handbook of matrices. Chichester: Wiley; 1996.
   Google Scholar
• Wang GQ, Bai YQ, Roos C. Primal-dual interior point algorithm for semidefinite optimization based on a simple kernel function. J Math Model Algorithms. 2005;4:409–433.
   Google Scholar
• Roos C, Terlaky T, Vial J-P. Theory and algorithms for linear optimization: an interior point approach. New York (NY): Springer; 2005.
   Google Scholar
• Peng J. New design and analysis of interior point methods [PhD thesis]. The Netherlands: Faculty of Information Technology and Systems, Delft University of Technology; 2001.
   Google Scholar
• Borchers B. SDPLIB 1.2, A library of semidefinite programming test problems. Optim Methods Softw. 1999;11(1):683–690.
   Web of Science ®Google Scholar
• Touil I, Benterki D, Yassine A. A feasible primal-dual interior point method for linear semidefinite programming. J Comput Appl Math. 2016;312:216–230.
   Web of Science ®Google Scholar