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

Cláudio P. Santiago (), Sérgio Assunção Monteiro (), Helder Inácio (), Nelson Maculan () and Maria Helena Jardim ()
Additional contact information
Cláudio P. Santiago: Lawrence Livermore National Laboratory
Sérgio Assunção Monteiro: Federal University of Rio de Janeiro
Helder Inácio: Georgia Institute of Technology
Nelson Maculan: Federal University of Rio de Janeiro
Maria Helena Jardim: Federal University of Rio de Janeiro

EURO Journal on Computational Optimization, 2019, vol. 7, issue 2, No 3, 177-207

Abstract: Abstract 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 ) .

Keywords: Orthogonal projections; Convex programming; Separable quadratic programming; Interior-point methods; Strongly polynomial algorithm; 90-08; Computational; methods (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13675-018-0105-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurjco:v:7:y:2019:i:2:d:10.1007_s13675-018-0105-y

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13675

DOI: 10.1007/s13675-018-0105-y

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

More articles in EURO Journal on Computational Optimization from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().