Complexity estimation for an algorithm of searching for zero of a~piecewise linear convex function

E. V. Prosolupov ; G. Sh. Tamasyan

Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 2, pp. 82-100.

Résumé

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.

Détail

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

Bibliographie

[1] A. V. Aho, J. E. Hopcroft, J. D. Ullman, Data Structures and Algorithms, Addison-Wesley, Reading, MA, 1983 | MR | Zbl

[2] A. S. Velichko, “On the step choice in projection algorithms for large-scale linear programming problems”, Dal'nevost. Mat. Zh., 12:2 (2012), 160–170 (Russian) | MR | Zbl

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

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

[5] 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 (Russian) | Zbl

[6] V. I. Zorkal'tsev, “Octahedral and Euclidean projections of a point to a linear manifold”, Proc. Steklov Inst. Math. Suppl. 1, 284 (2014), S185–S197 | DOI | MR | Zbl

[7] V. I. Zorkal'tsev, “Projecting a point on a polyhedron”, Zh. Vychisl. Mat. Mat. Fiz., 53:1 (2013), 4–19 (Russian) | DOI | Zbl

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

[9] 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

[10] V. N. Malozemov, G. Sh. Tamasyan, “Two fast algorithms for finding the projection of a point onto the standard simplex”, Comput. Math. Math. Phys., 56:5 (2016), 730–743 | DOI | DOI | MR | Zbl

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

[12] B. F. Mitchell, V. F. Demyanov, V. N. Malozemov, “Finding point of polyhedron nearest to the origin”, Vestn. Leningr. Univ., 1971, no. 19, 38–45 (Russian) | Zbl

[13] E. A. Nurminski, “A parallel method of projection onto the convex hull of a family of sets”, Russ. Math., 47:12 (2003), 74–78 | MR | Zbl

[14] E. A. Nurminski, “Projection onto polyhedra in outer representation”, Comput. Math. Math. Phys., 48:3 (2008), 367–375 | DOI | MR | Zbl

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

[16] 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

[17] G. Sh. Tamasyan, E. V. Prosolupov, T. A. Angelov, “Comparative study of two fast algorithms for projecting a point to the standard simplex”, J. Appl. Ind. Math., 10:2 (2016), 288–301 | DOI | MR | Zbl

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

[19] 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

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

[21] 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

[22] Demyanov V. F., “Algorithms for some minimax problems”, J. Comput. Syst. Sci., 2:4 (1968), 342–380 | DOI | MR | Zbl

[23] 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, Springer-Verl., New York, 2005, 301–342 | DOI | MR | Zbl

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

[25] 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

[26] Deutsch F., “The method of alternating orthogonal projections”, Approximation Theory, Spline Functions and Applications, Kluwer Acad. Publ., Dordrecht, 1992, 105–121 | DOI | MR

[27] Dolgopolik M. V., Tamasyan G. Sh., “Method of steepest descent for two-dimensional problems of calculus of variations”, Constructive Nonsmooth Analysis and Related Topics, Optim. Its Appl., 87, Springer-Verl., New York, 2014, 101–113 | MR | Zbl

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

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

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

[31] 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:1 (1986), 195–200 | DOI | MR | Zbl

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

[33] Tamasyan G., Chumakov 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 joined with 21st Int. Workshop on Beam Dynamics and Optimization (St. Petersburg, Russia, Oct. 5–9, 2015), IEEE, Piscataway, 2015, 357–360

[34] 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 joined with 21st Int. Workshop on Beam Dynamics and Optimization (St. Petersburg, Russia, Oct. 5–9, 2015), IEEE, Piscataway, 2015, 353–356