Technical Report ERGO 19-012

An Interior Point–Proximal Method of Multipliers for Convex Quadratic Programming
S. Pougkakiotis and J. Gondzio

Abstract:

In this parer, we combine an infeasible Interior Point Method (IPM) with the Proximal Method of Multipliers (PMM). The resulting algorithm (IP–PMM) is interpreted as a primal–dual regularized IPM, suitable for solving linearly constrained convex quadratic programming problems. We apply few iterations of the interior point method to each sub–problem of the proximal method of multipliers. Once a satisfactory solution of the PMM sub–problem is found, we update the PMM parameters, form a new IPM neighbourhood and repeat this process. Given this framework, we prove polynomial complexity of the algorithm, under very mild assumptions. To our knowledge, this is the first polynomial complexity result for a primal–dual regularized IPM. Subsequently, we provide a robust implementation of the presented algorithm and test it over a set of small to large scale linear and convex quadratic programming problems. The numerical results demonstrate the benefits of using regularization in IPMs as well as the reliability of the method.

Download:

ERGO-19-012.pdf

Status:

Submitted for publication