Volume 25, No 2, 2018, P. 82-100

UDC 519.8
E. V. Prosolupov and G. Sh. Tamasyan
Complexity estimation for an algorithm of searching for zero of a piecewise linear convex function

Abstract:
It is known that the problem of the orthogonal projection of a point to the standard simplex can be reduced to solution of a scalar equation. In this article, the complexity is analyzed of an algorithm of searching for zero of a piecewise linear convex function which is proposed by N. Maculan and G. Galdino de Paula, Jr. (Oper. Res. Lett. 8 (4), 219–222 (1989)). The analysis is carried out of the best and worst cases of the input data for the algorithm. To this end, the largest and smallest numbers of iterations of the algorithm are studied as functions of the size of the input data. It is shown that, in the case of equality of elements of the input set, the algorithm performs the smallest number of iterations. In the case of different elements of the input set, the number of iterations is maximal and depends rather weakly on the particular values of the elements of the set. The results of numerical experiments with random input data of large dimension are presented.
Tab. 2, illustr. 2, bibliogr. 34.

Keywords: standard simplex, orthogonal projection of a point, zeros of function.

DOI: 10.17377/daio.2018.25.571

Evgeny V. Prosolupov ¹
Grigory Sh. Tamasyan ¹
1. St. Petersburg State University,
Universitetskii Ave., 35, 198504 St. Petersburg, Russia
e-mail: e.prosolupov@spbu.ru, g.tamasyan@spbu.ru

Received 10 March 2017
Revised 26 December 2017

References

