\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

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

Abstract / Introduction Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 90C05, 90C51; Secondary: 65K05.

    Citation:

    \begin{equation} \\ \end{equation}
  • [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.

  • 加载中
SHARE

Article Metrics

HTML views() PDF downloads(158) Cited by(0)

Access History

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return