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 & 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]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115
[2]

Xin Guo, Lexin Li, Qiang Wu. Modeling interactive components by coordinate kernel polynomial models. Mathematical Foundations of Computing, 2020, 3 (4) : 263-277. doi: 10.3934/mfc.2020010
[3]

Qiang Long, Xue Wu, Changzhi Wu. Non-dominated sorting methods for multi-objective optimization: Review and numerical comparison. Journal of Industrial & Management Optimization, 2021, 17 (2) : 1001-1023. doi: 10.3934/jimo.2020009
[4]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443
[5]

Philippe G. Ciarlet, Liliana Gratie, Cristinel Mardare. Intrinsic methods in elasticity: a mathematical survey. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 133-164. doi: 10.3934/dcds.2009.23.133
[6]

Xing-Bin Pan. Variational and operator methods for Maxwell-Stokes system. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3909-3955. doi: 10.3934/dcds.2020036
[7]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117
[8]

Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079
[9]

Xin Guo, Lei Shi. Preface of the special issue on analysis in data science: Methods and applications. Mathematical Foundations of Computing, 2020, 3 (4) : i-ii. doi: 10.3934/mfc.2020026
[10]

Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171
[11]

Bin Wang, Lin Mu. Viscosity robust weak Galerkin finite element methods for Stokes problems. Electronic Research Archive, 2021, 29 (1) : 1881-1895. doi: 10.3934/era.2020096
[12]

Jiwei Jia, Young-Ju Lee, Yue Feng, Zichan Wang, Zhongshu Zhao. Hybridized weak Galerkin finite element methods for Brinkman equations. Electronic Research Archive, , () : -. doi: 10.3934/era.2020126
[13]

Baoli Yin, Yang Liu, Hong Li, Zhimin Zhang. Approximation methods for the distributed order calculus using the convolution quadrature. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1447-1468. doi: 10.3934/dcdsb.2020168
[14]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017
[15]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073
[16]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105
[17]

Yuyuan Ouyang, Trevor Squires. Some worst-case datasets of deterministic first-order methods for solving binary logistic regression. Inverse Problems & Imaging, 2021, 15 (1) : 63-77. doi: 10.3934/ipi.2020047
[18]

Ömer Arslan, Selçuk Kürşat İşleyen. A model and two heuristic methods for The Multi-Product Inventory-Location-Routing Problem with heterogeneous fleet. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021002
[19]

Tetsuya Ishiwata, Takeshi Ohtsuka. Numerical analysis of an ODE and a level set methods for evolving spirals by crystalline eikonal-curvature flow. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 893-907. doi: 10.3934/dcdss.2020390
[20]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences