A linear-time median-finding algorithm for projecting a vector on the simplex of \({\mathbb{R}}^ n\)
type: Item
instance of: scholarly article
title: A linear-time median-finding algorithm for projecting a vector on the simplex of \({\mathbb{R}}^ n\)
zbMATH Open document ID: 0679.90054
DOI: 10.1016/0167-6377(89)90064-3
author: Geraldo jun. Galdino de Paula
author: Nelson Maculan
published in: Operations Research Letters
publication date: 1989-01-01T00:00:00Z
review text: An algorithm is given for the projection of a vector \(\bar x\in R^ n\) on the simplex \(\{x\in R^ n|\) \(e^ Tx=1\), \(x\geq 0\}\). The problem is written as a convex quadratic programming problem, for which the Kuhn- Tucker conditions are solved. It is shown that the complexity is O(n) time. A numerical example is given.
Mathematics Subject Classification ID: 90C30
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90C20
Mathematics Subject Classification ID: 90C25
zbMATH DE Number: 4114387
zbMATH Keywords: computational linear algebra
zbMATH Keywords: projection of a vector
zbMATH Keywords: Kuhn-Tucker conditions
Wikidata QID: Q56070151
reviewed by: Morgan A. Hanson
MaRDI profile type: Publication
full work available at URL: 0167-6377(89)90064-3
OpenAlex ID: W1993367034
cites work: Q4091421
cites work: Validation of subgradient optimization
cites work: Q3738922
description: scientific article; zbMATH DE number 4114387