American Institute of Mathematical Sciences

Advanced
  • 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

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

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 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: 

Tools

Metrics

  • PDF downloads (142)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy