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

Guoqiang  Wang; Zhongchen  Wu; Zhongtuan  Zheng; Xinzhong  Cai

doi:10.3934/naco.2015.5.101

Article Contents

2015, Volume 5, Issue 2: 101-113. Doi: 10.3934/naco.2015.5.101

This issue Previous Article Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties Next Article A smooth QP-free algorithm without a penalty function or a filter for mathematical programs with complementarity constraints

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

Received: September 30, 2014

Revised: April 30, 2015

Published: May 2015

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90C05, 90C51; Secondary: 65K05.

Citation:

Related Papers

Cited by

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.