Programming approach to Malfatti’s problem
Автор: Enkhbat Rentsen, Barkova Mariya V., Sukhee Batbileg
Журнал: Вестник Бурятского государственного университета. Математика, информатика @vestnik-bsu-maths
Рубрика: Управляемые системы и методы оптимизации
Статья в выпуске: 4, 2018 года.
Бесплатный доступ
In previous works R. Enkhbat showed that the Malfatti's problem can be treated as the convex maximization problem and provided with an algorithm based on Global Optimality Conditions of A. S. Strekalovsky. In this article we reformulate Malfatti’s problem as a D.C. programming problem with a nonconvex constraint. The reduced problem as an optimization problem with D.C. constraints belongs to a class of global optimization. We apply the local and global optimality conditions by A. S. Strekalovsky developed for D.C programming. Based on local search methods for D.C. programming, we have developed an algorithm for numerical solution of Malfatti's problem. In numerical experiments, initial points of the proposed algorithm are chosen randomly. Global solutions have been found in all cases.
D.c. programming, global optimality conditions, malfatti''s problem, convex maximization, local search algorithm, d.c. constraint, global optimization, malfatti circles, linearized problem, d.c. minimization, d.c. оптимизация, d.c. ограничение, d.c. минимизация
Короткий адрес: https://sciup.org/148308922
IDR: 148308922 | УДК: 519.853 | DOI: 10.18101/2304-5728-2018-4-72-83
Подход к решению задачи Мальфатти
В предыдущих работах Р. Энхбат показал, что проблему Малфатти можно рассматривать как проблему выпуклой максимизации и решать алгоритмом на основе глобальных условий оптимальности А. С. Стрекаловского. В этой статье мы переформулируем проблему Малфатти как проблему D.C. программирования с невыпуклым ограничением. Приведенная проблема, как проблема оптимизации с D.C. ограничениями, принадлежит классу глобальной оптимизации. Мы применяем локальные и глобальные условия оптимальности А. С. Стрекаловского, разработанные для D.C. программирования. Основываясь на методах локального поиска для D.C. программирования, мы разработали алгоритм для численного решения задачи Малфатти. В численных экспериментах исходные точки предлагаемого алгоритма выбираются случайным образом. Во всех случаях найдены глобальные решения.
Список литературы Programming approach to Malfatti’s problem
- Andreatta M., Bezdek A. and Boroaski Jan P. The Problem of Malfatti: Two Centuries of Debate. The Mathematical Intelligencer. 2011. No. 33. Pp. 72-76.
- Andrei N. Hybrid Conjugate Gradient Algorithm for Unconstrained Optimization. JOTA. 2009. No. 141. Pp. 249-264.
- Anikin A., Gornov A., and Andrianov A. Computational Technologies for Morse Potential Optimization. Optimization and Applications (OPTIMA-2013): Abstracts of IV Internetional Conference. 2013. Pp. 22-23.
- David J. W. and Doye J. P. K. Global optimization by basin-hopping and the lowest energy structures of Lennard-Jones clusters containing up to 110 atoms. The Journal of Physical Chemistry A. 1997. V. 28. No. 101. Pp. 5111 -5116.
- Nocedai J., Wright St. J. Numerical Optimization. New York: Springer, 2006. 685 p.
