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

Maculan, Nelson; Galdino de Paula, Geraldo jun.

Oper. Res. Lett. 8, No. 4, 219-222 (1989).

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

MSC:

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

Keywords:

computational linear algebra; projection of a vector; Kuhn-Tucker conditions

References:

[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)