Complexity analysis of primal-dual interior-point methods for convex quadratic programming based on a new twice parameterized kernel function

In this paper, we present primal-dual interior-point methods (IPMs) for convex quadratic programming (CQP) based on a new twice parameterized kernel function (KF) with a hyperbolic barrier term.  To our knowledge, this is the first KF with a twice parameterized hyperbolic barrier term. By using some conditions and simple analysis, we derive the currently best-known iteration bounds for large- and small-update methods, namely, \textbf{O}\big(\sqrt{n}\log n\log\frac{n}{\epsilon}\big) and \textbf{O}\big(\sqrt{n}\log\frac{n}{\epsilon}\big), respectively, with  special choices of the parameters. Finally, some numerical results regarding the practical performance of the new proposed KF are reported.

کلیدواژه ها:

Convex quadratic programming ، kernel function ، Interior-point methods ، Large- and small-update methods