An efficient algorithm for the projection of a point on the intersection of two hyperplanes and a box in $$\mathbb {R}^n$$ R n

In this work, we present an efficient strongly polynomial algorithm for the projection of a point on the intersection of two hyperplanes and a box in $$\mathbb {R}^n$$ R n . 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(n^2 \log n)$$ O ( n 2 log n ) .