Geodesic
Two fast algorithms for projecting a point onto the canonical simplex
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 5, pp. 742-755 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{ZVMMF_2016_56_5_a2,
     author = {V. N. Malozemov and G. Sh. Tamasyan},
     title = {Two fast algorithms for projecting a point onto the canonical simplex},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {742--755},
     year = {2016},
     volume = {56},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_5_a2/}
}
TY  - JOUR
AU  - V. N. Malozemov
AU  - G. Sh. Tamasyan
TI  - Two fast algorithms for projecting a point onto the canonical simplex
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2016
SP  - 742
EP  - 755
VL  - 56
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_5_a2/
LA  - ru
ID  - ZVMMF_2016_56_5_a2
ER  - 
%0 Journal Article
%A V. N. Malozemov
%A G. Sh. Tamasyan
%T Two fast algorithms for projecting a point onto the canonical simplex
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2016
%P 742-755
%V 56
%N 5
%U http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_5_a2/
%G ru
%F ZVMMF_2016_56_5_a2
V. N. Malozemov; G. Sh. Tamasyan. Two fast algorithms for projecting a point onto the canonical simplex. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 5, pp. 742-755. http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_5_a2/

[1] Held M., Wolfe P., Crowder H. P., “Validation of the subgradient optimization”, Math. Programming, 6 (1974), 62–88 | DOI | MR | Zbl

[2] Maculan N., de Paula G. G. (Jr.), “A linear-time median-finding algorithm for projecting a vector on the simplex of $\mathbb{R}^n$”, Operations Research Letters, 8:4 (1989), 219–222 | DOI | MR | Zbl

[3] Malozemov V. N., Pevnyi A. B., “Bystryi algoritm proektirovaniya tochki na simpleks”, Vestnik SPbGU. Ser. 1, 1992, no. 1(1), 112–113

[4] Michelot C., “A finite algorithm for finding the projection of a point onto the canonical simplex of $\mathbb{R}^n$”, J. Optim. Theory Appl., 50 (1986), 195–200 | DOI | MR | Zbl

[5] Causa A., Raciti F., “A purely geometric approach to the problem of computing the projection of a point on a simplex”, J. Optim. Theory Appl., 156:2 (2013), 524–528 | DOI | MR | Zbl

[6] Malozemov V. N., “Proektirovanie tochki na podprostranstvo i na standartnyi simpleks”, Seminar “DHA CAGD”, Izbrannye doklady (28 fevralya 2013 g.) http://dha.spb.ru/reps13.shtml#0228

[7] Malozemov V. N., Tamasyan G. Sh., “Esche odin bystryi algoritm proektirovaniya tochki na standartnyi simpleks”, Seminar “DHA CAGD”, Izbrannye doklady (5 sentyabrya 2013 g.) http://dha.spb.ru/reps13.shtml#0905

[8] Malozemov V. N., Tamasyan G. Sh., “Proektirovanie tochki na telesnyi simpleks”, Seminar “DHA CAGD”, Izbrannye doklady (11 oktyabrya 2013 g.) http://dha.spb.ru/reps13.shtml#1011

[9] Tamasyan G. Sh., “Sravnitelnoe izuchenie dvukh bystrykh algoritmov proektirovaniya tochki na standartnyi simpleks”, Seminar “CNSA NDO”, Izbrannye doklady (15 maya 2014 g.) http://www.apmath.spbu.ru/cnsa/doklad14.html#0515