[1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, Data Structures and Algorithms, Addison-Wesley, Reading, MA, 1983. Translated under the title Struktury dannykh i algoritmy, Izd. dom Williams, Moscow, 2003 [Russian].

[2] A. S. Velichko, On the step choice in projection algorithms for large-scale linear programming problems, Dal’nevost. Mat. Zh., 12, No. 2, 160–170, 2012 [Russian].

[3] V. F. Demyanov and G. Sh. Tamasyan, On direct methods for solving variational problems, Tr. Inst. Mat. Mekh., 16, No. 5, 36–47, 2010 [Russian].

[4] D. V. Dolgii, E. A. Nurminskii, An accelerated parallel projection method for solving the minimum length problem, Vychisl. Metody Program., 7, No. 3, 273–277, 2006 [Russian].

[5] 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 [Russian].

[6] V. I. Zorkal’tsev, Octahedral and Euclidean projections of a point to a linear manifold, Tr. Inst. Mat. Mekh., 18, No. 3, 106–118, 2012 [Russian]. Translated in Proc. Steklov Inst. Math., 284, Suppl. 1, 185–197, 2014.

[7] V. I. Zorkal’tsev, Projecting a point on a polyhedron, Zh. Vychisl. Mat. Mat. Fiz., 53, No. 1, 4–19, 2013 [Russian].

[8] V. N. Malozemov, MDM method — 40 years, Vestn. Syktyvkar. Univ., Ser. 1, No. 15, 51–62, 2012 [Russian].

[9] 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 [Russian]. Translated in Vestn. St. Petersbg. Univ., Math., 25, No. 1, 62–63, 1992.

[10] 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., 56, No. 5, 742–755, 2016 [Russian]. Translated in Comput. Math. Math. Phys., 56, No. 5, 730–743, 2016.

[11] V. N. Malozemov and G. Sh. Tamasyan, Gibb’s lemma and its applications, Seminar on Constructive Nonsmooth Analysis and Nondifferentiable Optimization, Selected Talks, St-Peterbg. Gos. Univ., St. Petersburg, 2017. Available at http://www.apmath.spbu.ru/cnsa/pdf/2017/LemmaGibbsa.pdf (accessed Jan. 3, 2018) [Russian].

[12] B. F. Mitchell, V. F. Demyanov, and V. N. Malozemov, Finding point of polyhedron nearest to the origin, Vestn. Leningr. Univ., No. 19, 38–45, 1971 [Russian].

[13] E. A. Nurminski, A parallel method of projection onto the convex hull of a family of sets, Izv. Vyssh. Uchebn. Zaved., Mat., No. 12, 78–82, 2003 [Russian]. Translated in Russ. Math., 47, No. 12, 74–78, 2003.

[14] E. A. Nurminski, Projection onto polyhedra in outer representation, Zh. Vychisl. Mat. Mat. Fiz., 48, No. 3, 387–396, 2008 [Russian]. Translated in Comput. Math. Math. Phys., 48, No. 3, 367–375, 2008.

[15] 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 [Russian].

[16] G. Sh. Tamasyan, Numerical methods in problems of calculus of variations for functionals depending on higher order derivatives, in Problems of Mathematical Analysis, Vol. 67, pp. 113–132, Tamara Rozhkovskaya, Novosibirsk, 2012 [Russian]. Translated in J. Math. Sci., 188, No. 3, 299–321, 2013.

[17] G. Sh. Tamasyan, E. V. Prosolupov, and T. A. Angelov, Comparative study of two fast algorithms for projecting a point to the standard simplex, Diskretn. Anal. Issled. Oper., 23, No. 2, 100–123, 2016 [Russian]. Translated in J. Appl. Ind. Math., 10, No. 2, 288–301, 2016.

[18] G. Sh. Tamasyan and A. A. Chumakov, Finding the distance between ellipsoids, Diskretn. Anal. Issled. Oper., 21, No. 3, 87–102, 2014 [Russian]. Translated in J. Appl. Ind. Math., 8, No. 3, 400–410, 2014.

[19] 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 [Russian]. Translated in Dokl. Math., 77, No. 2, 269–272, 2008.

[20] P. Brucker, An $O(n)$ algorithm for quadratic knapsack problems, Oper. Res. Lett., 3, No. 3, 163–166, 1984.

[21] A. Causa and F. Raciti, A purely geometric approach to the problem of computing the projection of a point on a simplex, J. Optim. Theory Appl., 156, No. 2, 524–528, 2013.

[22] V. F. Demyanov, Algorithms for some minimax problems, J. Comput. Syst. Sci., 2, No. 4, 342–380, 1968.

[23] V. F. Demyanov, F. Giannessi, and G. Sh. Tamasyan, Variational control problems with constraints via exact penalization, in Variational Analysis and Applications, pp. 301–342, Springer, New York, 2005 (Nonconvex Optim. Its Appl., Vol. 79).

[24] V. F. Demyanov and G. Sh. Tamasyan, Exact penalty functions in isoperimetric problems, Optim., 60, No. 1–2, 153–177, 2011.

[25] V. F. Demyanov and G. Sh. Tamasyan, Direct methods in the parametric moving boundary variational problem, Numer. Funct. Anal. Optim., 35, No. 7–9, 932–961, 2014.

[26] F. Deutsch, The method of alternating orthogonal projections, in Approximation Theory, Spline Functions and Applications, pp. 105–121, Kluwer Acad. Publ., Dordrecht, 1992.

[27] M. V. Dolgopolik and G. Sh. Tamasyan, Method of steepest descent for two-dimensional problems of calculus of variations, in Constructive Nonsmooth Analysis and Related Topics, pp. 101–113, Springer, New York, 2014 (Springer Optim. Its Appl., Vol. 87).

[28] M. Held, P. Wolfe, and H. P. Crowder, Validation of subgradient optimization, Math. Program., 6, No. 1, 62–88, 1974.

[29] 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.

[30] 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.

[31] 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.

[32] M. Patriksson, A survey on the continuous nonlinear resource allocation problem, Eur. J. Oper. Res., 185, No. 1, 1–46, 2008.

[33] G. Sh. Tamasyan and A. A. Chumakov, Finding the distance between an ellipsoid and the intersection of a linear manifold and ellipsoid, Proc. 2015 Int. Conf. “Stability and Control Processes” in Memory of V. I. Zubov, St. Petersburg, Russia, Oct. 5–9, 2015, pp. 357–360, IEEE, Piscataway, 2015.

[34] G. Sh. Tamasyan and E. V. Prosolupov, 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, St. Petersburg, Russia, Oct. 5–9, 2015, pp. 353–356, IEEE, Piscataway, 2015.