×

Comparative study of two fast algorithms for projecting a point to the standard simplex. (Russian, English) Zbl 1349.90668

Diskretn. Anal. Issled. Oper. 23, No. 2, 100-123 (2016); translation in J. Appl. Ind. Math. 10, No. 2, 288-301 (2016).
Summary: We consider two algorithms for orthogonal projection of a point to the standard simplex. These algorithms are fundamentally different; however, they are related to each other by the following fact: When one of them has the maximum run time, the run time of the other is minimal. Some particular domains are presented whose points are projected by the considered algorithms in the minimum and maximum number of iterations. The correctness of the conclusions is confirmed by the numerical experiments independently implemented in the MatLab environment and the Java programming language.

MSC:

90C20 Quadratic programming

Software:

Matlab
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. K. Gavurin and V. N. Malozemov, Extreme Problems with Linear Constraints (Izd. Leningrad. Univ., Leningrad, 1984) [in Russian]. · Zbl 0593.90046
[2] V. F. Demyanov and G. Sh. Tamasyan, “On Direct Methods for Solving Variational Problems,” Trudy Inst. Mat. Mekh. Ural. Otdel. Ross. Akad. Nauk 16 (5), 36-47 (2010).
[3] M. V. Dolgopolik and G. Sh. Tamasyan, “On Equivalence of the Methods of Steepest and Hypodifferential Descents in Some Constrained Optimization Problems,” Izv. Saratov. Univ. Ser. Mat. Mekh. Inform. 14 (4-2), 532-542 (2014). · Zbl 1310.49007
[4] V. N. Malozemov, “MDMMethod—40 Years,” Vestnik Syktyvkar. Univ. Ser. 1, No. 15, 51-62(2012).
[5] V. N. Malozemov and A. B. Pevnyi, “Fast Algorithm for Projecting a Point on a Simplex,” Vestnik. St.- Peterburg. Univ. Ser. 1, No. 1, 112-113 (1992) [Vestnik St. Petersburg Univ. Math. 25 (1), 62-63 (1992)]. · Zbl 0797.90074
[6] Malozemov, V. N.; Tamasyan, G. Sh., Two Fast Algorithms for Finding the Projection of a Point onto the Standard Simplex (2016) · Zbl 1352.65154
[7] G. Sh. Tamasyan, “Methods of Steepest and Hypodifferential Descent in a Problem of Calculus of Variations,” Vychisl. Metody Program. 13 (1), 197-217 (2012).
[8] Tamasyan, G. Sh., Numerical Methods in Problems of Calculus of Variations for Functionals Depending on Higher Order Derivatives, 113-132 (2012), Novosibirsk
[9] G. Sh. Tamasyan and A. A. Chumakov, “Finding the Distance between Ellipsoids,” Diskretn. Anal. Issled. Oper. 21 (3), 87-102 (2014) [J. Appl. Indust. Math. 8 (3), 400-410 (2014)]. · Zbl 1324.90196
[10] A. Yu. Uteshev and M. V. Yashina, “Computation of the Distance from an Ellipsoid to a Linear Surface and a Quadric in Rn,” Dokl. Akad. Nauk 419 (4), 471-474 (2008) [Dokl. Math. 77 (2), 269-272 (2008)]. · Zbl 1152.53005
[11] P. Brucker, “An O(n) Algorithm for Quadratic Knapsack Problems,” Oper. Res. Lett. 3 (3), 163-166 (1984). · Zbl 0544.90086 · doi:10.1016/0167-6377(84)90010-5
[12] A. Causa and F. Raciti, “A PurelyGeometric Approach to the Problem of Computing the Projection of a Point on a Simplex,” J. Optimization Theory Appl. 156 (2), 524-528 (2013). · Zbl 1262.90084 · doi:10.1007/s10957-012-0115-5
[13] Demyanov, V. F.; Giannessi, F.; Sh. Tamasyan, G.; Giannessi, F. (ed.); Maugeru, A. (ed.), Variational Control Problems with Constraints via Exact Penalization, 301-342 (2005), New York · Zbl 1113.49036 · doi:10.1007/0-387-24276-7_21
[14] V. F. Demyanov and G. Sh. Tamasyan, “Exact Penalty Functions in Isoperimetric Problems,” Optimization 60 (1-2), 153-177 (2011). · Zbl 1237.90228 · doi:10.1080/02331934.2010.534166
[15] V. F. Demyanov and G. Sh. Tamasyan, “Direct Methods in the Parametric Moving Boundary Variational Problem,” Numer. Funct. Anal. Optim. 35 (7-9), 932-961 (2014). · Zbl 1295.49009 · doi:10.1080/01630563.2014.922097
[16] Dolgopolik, M. V.; Tamasyan, G. Sh.; Demyanov, V. F. (ed.); Pardalos, P. M. (ed.); Batsyn, M. (ed.), Method of Steepest Descent for Two-Dimensional Problems of Calculus of Variations, 101-113 (2014), New York · Zbl 1280.49039 · doi:10.1007/978-1-4614-8615-2_7
[17] M. Held, P. Wolfe, and H. P. Crowder, “Validation of the Subgradient Optimization,” Math. Progr. 6 (1), 62-88 (1974). · Zbl 0284.90057 · doi:10.1007/BF01580223
[18] R. V. Helgason, J. L. Kennington, and H. Lall, “A Polynomially Bounded Algorithm for a Singly Constrained Quadratic Program,” Math. Program. 18 (1), 338-343 (1980). · Zbl 0452.90054 · doi:10.1007/BF01588328
[19] N. Maculan and G. Galdino de Paula, Jr., “A Linear-Time Median-Finding Algorithm for Projecting a Vector on the Simplex of Rn,” Oper. Res. Lett. 8 (4), 219-222 (1989). · Zbl 0679.90054 · doi:10.1016/0167-6377(89)90064-3
[20] C. Michelot, “A Finite Algorithm for Finding the Projection of a Point onto the Canonical Simplex of Rn,” J. Optim. Theory Appl. 50 (1), 195-200 (1986). · Zbl 0571.90074 · doi:10.1007/BF00938486
[21] M. Patriksson, “A Survey on the Continuous Nonlinear Resource Allocation Problem,” European J. Oper. Res. 185 (1), 1-46 (2008). · Zbl 1146.90493 · doi:10.1016/j.ejor.2006.12.006
[22] Sh. Tamasyan, G.; Chumakov, A. A., Finding the Distance between the Ellipsoid and the Intersection of a Linear Manifold and Ellipsoid (2015)
[23] Tamasyan, G.; Prosolupov, E., Orthogonal Projection of a Point onto the Standard Simplex Algorithms Analysis, 353-356 (2015)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.