Abstract

In this paper we extended the results obtained for the first trigonometric kernel-function-based IPMs introduced by El Ghami et al. in [#!Trigonometry1!#] for LO to semidefinite optimization problems. The kernel function has a trigonometric Barrier Term. In this paper we generalize the analysis presented in the above paper for Semidefinit Optimization Problems (SDO). It is shown that the interior-point methods based on this function for large-update methods, the iteration bound is improved significantly. For small-update interior point methods the iteration bound is the best currently known bound for primal-dual interior point methods. The analysis for SDO deviates significantly from the analysis for linear optimization. Several new tools and techniques are derived in this paper.

Citation details of the article

Journal: International Journal of Applied Mathematics
Journal ISSN (Print): ISSN 1311-1728
Journal ISSN (Electronic): ISSN 1314-8060
Volume: 32
Issue: 2
Year: 2019

DOI: 10.12732/ijam.v32i2.13

Download Section

Download the full text of article from here.

You will need Adobe Acrobat reader. For more information and free download of the reader, please follow this link.

References

1. [1] F. Alizadeh, Combinatorial Optimization with Interior Point Methods and Semi-Definite Matrices, PhD thesis, University of Minnesota, Minneapolis, Minnesota, USA (1991).
2. [2] F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. on Optimization, 5 No 1 (1995), 13-51.
3. [3] Y.Q. Bai, M. El Ghami, C. Roos, A new efficient large-update primal-dual interior-point method based on a finite barrier, SIAM J. on Optimization, 13 No 3 (2003), 766-782.
4. [4] Y.Q. Bai, M. El Ghami, C. Roos, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization, SIAM J. on Optimization, 15 No 1 (2004), 101-128.
5. [5] X.Z. Cai, G.Q.Wang, M. El Ghami, Y.J. Yue, Complexity analysis of primal-dual interior-point methods for linear optimization based on a parametric kernel function with a trigonometric barrier term, Abstr. Appl. Anal. (2014), Art. # 710158.
6. [6] M. El Ghami, Primal-dual algorithms for semidefinit optimization problems based on generalized trigonometric barrier function, International J. of Pure and Applied Mathematics, 114, No 4 (2017), 797-818; doi: 10.12732/ijpam.v114i4.10. PRIMAL-DUAL ALGORITHMS FOR SEMIDEFINITE... 355
7. [7] M. El Ghami, G.Q. Wang, Interior-point methods for P∗(κ)-linear complementarity problems based on generalised trigonometric barier function. International J. of Applied Mathematics, 30, No 1 (2017), 11-33, doi: 10.12732/ijam.v30i1.2.
8. [8] M. El Ghami, Z.A. Guennoun, S. Bouali, T. Steihaug, Primal-dual iInterior-point methods for linear optimization based on a kernel function with trigonometric barrier term, J. of Computational and Applied Mathematics, 236, No 15 (2012), 3613-3623.
9. [9] M. El Ghami, A Kernel Function Approach for Interior Point Methods: Analysis and Implementation, LAP Lambert Academic Publishing, Germany, (2011).
10. [10] M. El Ghami, C. Roos, Generic primal-dual interior point methods based on a new kernel function, International J. RAIRO-Operations Research, 42, No 2 (2008), 199-213.
11. [11] R.A. Horn, C.R. Johnson, Topics in Matrix Analysis, Cambridge University Press, Cambridge (1991).
12. [12] Y.E. Nesterov, A.S. Nemirovskii, Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms, SIAM, Philadelphia, USA (1993).
13. [13] B. Kheirfam, Primal-dual interior-point algorithm for semidenite optimization based on a new kernel function with trigonometric barrier term, Numerical Algorithms, 61, No 4 (2012), 659-680.
14. [14] E. de Klerk, Aspects of Semidefintie Programming: Interior Point Algorithms and Selected Applications, Applied Optimization Book 65, Kluwer Academic Publishers, Dordrecht (2002).
15. [15] J. Peng, C. Roos, T. Terlaky, Self-Regularity: A New Paradigm for PrimalDual Interior-Point Algorithms, Princeton University Press (2002).
16. [16] Y.E. Nesterov, M.J. Todd, Self-scaled barriers and interior-point methods for convex programming, Mathematics of Operations Research, 22, No 1 (1997), 1-42.
17. [17] J.F. Sturm, S. Zhang, Symmetric primal-dual path following algorithms for semidefinite programming, Applied Numirical Mathematics, 29 (1999), 301–315. 356 M. El Ghami, G. Wang, T. Steihaug
18. [18] R.A. Horn, C.R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, UK (1985).
19. [19] W. Rudin, Principles of Mathematical Analysis, Mac-Graw Hill Book Company, New York (1978).
20. [20] C. Roos, T. Terlaky, J.-Ph. Vial, Theory and Algorithms for Linear Optimization. An Interior-Point Approach, Springer Science (2005).