An O(n) Algorithm for Projecting a Vector on the Intersection of a Hyperplane and a Box in Rn

N. Maculan, C.P. Santiago, E.M. Macambira and M.H.C. Jardim
Additional contact information
N. Maculan: Universidade Federal do Rio de Janeiro
C.P. Santiago: Universidade Federal do Rio de Janeiro
E.M. Macambira: Universidade Federal do Rio de Janeiro
M.H.C. Jardim: Universidade Federal do Rio de Janeiro

Journal of Optimization Theory and Applications, 2003, vol. 117, issue 3, No 7, 553-574

Abstract: Abstract We consider the problem of projecting a vector on the intersection of a hyperplane and a box in Rn. This paper extends a previous result of Maculan, Minoux, and Plateau (Ref. 1) concerning the projection of a vector on the intersection of a hyperplane and Rn +. We present an O(n) time algorithm based on the linear-time median-finding algorithm. This algorithm determines the median of the components of the vector to be projected. Computational results are also presented in order to evaluate the algorithm and its time complexity. We consider two sets of instances which are randomly generated for any given n. The algorithm was successful in solving all the instances in a reasonable time.

Keywords: Orthogonal projections; linear-time algorithm; computational linear algebra; subgradient methods (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1023/A:1023997605430 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:joptap:v:117:y:2003:i:3:d:10.1023_a:1023997605430

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1023/A:1023997605430

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().