An interior point-proximal method of multipliers for convex quadratic programming
An interior point-proximal method of multipliers for convex quadratic programming
复制标题
DOI：
10.1007/s10589-020-00240-9
复制
发表时间：
2019-04
影响因子：
2.2
通讯作者：
Spyridon Pougkakiotis;J. Gondzio
中科院分区：
文献类型：
--
作者：
Spyridon Pougkakiotis;J. Gondzio
本文将不可行内点法(IPM)与乘子近似法(PMM)相结合。由此得到的算法(IP-PMM)被解释为一种原始-对偶正则化的IPM，适用于求解线性约束凸二次规划问题。对于乘子近似法的每个子问题，我们都采用了较少的内点法迭代。一旦找到PMM子问题的满意解，我们更新PMM参数，形成新的IPM邻域，并重复该过程。在此框架下，我们在标准假设下证明了算法的多项式复杂性。据我们所知，这是原-对偶正则IPM的第一个多项式复杂性结果。该算法通过使用单个惩罚参数来指导，即对数障碍的惩罚参数。换言之，我们证明了IP-PMM继承了IPMS的多项式复杂性，以及PMM子问题的严格凸性。惩罚参数的更新是由IPM控制的，因此是很好地调整的，并且不依赖于所解决的问题。此外，我们还研究了该方法应用于不可行问题时的行为，并给出了不可行的必要条件。后者用于构建不可行检测机制。随后，我们给出了算法的健壮性实现，并在一组由小到大的线性和凸二次规划问题上对其进行了测试。数值结果表明了正则化方法在IPMS中应用的好处以及该方法的可靠性。
In this paper 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 standard assumptions. To our knowledge, this is the first polynomial complexity result for a primal-dual regularized IPM. The algorithm is guided by the use of a single penalty parameter; that of the logarithmic barrier. In other words, we show that IP-PMM inherits the polynomial complexity of IPMs, as well as the strict convexity of the PMM sub-problems. The updates of the penalty parameter are controlled by IPM, and hence are well-tuned, and do not depend on the problem solved. Furthermore, we study the behavior of the method when it is applied to an infeasible problem, and identify a necessary condition for infeasibility. The latter is used to construct an infeasibility detection mechanism. 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.