# American Institute of Mathematical Sciences

• Previous Article
A smooth QP-free algorithm without a penalty function or a filter for mathematical programs with complementarity constraints
• NACO Home
• This Issue
• Next Article
Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
2015, 5(2): 101-113. doi: 10.3934/naco.2015.5.101

## Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term

 1 College of Fundamental Studies, Shanghai University of Engineering Science, Shanghai 201620, China, China, China, China

Received  October 2014 Revised  May 2015 Published  June 2015

In this paper, we present a class of large- and small-update primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. For both versions of the kernel-based interior-point methods, the worst case iteration bounds are established, namely, $O(n^{\frac{2}{3}}\log\frac{n}{\varepsilon})$ and $O(\sqrt{n}\log\frac{n}{\varepsilon})$, respectively. These results match the ones obtained in the linear optimization case.
Citation: Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101
##### References:
 [1] M. Achache and L. Guerra, A full Nesterov-Todd step feasible primal-dual interior-point algorithm for convex quadratic semidefinite optimization, Applied Mathematics and Computation, 231 (2014), 581-590. doi: 10.1016/j.amc.2013.12.070. [2] Y. Q. Bai, M. El Ghami and C. Roos, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization, SIAM Journal on Optimization, 15 (2004), 101-128. doi: 10.1137/S1052623403423114. [3] X. Z. Cai, G. Q. Wang, M. El Ghami and 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, Abstract and Applied Analysis, 2014 (2014), 710158. doi: 10.1155/2014/710158. [4] B. K. Choi. and G. M. Lee, On complexity analysis of the primal-dual interior-point method for semidefinite optimization problem based on a new proximity function, Nonlinear Analysis, Theory, Methods & Applications, 71 (2009), 2628-2640. doi: 10.1016/j.na.2009.05.078. [5] Zs. Darvay, New interior point algorithms in linear programming, Advanced Modeling and Optimization, 5 (2003), 51-92. [6] E. De Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2002. doi: 10.1007/b105286. [7] M. El Ghami, Z. A. Guennounb, S. Bouali and T. Steihaug, Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term, Journal of Computational and Applied Mathematics, 236 (2012), 3613-3623. doi: 10.1016/j.cam.2011.05.036. [8] M. El Ghami, C. Roos and T. Steihaug, A generic primal-dual interior-point method for semidefinite optimization based on a new class of kernel functions, Optimization Methods & Software, 25 (2010), 387-403. doi: 10.1080/10556780903239048. [9] R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, UK, 1991. doi: 10.1017/CBO9780511840371. [10] B. Kheirfam, Simplified infeasible interior-point algorithm for SDO using full Nesterov-Todd step, Numerical Algorithms, 59 (2012), 589-606. doi: 10.1007/s11075-011-9506-1. [11] M. Kojima, M. Shida and S. Shindoh, Local convergence of predictor-corrector infeasible-interior-point method for SDPs and SDLCPs, Mathematical Programming, 80 (1998), 129-160. doi: 10.1007/BF01581723. [12] H. W. Liu, C. H. Liu and X. M. Yang, New complexity analysis of a Mehrotra-type predictor-corrector algorithm for semidefinite programming, Optimization Methods & Software, 28 (2013), 1179-1194. doi: 10.1080/10556788.2012.679270. [13] H. Mansouri and C. Roos, A new full-Newton step O(n) infeasible interior-point algorithm for semidefinite optimization, Numerical Algorithms, 52 (2009), 225-255. doi: 10.1007/s11075-009-9270-7. [14] J. Peng, C. Roos and T. Terlaky, Self-regular functions and new search directions for linear and semidefinite optimization, Mathematical Programming, 93 (2002), 129-171. doi: 10.1007/s101070200296. [15] M. R. Peyghami, An interior-point approach for semidefinite optimization using new proximity functions, Asia-Pacific Journal of Operational Research, 26 (2009), 365-382. doi: 10.1142/S0217595909002250. [16] M. R. Peyghami and S. F. Hafshejani, Complexity analysis of an interior-point algorithm for linear optimization based on a new proximity function, Numerical Algorithms, 67 (2014), 33-48. doi: 10.1007/s11075-013-9772-1. [17] M. R. Peyghami, S. F. Hafshejani and L. Shirvani, Complexity of interior-point methods for linear optimization based on a new trigonometric kernel function, Journal of Computational and Applied Mathematics, 255 (2014), 74-85. doi: 10.1016/j.cam.2013.04.039. [18] C. Roos, T. Terlaky and J.-Ph. Vial, Theory and Algorithms for Linear Optimization, Springer, New York, 2005. [19] G. Q. Wang and Y. Q. Bai, A new primal-dual path-following interior-point algorithm for semidefinite optimization, Journal of Mathematical Analysis and Applications, 353 (2009), 339-349. doi: 10.1016/j.jmaa.2008.12.016. [20] G. Q. Wang, Y. Q. Bai and C. Roos, Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function, Journal of Mathematical Modelling and Algorithms, 4 (2005), 409-433. [21] G. Q. Wang and D. T. Zhu., A unified kernel function approach to primal-dual interior-point algorithms for convex quadratic SDO, Numerical Algorithms, 57 (2011), 537-558. doi: 10.1007/s11075-010-9444-3. [22] L. P. Zhang, Y. H. Xu and Z. J. Jin, An efficient algorithm for convex quadratic semidefinite optimization, Numerical Algebra, Control and Optimization, 2 (2012), 129-144. doi: 10.3934/naco.2012.2.129. [23] M. W. Zhang, A large-update interior-point algorithm for convex quadratic semidefinite optimization based on a new kernel function, Acta Mathematica Sinica (English Series), 28 (2012), 2313-2328. doi: 10.1007/s10114-012-0194-0. [24] Y. Zhang, On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming, SIAM Journal on Optimization, 8 (1998), 365-386. doi: 10.1137/S1052623495296115.

