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

Xiyao Luo; Gang Ma; Xiaodong Hu; Yuqing Fu

doi:doi:10.11648/j.ajam.20160406.18

| Peer-Reviewed

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

Xiyao Luo, Gang Ma, Xiaodong Hu, Yuqing Fu

Published in American Journal of Applied Mathematics (Volume 4, Issue 6)

Received: 2 November 2016 Accepted: 6 December 2016 Published: 26 December 2016

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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

Plain Text BibTeX RIS

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

Xiyao Luo

College of Fundamental Studies, Shanghai University of Engineering Science, Shanghai, China
Gang Ma

College of Fundamental Studies, Shanghai University of Engineering Science, Shanghai, China
Xiaodong Hu

College of Fundamental Studies, Shanghai University of Engineering Science, Shanghai, China
Yuqing Fu

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

Download PDF

Sections

Plain Text BibTeX RIS

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