Volume 4, Issue 6, December 2016, Page: 316-323
A Parametric Kernel Function Yielding the Best Known Iteration Bound of Interior-Point Methods for Semidefinite Optimization
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
Received: Nov. 2, 2016;       Accepted: Dec. 6, 2016;       Published: Dec. 26, 2016
DOI: 10.11648/j.ajam.20160406.18      View  2728      Downloads  95
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.
Keywords
Interior-Point Methods, Semidefinite Optimization, Large-Update Methods, Polynomial Complexity
To cite this article
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, American Journal of Applied Mathematics. Vol. 4, No. 6, 2016, pp. 316-323. doi: 10.11648/j.ajam.20160406.18
Copyright
Copyright © 2016 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Reference
[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)
Browse journals by subject