A linear-time median-finding algorithm for projecting a vector on the simplex of \({\mathbb{R}}^ n\). (English) Zbl 0679.90054

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.
Reviewer: M.A.Hanson


90C30 Nonlinear programming
68Q25 Analysis of algorithms and problem complexity
90C20 Quadratic programming
90C25 Convex programming
Full Text: DOI


[2] Held, M.; Wolfe, P.; Crowder, H. P., Validation of the subgradient optimization, Math. Programming, 6, 62-88 (1974) · Zbl 0284.90057
[3] Minoux, M., Mathematical Programming (1986), Wiley · Zbl 0602.90090
[4] Paula, G. G., Um algoritmo de Decomposicao Primal para um problema Dinamico de Localizacao na Producao de Carvao em Plantacao de Eucaliptus, (PhD dissertation (1986), System Engineering, COPPE, Federal University of Rio de Janeiro)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.