TY - JOUR

T1 - Two Fast Algorithms for Projecting a Point onto the Canonical Simplex

AU - Malozemov, V. N.

AU - Tamasyan, G. Sh.

PY - 2016

Y1 - 2016

N2 - Two fast orthogonal projection algorithms of a point onto the canonical simplex are analyzed. These algorithms are called the vector and scalar algorithms, respectively. The ideas underlying these algorithms are well known. Improved descriptions of both algorithms are given, their finite convergence is proved, and exact estimates of the number of arithmetic operations needed for their implementation are derived, and numerical results of the comparison of their computational complexity are presented. It is shown that on some examples the complexity of the scalar algorithm is maximal but the complexity of the vector algorithm is minimal and conversely. The orthogonal projection of a point onto the solid simplex is also considered.

AB - Two fast orthogonal projection algorithms of a point onto the canonical simplex are analyzed. These algorithms are called the vector and scalar algorithms, respectively. The ideas underlying these algorithms are well known. Improved descriptions of both algorithms are given, their finite convergence is proved, and exact estimates of the number of arithmetic operations needed for their implementation are derived, and numerical results of the comparison of their computational complexity are presented. It is shown that on some examples the complexity of the scalar algorithm is maximal but the complexity of the vector algorithm is minimal and conversely. The orthogonal projection of a point onto the solid simplex is also considered.

KW - quadratic programming

KW - projecting onto a simplex

KW - optimality condition

KW - fast algorithms

U2 - 10.1134/S0965542516050146

DO - 10.1134/S0965542516050146

M3 - Article

VL - 56

SP - 730

EP - 743

JO - Computational Mathematics and Mathematical Physics

JF - Computational Mathematics and Mathematical Physics

SN - 0965-5425

IS - 5

ER -