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

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

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

Guoqiang Wang ^1, , Zhongchen Wu ^1, , Zhongtuan Zheng ^1, and Xinzhong Cai ^1,

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

Abstract
Related Papers

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: large- and small-update methods, kernel function, semidefinite optimization, Interior-point methods, polynomial complexity..

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

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 & 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. doi: 10.1016/j.amc.2013.12.070. Google Scholar*
[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. doi: 10.1137/S1052623403423114. Google Scholar
[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). doi: 10.1155/2014/710158. Google Scholar*
[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, 71 (2009), 2628. doi: 10.1016/j.na.2009.05.078. Google Scholar
[5]	Zs. Darvay, New interior point algorithms in linear programming,, Advanced Modeling and Optimization, 5 (2003), 51. Google Scholar
[6]	E. De Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications,, Kluwer Academic Publishers, (2002). doi: 10.1007/b105286. Google Scholar
[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. doi: 10.1016/j.cam.2011.05.036. Google Scholar*
[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. doi: 10.1080/10556780903239048. Google Scholar
[9]	R. A. Horn and C. R. Johnson, Topics in Matrix Analysis,, Cambridge University Press, (1991). doi: 10.1017/CBO9780511840371. Google Scholar
[10]	B. Kheirfam, Simplified infeasible interior-point algorithm for SDO using full Nesterov-Todd step,, Numerical Algorithms, 59 (2012), 589. doi: 10.1007/s11075-011-9506-1. Google Scholar
[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. doi: 10.1007/BF01581723. Google Scholar
[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. doi: 10.1080/10556788.2012.679270. Google Scholar
[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. doi: 10.1007/s11075-009-9270-7. Google Scholar
[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. doi: 10.1007/s101070200296. Google Scholar
[15]	M. R. Peyghami, An interior-point approach for semidefinite optimization using new proximity functions,, Asia-Pacific Journal of Operational Research, 26 (2009), 365. doi: 10.1142/S0217595909002250. Google Scholar
[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. doi: 10.1007/s11075-013-9772-1. Google Scholar
[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. doi: 10.1016/j.cam.2013.04.039. Google Scholar*
[18]	C. Roos, T. Terlaky and J.-Ph. Vial, Theory and Algorithms for Linear Optimization,, Springer, (2005). Google Scholar
[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. doi: 10.1016/j.jmaa.2008.12.016. Google Scholar*
[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. Google Scholar
[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. doi: 10.1007/s11075-010-9444-3. Google Scholar
[22]	L. P. Zhang, Y. H. Xu and Z. J. Jin, An efficient algorithm for convex quadratic semidefinite optimization,, Numerical Algebra, 2 (2012), 129. doi: 10.3934/naco.2012.2.129. Google Scholar
[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. doi: 10.1007/s10114-012-0194-0. Google Scholar
[24]	Y. Zhang, On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming,, SIAM Journal on Optimization, 8 (1998), 365. doi: 10.1137/S1052623495296115. Google Scholar

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. doi: 10.1016/j.amc.2013.12.070. Google Scholar*
[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. doi: 10.1137/S1052623403423114. Google Scholar
[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). doi: 10.1155/2014/710158. Google Scholar*
[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, 71 (2009), 2628. doi: 10.1016/j.na.2009.05.078. Google Scholar
[5]	Zs. Darvay, New interior point algorithms in linear programming,, Advanced Modeling and Optimization, 5 (2003), 51. Google Scholar
[6]	E. De Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications,, Kluwer Academic Publishers, (2002). doi: 10.1007/b105286. Google Scholar
[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. doi: 10.1016/j.cam.2011.05.036. Google Scholar*
[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. doi: 10.1080/10556780903239048. Google Scholar
[9]	R. A. Horn and C. R. Johnson, Topics in Matrix Analysis,, Cambridge University Press, (1991). doi: 10.1017/CBO9780511840371. Google Scholar
[10]	B. Kheirfam, Simplified infeasible interior-point algorithm for SDO using full Nesterov-Todd step,, Numerical Algorithms, 59 (2012), 589. doi: 10.1007/s11075-011-9506-1. Google Scholar
[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. doi: 10.1007/BF01581723. Google Scholar
[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. doi: 10.1080/10556788.2012.679270. Google Scholar
[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. doi: 10.1007/s11075-009-9270-7. Google Scholar
[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. doi: 10.1007/s101070200296. Google Scholar
[15]	M. R. Peyghami, An interior-point approach for semidefinite optimization using new proximity functions,, Asia-Pacific Journal of Operational Research, 26 (2009), 365. doi: 10.1142/S0217595909002250. Google Scholar
[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. doi: 10.1007/s11075-013-9772-1. Google Scholar
[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. doi: 10.1016/j.cam.2013.04.039. Google Scholar*
[18]	C. Roos, T. Terlaky and J.-Ph. Vial, Theory and Algorithms for Linear Optimization,, Springer, (2005). Google Scholar
[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. doi: 10.1016/j.jmaa.2008.12.016. Google Scholar*
[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. Google Scholar
[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. doi: 10.1007/s11075-010-9444-3. Google Scholar
[22]	L. P. Zhang, Y. H. Xu and Z. J. Jin, An efficient algorithm for convex quadratic semidefinite optimization,, Numerical Algebra, 2 (2012), 129. doi: 10.3934/naco.2012.2.129. Google Scholar
[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. doi: 10.1007/s10114-012-0194-0. Google Scholar
[24]	Y. Zhang, On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming,, SIAM Journal on Optimization, 8 (1998), 365. doi: 10.1137/S1052623495296115. Google Scholar

[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 & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[2]	Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601
[3]	Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015
[4]	Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739
[5]	Jie Sun. On methods for solving nonlinear semidefinite optimization problems. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 1-14. doi: 10.3934/naco.2011.1.1
[6]	Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211
[7]	Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial & Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949
[8]	Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891
[9]	Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial & Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103
[10]	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 & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[11]	Yanxing Cui, Chuanlong Wang, Ruiping Wen. On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 863-873. doi: 10.3934/naco.2012.2.863
[12]	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 & Management Optimization, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2018190
[13]	Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011
[14]	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
[15]	Yin Yang, Yunqing Huang. Spectral Jacobi-Galerkin methods and iterated methods for Fredholm integral equations of the second kind with weakly singular kernel. Discrete & Continuous Dynamical Systems - S, 2019, 12 (3) : 685-702. doi: 10.3934/dcdss.2019043
[16]	Mauro Pontani. Orbital transfers: optimization methods and recent results. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 435-485. doi: 10.3934/naco.2011.1.435
[17]	Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011
[18]	Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial & Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381
[19]	Björn Sandstede, Arnd Scheel. Evans function and blow-up methods in critical eigenvalue problems. Discrete & Continuous Dynamical Systems - A, 2004, 10 (4) : 941-964. doi: 10.3934/dcds.2004.10.941
[20]	Martino Bardi, Annalisa Cesaroni, Daria Ghilli. Large deviations for some fast stochastic volatility models by viscosity methods. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 3965-3988. doi: 10.3934/dcds.2015.35.3965

Impact Factor:

American Institute of Mathematical Sciences