An efficient algorithm for the projection of a point on the intersection of two hyperplanes and a box in Rn

Abstract

In this work, Rn we present an efficient strongly polynomial algorithm for the projection of a point on the intersection of two hyperplanes and a box in Rn. Interior point methods are the most efficient algorithm in the literature to solve this problem. While efficient in practice, the complexity of interior-point methods is bounded by a polynomial in the dimension of the problem and in the accuracy of the solution. Moreover, their efficiency is highly dependent on a series of parameters depending on the specific method chosen (especially for nonlinear problems), such as step size, barrier parameter, accuracy, among others. We propose a new method based on the KKT optimality conditions. In this method, we write the problem as a function of the Lagrangian multipliers of the hyperplanes and seek to find the pair of multipliers that corresponds to the optimal solution. We prove that the algorithm has complexity O(n2logn).

Keywords

• 90-08 Computational methods