| Peer-Reviewed

A Parametric Kernel Function Yielding the Best Known Iteration Bound of Interior-Point Methods for Semidefinite Optimization

Received: 2 November 2016     Accepted: 6 December 2016     Published: 26 December 2016
Views:       Downloads:
Abstract

In this paper, a class of large-update primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function are presented. The proposed kernel function is not only used for determining the search directions but also for measuring the distance between the given iterate and the center for the algorithms. By means of the Nesterov and Todd scaling scheme, the currently best known iteration bounds for large-update methods is established.

Published in American Journal of Applied Mathematics (Volume 4, Issue 6)
DOI 10.11648/j.ajam.20160406.18
Page(s) 316-323
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2016. Published by Science Publishing Group

Keywords

Interior-Point Methods, Semidefinite Optimization, Large-Update Methods, Polynomial Complexity

References
[1] Anjos M. F., Lasserre, J. B.: Handbook on Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications. International Series in Operational Research and Management Science. Volume 166, Springer, New York, USA (2012)
[2] De Klerk, E.: Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands (2002)
[3] Cai X. Z., Wang G. Q., Zhang Z. H.: Complexity analysis and numerical implementation of primal-dual interior-point methods for convex quadratic optimization based on a finite barrier. Numer. Algorithms 62(2), 289-306 (2013)
[4] Cho G. M.: Large-update primal-dual interior-point algorithm for semidefinite optimization. Pac. J. Optim. 11(1), 29-36 (2015)
[5] El Ghami M., Bai Y. Q., Roos C.: Kernel-function based Algorithms for semidefinite optimization. RAIRO Oper. Res. 43(2), 189-199 (2009)
[6] Lee Y. H., Cho Y. Y., Jin J. H., Cho G. M.: Interior-point algorithms for LO and SDO based on a new class of kernel functions. J. Nonlinear Convex Anal. 13(3), 555-573 (2012)
[7] Liu, H. W., Liu, C. H., Yang X. M.: New complexity analysis of a Mehrotra-type predictor-corrector algorithm for semidefinite programming. Optim. Methods Softw. 28(6), 1179-1194 (2013)
[8] Wang G. Q., Bai Y. Q.: A new primal-dual path-following interior-point algorithm for semidefinite optimization. J. Math. Anal. Appl. 353(1), 339-349 (2009)
[9] Wang G. Q., Bai Y. Q.: Primal-dual interior-point algorithms for convex quadratic semidefinite optimization. Nonlinear Anal. 71(7-8), 3389-3402 (2009)
[10] Wang G. Q., Bai Y. Q., Gao X. Y., Wang D. Z.: Improved complexity analysis of full Nesterov-Todd step interior-point methods for semidefinite optimization. J. Optim. Theory Appl. 165(1), 242-262 (2015)
[11] Wang G. Q., Bai Y. Q., Roos C.: Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function. J. Math. Model. Algorithms 4(4), 409-433 (2005)
[12] Wang G. Q., Zhu D. T.: A unified kernel function approach to primal-dual interior-point algorithms for convex quadratic SDO. Numer. Algorithms 57(4), 537-558 (2011)
[13] Yang X. M., Liu H. W., Zhang Y. K.: A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighbourhood for semidefinite programming. Int. J. Comput. Math. 91(5), 1082-1096 (2014)
[14] Zhang M. W.: A large-update interior-point algorithm for convex quadratic semidefinite optimization based on a new kernel function. Acta Math. Sin. (Engl. Ser.) 28(11), 2313-2328 (2012)
[15] Bai, Y. Q., El Ghami, M., Roos, C.: A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15(1), 101-128 (2004)
[16] Achache M.: A new parameterized kernel function for LO yielding the best known iteration bound for a large-update interior point algorithm. Afrika Mat. 27(3), 591-601 (2015)
[17] Bai, Y. Q., El Ghami, M., Roos, C.: A new efficient large-dual interior-point method based on a finite barrier. SIAM J. Optim. 13(3), 766-782 (2003)
[18] Cai X. Z., Wang G. Q., El Ghami M., Yue Y. J.: Complexity analysis of primal-dual interior-point methods for linear optimization based on a parametric kernel function with a trigonometric barrier term. Abstr. Appl. Anal. 2014, 710158 (2014)
[19] Wang G. Q., Bai Y. Q.: Interior-Point Methods for Symmetric Cone Complementarity Problems: Theoretical Analysis and Algorithm Implementation. Harbin Institute of Technology Press, Harbin (2014)
[20] Horn, R. A., Johnson, C. R.: Topics in Matrix Analysis. Cambridge University Press, UK (1991)
[21] Peng, J., Roos, C., Terlaky, T.: Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program. 93(1), 129-171 (2002)
[22] Zhang, Y.: On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8(2), 365-386 (1998)
[23] Roos, C., Terlaky, T., Vial, J.-Ph.: Theory and Algorithms for Linear Optimization. Springer, Chichester, UK (1st Edition, Theory and Algorithms for Linear Optimization. An Interior-Point Approach. John Wiley & Sons, 1997) (2005)
Cite This Article
  • APA Style

    Xiyao Luo, Gang Ma, Xiaodong Hu, Yuqing Fu. (2016). A Parametric Kernel Function Yielding the Best Known Iteration Bound of Interior-Point Methods for Semidefinite Optimization. American Journal of Applied Mathematics, 4(6), 316-323. https://doi.org/10.11648/j.ajam.20160406.18

    Copy | Download

    ACS Style

    Xiyao Luo; Gang Ma; Xiaodong Hu; Yuqing Fu. A Parametric Kernel Function Yielding the Best Known Iteration Bound of Interior-Point Methods for Semidefinite Optimization. Am. J. Appl. Math. 2016, 4(6), 316-323. doi: 10.11648/j.ajam.20160406.18

    Copy | Download

    AMA Style

    Xiyao Luo, Gang Ma, Xiaodong Hu, Yuqing Fu. A Parametric Kernel Function Yielding the Best Known Iteration Bound of Interior-Point Methods for Semidefinite Optimization. Am J Appl Math. 2016;4(6):316-323. doi: 10.11648/j.ajam.20160406.18

    Copy | Download

  • @article{10.11648/j.ajam.20160406.18,
      author = {Xiyao Luo and Gang Ma and Xiaodong Hu and Yuqing Fu},
      title = {A Parametric Kernel Function Yielding the Best Known Iteration Bound of Interior-Point Methods for Semidefinite Optimization},
      journal = {American Journal of Applied Mathematics},
      volume = {4},
      number = {6},
      pages = {316-323},
      doi = {10.11648/j.ajam.20160406.18},
      url = {https://doi.org/10.11648/j.ajam.20160406.18},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajam.20160406.18},
      abstract = {In this paper, a class of large-update primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function are presented. The proposed kernel function is not only used for determining the search directions but also for measuring the distance between the given iterate and the center for the algorithms. By means of the Nesterov and Todd scaling scheme, the currently best known iteration bounds for large-update methods is established.},
     year = {2016}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - A Parametric Kernel Function Yielding the Best Known Iteration Bound of Interior-Point Methods for Semidefinite Optimization
    AU  - Xiyao Luo
    AU  - Gang Ma
    AU  - Xiaodong Hu
    AU  - Yuqing Fu
    Y1  - 2016/12/26
    PY  - 2016
    N1  - https://doi.org/10.11648/j.ajam.20160406.18
    DO  - 10.11648/j.ajam.20160406.18
    T2  - American Journal of Applied Mathematics
    JF  - American Journal of Applied Mathematics
    JO  - American Journal of Applied Mathematics
    SP  - 316
    EP  - 323
    PB  - Science Publishing Group
    SN  - 2330-006X
    UR  - https://doi.org/10.11648/j.ajam.20160406.18
    AB  - In this paper, a class of large-update primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function are presented. The proposed kernel function is not only used for determining the search directions but also for measuring the distance between the given iterate and the center for the algorithms. By means of the Nesterov and Todd scaling scheme, the currently best known iteration bounds for large-update methods is established.
    VL  - 4
    IS  - 6
    ER  - 

    Copy | Download

Author Information
  • College of Fundamental Studies, Shanghai University of Engineering Science, Shanghai, China

  • College of Fundamental Studies, Shanghai University of Engineering Science, Shanghai, China

  • College of Fundamental Studies, Shanghai University of Engineering Science, Shanghai, China

  • College of Fundamental Studies, Shanghai University of Engineering Science, Shanghai, China

  • Sections