A Parametric Kernel Function Generating the best Known Iteration Bound for Large-Update Methods for CQSDO
Abstract
In this paper, we propose a large-update primal-dual interior point algorithm for convex quadratic semidefiniteoptimization (CQSDO) based on a new parametric kernel function. This kernel function is a parameterized version of the kernel function introduced by M.W. Zhang (Acta Mathematica Sinica. 28: 2313-2328, 2012) for CQSDO. The investigation according to it generating the best known iteration bound O for large-update methods. Thus improves the iteration bound obtained by Zhang for large-update methods. Finally, we present few numerical results to show the efficiency of the proposed algorithm.References
M. Achache, A new parameterized kernel function for LO yielding the best known iteration bound for a large-update interior point algorithm, Afrika Matematika, vol. 27, no. 3, pp. 591–601, 2016.
M. Achache, A polynomial-time weighted path-following interior-point algorithm for linear optimization, Asian-European Journal of Mathematics, vol. 13, no. 2, 2050038, 2020.
M. Achache, Complexity analysis of an interior point algorithm for the semidefinite optimization based on a kernel function with a double barrier term, Acta Mathematica Sinica, English Series, vol. 31, no. 3, pp. 543–556, 2015.
M. Achache, and L. Guerra, A full-Nesterov-Todd-step primal-dual interior point algorithm for convex quadratic semidefinite optimization, Computational and Applied Mathematics, 231, pp. 581–590, 2014.
M. Achache, and N. Tabchouche, A full-step feasible interior-point algorithm for monotone horizontal linear complementarity problems, Optimization Letters, vol. 13, no. 5, pp. 1039–1057, 2019.
M. Achache, and N. Tabchouche, Complexity analysis and numerical implementation of large-update interior-point methods for SDLCP based on a new parametric barrier kernel function, Optimization, Journal of Mathematical Programming and Operations Research, vol. 67, no. 8, pp. 1211-1230, 2018.
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, vol. 15, no. 1, pp. 101–128, 2004.
Y.Q. Bai, J.L. Guo, and C. Roos, A new kernel function yielding the best known iteration bounds for primal-dual interior-point algorithm, Acta Mathematica Sinica, vol. 25, no. 12, pp. 2169–2178, 2009.
Y.Q. Bai, G. Lesaja, C. Roos, G.Q.Wang, and M. El Ghami, A class of large-and small-update primal-dual interior-point algorithm for linear optimization, Journal of optimization theory and application, vol. 138, no. 3, pp. 341–359, 2008.
X.Z. Cai, L.Wu, Y.J. Yue, M.M. Li, and G.Q.Wang, Kernel-function based primal-dual interior-point methods for convex quadratic optimization over symmetric cone, Journal of inequalities and applications, 308, 22 pp, 2014.
M. El Ghami, New primal-dual interior-point methods based on kernel functions, Phd thesis. Delft University, Netherland, 2005.
A.R. Horn, and C.R. Johnson, Topics in Matrix Analysis, Cambridge University Press, 1999.
M. Kojima, M. Shida, and S. Shindoh, Search directions in the SDP and monotone SDLCP: Generalization and inexact computation, Mathematical Programming, 85, pp. 51–80, 1999.
J.W. Nie, and Y.X. Yuan, A potential reduction algorithm for an extended SDP problem, Science in China (Series A), vol. 43, no. 1, pp. 35–46, 2000.
J. Peng, C. Roos, and T. Terlaky, Self-regular functions and new search directions for linear and semidefinite optimization, Mathematical Programming, 93, pp. 129–171, 2002.
J. Peng, C. Roos, and T. Terlaky, Self-regularity. A new paradigm for Primal-Dual Interior Point Algorithm, Princeton University Press. Princeton, 2002.
K.C. Toh, An inexact primal-dual path following algorithm for convex quadratic SDP, Mathematical Programming, vol. 112, no. 1, pp. 221–254, 2008.
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, vol. 353, no. 1, pp. 339-349, 2009.
G.Q.Wang, and Y.Q. Bai, Primal-dual interior-point algorithms for convex quadratic semidefinite optimization, Nonlinear analysis: theory, methods & applications, 71 (7-8), pp. 3389-3402, 2009.
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, vol. 4, no. 4, pp. 409-433, 2005.
G.Q. Wang, Z.H. Zhang, and D.T. Zhu, On extending primal-dual interior-point method for linear optimization to convex quadratic cone optimization, Numerical functional analysis and optimization, vol. 34, no. 5, pp. 576-603, 2013.
G.Q. Wang, and D.T. Zhu, A unified kernel function approach to primal-dual interior-point algorithms for convex quadratic SDO, Numerical Algorithms, vol. 57, no. 4, pp. 537-558, 2011.
M.W. Zhang, A large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function, Acta Mathematica Sinica, vol. 28, no. 11, pp. 2313-2328, 2012.
L. Zhang. Y. Xu, and Z. Jin, An efficient algorithm for convex quadratic semi-definite optimization, Numerical Algebra. Control and Optimization, vol. 2, no. 1, pp. 129–144, 2012.
D. Zhao, and M. W. Zhang, A primal-dual large-update interior point algorithm for semi-definite optimization based on a new parametric kernel function, Statistics, Optimization and information computing, 1, pp. 41–61, 2013.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