show all references

##### References:
 [1] M. Achache and L. Guerra, A full Nesterov-Todd step feasible primal-dual interior-point algorithm for convex quadratic semidefinite optimization, Applied Mathematics and Computation, 231 (2014), 581-590. doi: 10.1016/j.amc.2013.12.070. [2] Y. Q. Bai, M. El Ghami and C. Roos, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization, SIAM Journal on Optimization, 15 (2004), 101-128. doi: 10.1137/S1052623403423114. [3] X. Z. Cai, G. Q. Wang, M. El Ghami and 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, Abstract and Applied Analysis, 2014 (2014), 710158. doi: 10.1155/2014/710158. [4] B. K. Choi. and G. M. Lee, On complexity analysis of the primal-dual interior-point method for semidefinite optimization problem based on a new proximity function, Nonlinear Analysis, Theory, Methods & Applications, 71 (2009), 2628-2640. doi: 10.1016/j.na.2009.05.078. [5] Zs. Darvay, New interior point algorithms in linear programming, Advanced Modeling and Optimization, 5 (2003), 51-92. [6] E. De Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2002. doi: 10.1007/b105286. [7] M. El Ghami, Z. A. Guennounb, S. Bouali and T. Steihaug, Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term, Journal of Computational and Applied Mathematics, 236 (2012), 3613-3623. doi: 10.1016/j.cam.2011.05.036. [8] M. El Ghami, C. Roos and T. Steihaug, A generic primal-dual interior-point method for semidefinite optimization based on a new class of kernel functions, Optimization Methods & Software, 25 (2010), 387-403. doi: 10.1080/10556780903239048. [9] R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, UK, 1991. doi: 10.1017/CBO9780511840371. [10] B. Kheirfam, Simplified infeasible interior-point algorithm for SDO using full Nesterov-Todd step, Numerical Algorithms, 59 (2012), 589-606. doi: 10.1007/s11075-011-9506-1. [11] M. Kojima, M. Shida and S. Shindoh, Local convergence of predictor-corrector infeasible-interior-point method for SDPs and SDLCPs, Mathematical Programming, 80 (1998), 129-160. doi: 10.1007/BF01581723. [12] H. W. Liu, C. H. Liu and X. M. Yang, New complexity analysis of a Mehrotra-type predictor-corrector algorithm for semidefinite programming, Optimization Methods & Software, 28 (2013), 1179-1194. doi: 10.1080/10556788.2012.679270. [13] H. Mansouri and C. Roos, A new full-Newton step O(n) infeasible interior-point algorithm for semidefinite optimization, Numerical Algorithms, 52 (2009), 225-255. doi: 10.1007/s11075-009-9270-7. [14] J. Peng, C. Roos and T. Terlaky, Self-regular functions and new search directions for linear and semidefinite optimization, Mathematical Programming, 93 (2002), 129-171. doi: 10.1007/s101070200296. [15] M. R. Peyghami, An interior-point approach for semidefinite optimization using new proximity functions, Asia-Pacific Journal of Operational Research, 26 (2009), 365-382. doi: 10.1142/S0217595909002250. [16] M. R. Peyghami and S. F. Hafshejani, Complexity analysis of an interior-point algorithm for linear optimization based on a new proximity function, Numerical Algorithms, 67 (2014), 33-48. doi: 10.1007/s11075-013-9772-1. [17] M. R. Peyghami, S. F. Hafshejani and L. Shirvani, Complexity of interior-point methods for linear optimization based on a new trigonometric kernel function, Journal of Computational and Applied Mathematics, 255 (2014), 74-85. doi: 10.1016/j.cam.2013.04.039. [18] C. Roos, T. Terlaky and J.-Ph. Vial, Theory and Algorithms for Linear Optimization, Springer, New York, 2005. [19] G. Q. Wang and Y. Q. Bai, A new primal-dual path-following interior-point algorithm for semidefinite optimization, Journal of Mathematical Analysis and Applications, 353 (2009), 339-349. doi: 10.1016/j.jmaa.2008.12.016. [20] G. Q. Wang, Y. Q. Bai and C. Roos, Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function, Journal of Mathematical Modelling and Algorithms, 4 (2005), 409-433. [21] G. Q. Wang and D. T. Zhu., A unified kernel function approach to primal-dual interior-point algorithms for convex quadratic SDO, Numerical Algorithms, 57 (2011), 537-558. doi: 10.1007/s11075-010-9444-3. [22] L. P. Zhang, Y. H. Xu and Z. J. Jin, An efficient algorithm for convex quadratic semidefinite optimization, Numerical Algebra, Control and Optimization, 2 (2012), 129-144. doi: 10.3934/naco.2012.2.129. [23] M. W. Zhang, A large-update interior-point algorithm for convex quadratic semidefinite optimization based on a new kernel function, Acta Mathematica Sinica (English Series), 28 (2012), 2313-2328. doi: 10.1007/s10114-012-0194-0. [24] Y. Zhang, On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming, SIAM Journal on Optimization, 8 (1998), 365-386. doi: 10.1137/S1052623495296115.
 [1] Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37 [2] Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022003 [3] Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control and Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601 [4] Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control and Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015 [5] Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial and Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739 [6] Jie Sun. On methods for solving nonlinear semidefinite optimization problems. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 1-14. doi: 10.3934/naco.2011.1.1 [7] Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211 [8] Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial and Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949 [9] Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial and Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891 [10] Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial and Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103 [11] Yanxing Cui, Chuanlong Wang, Ruiping Wen. On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 863-873. doi: 10.3934/naco.2012.2.863 [12] Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control and Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024 [13] Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial and Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190 [14] Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011 [15] Hong Seng Sim, Chuei Yee Chen, Wah June Leong, Jiao Li. Nonmonotone spectral gradient method based on memoryless symmetric rank-one update for large-scale unconstrained optimization. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021143 [16] Jake Bouvrie, Boumediene Hamzi. Kernel methods for the approximation of some key quantities of nonlinear systems. Journal of Computational Dynamics, 2017, 4 (1&2) : 1-19. doi: 10.3934/jcd.2017001 [17] Yin Yang, Yunqing Huang. Spectral Jacobi-Galerkin methods and iterated methods for Fredholm integral equations of the second kind with weakly singular kernel. Discrete and Continuous Dynamical Systems - S, 2019, 12 (3) : 685-702. doi: 10.3934/dcdss.2019043 [18] Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control and Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011 [19] Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1505-1517. doi: 10.3934/jimo.2021030 [20] Mauro Pontani. Orbital transfers: optimization methods and recent results. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 435-485. doi: 10.3934/naco.2011.1.435

Impact Factor: