Two methods for the maximization of homogeneous polynomials over the simplex
Tóm tắt
The paper deals with the numerical solution of the problem P to maximize a homogeneous polynomial over the unit simplex. We discuss the convergence properties of the so-called replicator dynamics for solving P. We further examine an ascent method, which also makes use of the replicator transformation. Numerical experiments with polynomials of different degrees illustrate the theoretical convergence results.
Tài liệu tham khảo
Ahmed, F., Still, G.: Maximization of homogeneous polynomials over simplex and sphere: structure, stability, and generic behavior. J. Optim. Theory Appl. 181, 972–996 (2019)
Baum, L., Eagon, J.: An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology. Bull. Am. Math. Soc. 73, 360–363 (1967)
Bomze, I.M.: Non-cooperative two-person games in biology: a classification. Int. J. Game Theory 15(1), 31–57 (1986)
Bomze, I.M.: Evolution towards the maximum clique. J. Glob. Optim. 10(2), 143–164 (1997)
Bomze, I.M.: On standard quadratic optimization problems. J. Glob. Optim. 13(4), 369–387 (1998)
Bomze, I.M., De Klerk, E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Glob. Optim. 24(2), 163–185 (2002)
Broom, M., Cannings, C., Vickers, G.: Multi-player matrix games. Bull. Math. Biol. 59(5), 931–952 (1997)
Broom, M., Rychtár, J.: Game-Theoretical Models in Biology. CRC Press, Boca Raton (2013)
Bulò, S.R., Pelillo, M.: A continuous characterization of maximal cliques in k-uniform hypergraphs. In: International conference on learning and intelligent optimization, pp. 220–233. Springer (2007)
Bulò, S.R., Pelillo, M.: A generalization of the Motzkin–Straus theorem to hypergraphs. Optim. Lett. 3(2), 287–295 (2009)
Clark, P.: Sequences and series; a source book. http://www.math.uga.edu/~pete/3100supp.pdf
De Klerk, E., Laurent, M., Sun, Z., Vera, J.C.: On the convergence rate of grid search for polynomial optimization over the simplex. Optim. Lett. 11(3), 597–608 (2017)
Faybusovich, L.: Global optimization of homogeneous polynomials on the simplex and on the sphere. In: Frontiers in Global Optimization, pp. 109–121. Springer (2004)
Kingman, J.F.: On an inequality in partial averages. Q. J. Math. 12, 78–80 (1961)
Kleniati, P.-M., Parpas, P., Rustem, B.: Partitioning procedure for polynomial optimization. J. Glob. Optim. 48, 549–567 (2010)
Losert, V., Akin, E.: Dynamics of games and genes: discrete versus continuous time. J. Math. Biol. 17, 241–251 (1983)
Lyubich, Y., Maistrovskii, G., Ol’khovskii, Y.: Selection-induced convergence to equilibrium in a single-locus autosomal population. Probl. Peredachi Inf. 16(1), 93–104 (1980). ((Russian))
Motzkin, T., Strauss, E.: Maxima for graphs and a new proof of a theorem of Turán. Can. J. Math. 17, 533–540 (1965)
Murty, K., Kabadi, S.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39(2), 117–129 (1987)
Palm, G.: Evolutionary stable strategies and game dynamics for \(n\)-person games. J. Math. Biol. 19(3), 329–334 (1984)
Smith, J.M.: The theory of games and the evolution of animal conflicts. J. Theor. Biol. 47(1), 209–221 (1974)
Smith, J.M., Price, G.R.: The logic of animal conflict. Nature 246(5427), 15–18 (1973)