Global search method for solving Malfatti’s four-circle problem
We consider Malfatti’s problem formulated 200 years ago. In the beginning, Malfatti’s problem was supposed to be solved in a geometric construction way. In 1994, it was done by Zalgaller and Los for the original Malfatti’s problem using so-called greedy algorithm. There is still a conjecture about solving Malfatti’s problem for more than four circles by the greedy algorithm. We generalize Malfatti’s problem formulated for the case of three circles inscribed in a triangle for four circles. We examine six cases for inscribed circles in a triangle. The problem has been formulated as the convex maximization problem over a nonconvex set. Global optimality conditions by Strekalovsky have been applied to this problem. For solving numerically Malfatti’s problem, we propose an algorithm which converges globally. Subproblems of the proposed algorithm were quadratic programming problems with quadratic constraints. These problem can be solved by Lagrangian methods. For a computational purpose, we consider a triangle with given vertices. Some computational results are provided.
1. Enkhbat R. An algorithm for maximizing a convex function over a simple set. Journal of Global Optimization, 1996, vol.8, pp. 379-391.
2. Marco Andreatta, Andrs Bezdek and Jan P. Boroski, The Problem of Malfatti: Two Centuries of Debate. The Mathematical Intelligencer, 2011, vol. 33, issue 1, pp. 72-76.
3. V.N. Nefedov, Finding the Global Maximum of a Function of Several Variables on a Set Given by Inequality Constraints. Journal of Numerical Mathematics and Mathematical Physics, 1987, vol. 27(1), pp. 35-51.
4. Strekalovsky A.S. On the global extrema problem. Soviet Math. Doklad, 1987, vol. 292(5), pp. 1062-1066.
5. V.A. Zalgaller, An inequality for acute triangles. Ukr. Geom. Sb., 1991, vol. 34, pp. 10-25.
6. V.A. Zalgaller, The solution of Malfatti’s problem. Journal of Mathematical Sciences, 1994, vol.72, no 4, pp. 3163-3177.
7. G.A. Los, Malfatti’s Optimization Problem. [in Russian]. Dep. Ukr. NIINTI, July 5, 1988.
8. Saaty T. Integer Optimization Methods and Related Extremal Problems [Russian translation]. Moscow, Nauka, 1973.
9. Gabai H., Liban E. On Goldberg’s inequality associated with the Malfatti problem. Math. Mag., 1967, vol. 41, no 5, pp. 251-252.
10. Goldberg M. On the original Malfatti problem. Math. Mag., 1967, vol. 40, no 5, pp. 241-247.
11. H. Lob and H. W. Richmond, On the solutions of the Malfatti problem for a triangle. Proc. London Math. Soc., 1930, vol. 2, no 30, pp. 287-301.
12. C. Malfatti, Memoria sopra una problema stereotomico. Memoria di Matematica e di Fisica della Societa italiana della Scienze, 1803, vol. 10, no 1, pp. 235-244.