Comparative study of two fast algorithms for projecting a~point to the standard simplex

G. Sh. Tamasyan ; E. V. Prosolupov ; T. A. Angelov

Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 2, pp. 100-123.

Résumé

We consider two algorithms for orthogonal projection of a point to the standard simplex. Although these algorithms are fundamentally different, the following fact unites them. 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. Ill. 11, bibliogr. 23.

Détail

Keywords: quadratic programming, projecting a point to a simplex, optimality conditions.

Bibliographie

[1] M. K. Gavurin, V. N. Malozemov, Extreme Problems with Linear Constraints, Izd. Leningr. Univ., Leningrad, 1984

[2] V. F. Demyanov, G. Sh. Tamasyan, “On direct methods for solving variational problems”, Tr. Inst. Mat. Mekh., 16, no. 5, 2010, 36–47

[3] M. V. Dolgopolik, G. Sh. Tamasyan, “On equivalence of the method of steepest descent and the method of hypodifferential descent in some constrained optimization problems”, Izv. Sarat. Univ., Ser. Mat. Mekh. Inform., 14:4-2 (2014), 532–542 | Zbl

[4] V. N. Malozemov, “MDM method – 40 years”, Vestn. Syktyvkar. Univ., Ser. 1, 2012, no. 15, 51–62

[5] V. N. Malozemov, A. B. Pevnyi, “Fast algorithm for projecting a point on a simplex”, Vestn. St. Petersbg. Univ., Math., 25:1 (1992), 62–63 | MR | Zbl

[6] V. N. Malozemov, G. Sh. Tamasyan, “Two fast algorithms for finding the projection of a point onto the standard simplex”, Zh. Vychisl. Mat. Mat. Fiz., 56:5 (2016), 742–755

[7] G. Sh. Tamasyan, “Methods of steepest and hypodifferential descent in one problem of calculus of variations”, Vychisl. Metody Program., 13:1, 197–217

[8] G. Sh. Tamasyan, “Numerical methods in problems of calculus of variations for functionals depending on higher order derivatives”, J. Math. Sci., 188:3 (2013), 299–321 | DOI | MR | Zbl

[9] G. Sh. Tamasyan, A. A. Chumakov, “Finding the distance between ellipsoids”, J. Appl. Ind. Math., 8:3 (2014), 400–410 | DOI | MR | Zbl

[10] A. Yu. Uteshev, M. V. Yashina, “Computation of the distance from an ellipsoid to a linear surface and a quadric in $\mathbb R^n$”, Dokl. Math., 77:2 (2008), 269–272 | DOI | MR | Zbl

[11] Brucker P., “An $O(n)$ algorithm for quadratic knapsack problems”, Oper. Res. Lett., 3:3 (1984), 163–166 | DOI | MR | Zbl

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

[13] Demyanov V. F., Giannessi F., Tamasyan G. Sh., “Variational control problems with constraints via exact penalization”, Variational Analysis and Applications, Nonconvex Optim. Its Appl., 79, eds. F. Giannessi, A. Maugeru, Springer-Verl., New York, 2005, 301–342 | DOI | MR | Zbl

[14] Demyanov V. F., Tamasyan G. Sh., “Exact penalty functions in isoperimetric problems”, Optimization, 60:1–2 (2011), 153–177 | DOI | MR | Zbl

[15] Demyanov V. F., Tamasyan G. Sh., “Direct methods in the parametric moving boundary variational problem”, Numer. Funct. Anal. Optimization, 35:7–9 (2014), 932–961 | DOI | MR | Zbl

[16] Dolgopolik M. V., Tamasyan G. Sh., “Method of steepest descent for two-dimensional problems of calculus of variations”, Constructive Nonsmooth Analysis and Related Topics, Springer Optimization Its Appl., 87, eds. V. F. Demyanov, P. M. Pardalos, M. Batsyn, Springer-Verl., New York, 2014, 101–113 | DOI | MR | Zbl

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

[18] Helgason R. V., Kennington J. L., Lall H., “A polynomially bounded algorithm for a singly constrained quadratic program”, Math. Program., 18:1 (1980), 338–343 | DOI | MR | Zbl

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

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

[21] Patriksson M., “A survey on the continuous nonlinear resource allocation problem”, Eur. J. Oper. Res., 185:1 (2008), 1–46 | DOI | MR | Zbl

[22] Tamasyan G. Sh., Chumakov A. A., “Finding the distance between the ellipsoid and the intersection of a linear manifold and ellipsoid”, Proc. 2015 Int. Conf. “Stability and Control Processes” in Memory of V. I. Zubov (SCP) joined with 21st Int. Workshop on Beam Dynamics and Optimization (BDO) (St. Petersburg, Russia, Oct. 5–9, 2015), IEEE, 2015, 357–360 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7342138

[23] Tamasyan G., Prosolupov E., “Orthogonal projection of a point onto the standard simplex algorithms analysis”, Proc. 2015 Int. Conf. “Stability and Control Processes” in Memory of V. I. Zubov (SCP) joined with 21st Int. Workshop on Beam Dynamics and Optimization (BDO) (St. Petersburg, Russia, Oct. 5–9, 2015), IEEE, 2015, 353–356 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7342137