About Journal 
Editorial Board
Publishing Ethics
Author Guide 
Submission
Prepare Your Manuscript
Peer review
Archive
Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2016, 10:2, 288-301
Volume 23, No 2, 2016, P. 100-123
UDC 519.85
G. Sh. Tamasyan, E. V. Prosolupov, and T. A. Angelov
Comparative study of two fast algorithms for projecting a point to the standard simplex
Abstract:
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.
Keywords: quadratic programming, projecting a point to a simplex, optimality conditions.
DOI: 10.17377/daio.2016.23.510
Grigoriy Sh. Tamasyan 1
Evgenii V. Prosolupov 1
Todor A. Angelov 1
1. St. Petersburg State University,
35 University Ave., 198504 Peterhof, Russia
e-mail: g.tamasyan@spbu.ru, e.prosolupov@spbu.ru, t.angelov@spbu.ru
Received 11 September 2015
Revised 19 October 2015
References
[1] M. K. Gavurin and V. N. Malozemov, Ekstremal’nye zadachi s lineinymi ogranicheniyami (Extreme Problems with Linear Constraints), Izd. Leningr. Univ., Leningrad, 1984.[2] V. F. Demyanov and G. Sh. Tamasyan, On direct methods for solving variational problems, Tr. Inst. Mat. Mekh., 16, No. 5, 36–47, 2010.
[3] M. V. Dolgopolik and 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, No. 4-2, 532–542, 2014.
[4] V. N. Malozemov, MDM method 40 years, Vestn. 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, Vestn. St.-Peterbg. Univ., Ser. 1, No. 1, 112–113, 1992. Translated in Vestn. St. Petersbg. Univ., Math., 25, No. 1, 62–63, 1992.
[6] V. N. Malozemov and G. Sh. Tamasyan, Two fast algorithms for finding the projection of a point onto the standard simplex, Zh. Vychisl. Mat. Mat. Fiz., 2016. DOI: 10.7868/S0044466916050148
[7] G. Sh. Tamasyan, Methods of steepest and hypodifferential descent in one problem of calculus of variations, Vychisl. Metody Program., 13, No. 1, 197–217, 2012.
[8] G. Sh. Tamasyan, Numerical methods in problems of calculus of variations for functionals depending on higher order derivatives, in Problemy matematicheskogo analiza (Problems of Mathematical Analysis), Vol. 67, pp. 113–132, Tamara Rozhkovskaya, Novosibirsk, 2012. Translated in J. Math. Sci., 188, No. 3, 299–321, 2013.
[9] G. Sh. Tamasyan and A. A. Chumakov, Finding the distance between ellipsoids, Diskretn. Anal. Issled. Oper., 21, No. 3, 87–102, 2014. Translated in J. Appl. Ind. Math., 8, No. 3, 400–410, 2014.
[10] A. Yu. Uteshev and M. V. Yashina, Computation of the distance from an ellipsoid to a linear surface and a quadric in $\mathbb{R}^{n}$, Dokl. Akad. Nauk, 419, No. 4, 471–474, 2008. Translated in Dokl. Math., 77, No. 2, 269–272, 2008.
[11] P. Brucker, An $O(n)$ algorithm for quadratic knapsack problems, Oper. Res. Lett., 3, No. 3, 163–166, 1984.
[12] A. Causa and F. Raciti, A purely geometric approach to the problem of computing the projection of a point on a simplex, J. Optimization Theory Appl., 156, No. 2, 524–528, 2013.
[13] V. F. Demyanov, F. Giannessi, and G. Sh. Tamasyan, Variational control problems with constraints via exact penalization, in F. Giannessi and A. Maugeru, eds., Variational Analysis and Applications, pp. 301–342, Springer, New York, 2005 (Nonconvex Optim. Its Appl., Vol. 79).
[14] V. F. Demyanov and G. Sh. Tamasyan, Exact penalty functions in isoperimetric problems, Optimzation, 60, No. 1–2, 153–177, 2011.
[15] V. F. Demyanov and G. Sh. Tamasyan, Direct methods in the parametric moving boundary variational problem, Numer. Funct. Anal. Optimization, 35, No. 7–9, 932–961, 2014.
[16] M. V. Dolgopolik and G. Sh. Tamasyan, Method of steepest descent for two-dimensional problems of calculus of variations, in V. F. Demyanov, P. M. Pardalos, and M. Batsyn, eds., Constructive Nonsmooth Analysis and Related Topics, pp. 101–113, Springer, New York, 2014 (Springer Optimization Its Appl., Vol. 87).
[17] M. Held, P. Wolfe, and H. P. Crowder, Validation of subgradient optimization, Math. Program., 6, No. 1, 62–88, 1974.
[18] R. V. Helgason, J. L. Kennington, and H. Lall, A polynomially bounded algorithm for a singly constrained quadratic program, Math. Program., 18, No. 1, 338–343, 1980.
[19] N. Maculan and G. Galdino de Paula, Jr., A linear-time median-finding algorithm for projecting a vector on the simplex of $\mathbb{R}^{n}$, Oper. Res. Lett., 8, No. 4, 219–222, 1989.
[20] C. Michelot, A finite algorithm for finding the projection of a point onto the canonical simplex of $\mathbb{R}^{n}$, J. Optim. Theory Appl., 50, No. 1, 195–200, 1986.
[21] M. Patriksson, A survey on the continuous nonlinear resource allocation problem, Eur. J. Oper. Res., 185, No. 1, 1–46, 2008.
[22] G. Tamasyan, A. Chumakov, Finding the distance between the ellipsoid and the intersection of a linear manifold and ellipsoid, in 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, pp. 357–360, IEEE, 2015.
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7342138
[23] G. Tamasyan, E. Prosolupov, Orthogonal projection of a point onto the standard simplex algorithms analysis, in 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, pp. 353–356, IEEE, 2015.
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7342137
