Method of searching for global extremum of a continuous function on a simplex

M. Yu. Livshits ; A. P. Sizikov

Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences, Tome 20 (2016) no. 4, pp. 755-768.

Résumé

A non-convex problem of mathematical programming is considered, which permissible region is a simplex. A two-stage algorithm is proposed for approximate solution of the problem. The region of global optimum is determined using the $\Psi$-transform method at the first stage; local “fine-tuning” of the solution is performed at the second stage. The $\Psi$-transform was modified taking into account the special features of the problem under consideration. $\Psi$-function is determined according to the results of statistical tests implemented using the generator of random points uniformly distributed over the simplex. The proposed method of reflection of regular simplexes is used for fine-tuning of the solution. An example of application of the developed algorithm for solving the problem of optimization of component composition of the hydrocarbon mixture is presented.

Détail

Keywords: optimization, non-convex problems, $\Psi$- transform method, uniform distribution over the simplex, multi-component mixtures.

Bibliographie

[1] Zhigljavsky A., Žilinskas A., Stochastic Global Optimization, Springer Optimization and Its Applications, 9, Springer, Berlin, 2008, xiii+262 pp. | DOI | MR | Zbl

[2] Marti K., Stochastic Optimization Methods, Applications in Engineering and Operations Research, Springer, Berlin, 2015, xxiv+368 pp. | DOI | MR | Zbl

[3] Panteleev A. V., Metaevristicheskie algoritmy poiska global'nogo ekstremuma [Metaheuristic algorithms for global extremum search], MAI Print, Moscow, 2009, 159 pp. (In Russian)

[4] M. Tim Jones, AI Application Programming, Programming Series, Charles River Media, Boston, 2003, 496 pp.

[5] Savin A. N., Timofeeva N. E., “The application of optimization algorithm using simulated annealing method for parallel computing systems”, Izv. Saratov Univ. (N.S.), Ser. Math. Mech. Inform., 12:1 (2012), 110–116 (In Russian)

[6] Botev Z. I., Kroese D. P., “Global likelihood optimization via the cross-entropy method, with an application to mixture models”, Proceedings of the 2004 Winter Simulation Conference, IEEE, Washington, 2004, 529–535 | DOI

[7] Ernst D., Glavic M., Stan G.-B., Mannor S., Wehenkel L., “The cross-entropy method for power system combinatorial optimization problems”, 2007 IEEE Lausanne Power Tech, IEEE, Washington, 2007, 1290–1295 | DOI

[8] Evans G. E., Keith J. M., Kroese D. P., “Parallel cross-entropy optimization”, 2007 Winter Simulation Conference, IEEE, Washington, 2007, 2196–2202 | DOI

[9] Zhigljavsky A., Theory of Global Random Search, Mathematics and Its Applications (Soviet Series), 65, Springer, Berlin, 1991., xviii+341 pp. | DOI | MR

[10] Feoktistov A. G., Gorskii S. A., “The Implementation of the Multi-Start method in the Gradient package”, Vestnik NGU Seriia: Informatsionnye tekhnologii, 5:2 (2007), 78–82 (In Russian)

[11] Cohoon J., Karro J., Lienig J., “Evolutionary Algorithms for the Physical Design of VLSI Circuits”, Advances in Evolutionary Computing, Natural Computing Series, eds. A. Ghosh, S. Tsutsui, Springer, Berlin, 2003, 683–712 | DOI

[12] Gladkov L. A., Kureichik V. V., Kureichik V. M., Geneticheskie algoritmy [Genetic Algorithms], Fizmatlit, Moscow, 2006, 320 pp. (In Russian)

[13] Gladkov L. A., Gladkova N. V., “Features of use of fuzzy genetic algorithms for the decision of problems of optimisation and control”, Izvestiia YuFU. Tekhnicheskie nauki, 2009, no. 4(93), 130–136

[14] Skiena S. S., The Algorithm Design Manual, Springer, London, 2008., xvi+730 pp. | DOI | Zbl

[15] Chichinadze V. K., “Solution of nonlinear nonconvex optimization problems by $\Psi$-transformation method”, Computers Mathematics with Applications, 21:6–7 (1991), 7–15 | MR | Zbl

[16] Chichinadze V. K., Reshenie nevypuklykh nelineinykh zadach optimizatsii. Metod $\Psi$-preobrazovaniia [Solution of Nonconvex Nonlinear Optimization Problems. The $\Psi$-transformation method], Nauka, Moscow, 1983, 256 pp. (In Russian) | MR

[17] Akhmadiev F. G., Gil'fanov R. M., “Mathematical modeling and optimization of the “compozition-property” of multicomponent mixtures”, Izvestiia KGASU, 2012, no. 2(20), 289–297 (In Russian)

[18] Novoselov A. A., Uniform distribution on the standard simplex in $ R ^ n $ Retrieved (October 23, 2016) (In Russian) http://risktheory.novosyolov.com/lectures/unifs.pdf

[19] Rusin Yu. V., Algoritmy statisticheskogo modelirovaniia veroiatnostnykh raspredelenii [Algorithms of statistical modeling of probability distributions], Yaroslavl State Univ., Yaroslavl, 2006, 58 pp. (In Russian)

[20] Zedginidze I. G., Planirovanie eksperimenta dlia issledovaniia mnogokomponentnykh sistem [Experiment Planning for Multicomponent System Study], Nauka, Moscow, 1976, 390 pp. (In Russian) | MR

[21] Chinakal V. O., “Optimization of light oil formulation”, Optimizatsiia, issledovanie operatsii, bionika [Optimization, Operations Research, Bionics], Nauka, Moscow, 1973, 198–205 (In Russian)

[22] Nikitin V. A., Musayev A. A., “Optimizing the compounding process of hydrocarbon mixtures”, Tr. SPIIRAN, 4 (2007), 327–336 (In Russian)