A Weighted-path Following Interior-point Algorithm for Convex Quadratic Optimization Based on Modified Search Directions
Abstract
Getting a perfectly centered initial point for feasible path-following interior-point algorithms is a hard practical task. Therefore, it is worth to analyze other cases when the starting point is not necessarily centered. In this paper, we propose a short-step weighted-path following interior-point algorithm (IPA) for solving convex quadratic optimization (CQO). The latter is based on a modified search direction which is obtained by the technique of algebraically equivalent transformation (AET) introduced by a new univariate function to the Newton system which defines the weighted-path. At each iteration, the algorithm uses only full-Newton steps and the strategy of the central-path for tracing approximately the weighted-path. We show that the algorithm is well-defined and converges locally quadratically to an optimal solution of CQO. Moreover, we obtain the currently best known iteration bound, namely, $\mathcal{O}\left(\sqrt{n}\log \dfrac{n}{\epsilon}\right)$ which is as good as the bound for linear optimization analogue. Some numerical results are given to evaluate the efffficiency of the algorithm.References
M. Achache, A new primal-dual path-following method for convex quadratic programming, Comput. Appl. Math.,
: 97-110, 2006.
M. Achache, Complexity analysis of a weighted-full-Newton step interior-point algorithm for P∗(κ)-LCP, RAIROOper. Res. 50: 131-143, 2016.
M. Achache, A weighted path-following method for the linear complementarity problem, Studia Univ. Babes-Bolyai.
Ser. Inform. 49(1): 61-73, 2004.
M. Achache, A weighted full-Newton step primal-dual interior point algorithm for convex quadratic optimization,
Statistics, Optimization & Information Computing, (2): 21-32, 2014.
M. Achache, and M. Goutali, A primal-dual interior-point algorithm for convex quadratic programs, Studia Univ.
Babes-Bolyai. Ser. Inform. LVII(1): 48-58, 2012.
M. Achache, and M. Goutali, Complexity analysis and numerical implementation of a full-Newton step interior-point
algorithm for LCCO, Numer. Algorithms. 70: 393-405, 2015.
M. Achache, and R. Khebchache, A full-Newton step feasible weighted primal-dual interior point algorithm for
monotone LCP, Afrika Matematika. 26: 139-151, 2015.
M. Achache, Complexity analysis and numerical implementation of a short-step primal-dual algorithm for linear
complementarity problems, Appl. Math. Comput., 216(7), 1889–1895, 2010.
Zs. Darvay, New interior-point algorithms for linear optimization, Advanced Modeling Optimization. 5(1): 51-92,
Zs. Darvay, A weighted-path-following method for linear optimization, Studia Universitatis Babes-Bolyai Series
Informatica, 47(2): 3-12, 2002.
J. Ding, and T.Y. Li, An algorithm based on weighted logarithmic barrier functions for linear complementarity
problems, Arabian Journal for Science and Engineering, 15(4): 679-685, 1990.
S. Fathi-Hafshejani, and Z. Moaberfard, An interior-point algorithm for linearly constrained convex optimization
based on kernel function and application in non-negative matrix factorization, Optim Eng, 21(3): 1019-1051, 2020.
L. Goran, G. Wang, and A. Oganian, A Full Nesterov-Todd Step Infeasible Interior-point Method for Symmetric
Optimization in the Wider Neighborhood of the Central Path, Statistics, Optimization & Information Computing,
(2), 250-267, 2021.
L. Guerra, and M. Achache, A parametric Kernel Function Generating the best Known Iteration Bound for LargeUpdate Methods for CQSDO, Statistics, Optimization & Information Computing,(8): 876-889, 2020.
B. Jansen, C, Roos, T. Terlaky, and J.-Ph. Vial, Primal-dual target-following algorithms for linear programming,
Annals of Operations Research 62: 197-231, 1996.
H. Mansouri, M. Pirhaji, and M. Zanglabadi, A weighted-path-following interior-point algorithm for cartesian P∗(κ)-
LCP over symmetric cone, Korean Math. Soc.32, (3): 765-778, 2017.
P.R . Rigó, New trends in algebraic equivalent transformation of the central-path and its applications, PhD thesis,
Budapest University of Technology and Economics, Institute of Mathematics, Hungary, 2020.
C. Roos, T. Terlaky, and J.-Ph. Vial, Theory and Algorithms for Linear Optimization. An interior Point Approach,
John-Wiley and Sons, Chichester, UK, 1997.
G.Q. Wang, Y.J. Yue, and X.Z. Cai, A weighted path-following method for monotone horizontal linear complementarity problem Fuzzy Information and Engineering. 54: 479-487, 2009.
G.Q. Wang, Y.J. Yue, and X.Z. Cai, Weighted path-following method for monotone mixed linear complementarity
problem, Fuzzy Information and Engineering. 4: 435-445, 2009.
S.J. Wright, Primal-dual Interior-Point Methods, Copyright by SIAM, 1997.
Y. Ye, Interior-Point Algorithm. Theory and Analysis, New-York: John Wiley, 1997.
M. Zhang, YQ. Bai, and GQ. Wang, A new primal-dual path-following interior-point algorithm for linearly constrained
convex optimization, Journal of Shanghai University 12(6): 475-480, 2008.
D. Zhao, and M. Zhang, A primal-dual large-update interior-point algorithm for semi-definite optimization based on
a new kernel function, Statistics, Optimization & Information Computing, 1(1), 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).
