Global optimization reduction of generalized Malfatti's problem

Rentsen Enkhbat; Evgeniya A. Finkelstein; Anton S. Anikin; Alexandr Yu. Gornov

doi:10.3934/naco.2017015

Article Contents

2017, Volume 7, Issue 2: 211-221. Doi: 10.3934/naco.2017015

This issue Previous Article Feedback necessary optimality conditions for a class of terminally constrained state-linear variational problems inspired by impulsive control Next Article

Global optimization reduction of generalized Malfatti's problem

1.
Institute of Mathematics, National University of Mongolia, 210646, Ulaanbaatar, Mongolia
2.
Matrosov Institute for Systems Dynamics and Control Theory SB RAS, 664033, Irkutsk, Russia

^* Corresponding author: R.Enkhbat
^* Corresponding author: R.Enkhbat

Received: December 2016

Revised: May 2017

Published: October 2017

This paper was prepared at the occasion of The 10th International Conference on Optimization: Techniques and Applications (ICOTA 2016), Ulaanbaatar, Mongolia, July 23-26,2016, with its Associate Editors of Numerical Algebra, Control and Optimization (NACO) being Prof. Dr. Zhiyou Wu, School of Mathematical Sciences, Chongqing Normal University, Chongqing, China, Prof. Dr. Changjun Yu, Department of Mathematics and Statistics, Curtin University, Perth, Australia, and Shanghai University, China, and Prof. Gerhard-Wilhelm Weber, Middle East Technical University, Ankara, Turkey.

Abstract Full Text(HTML) Figure(5) / Table(5) Related Papers Cited by

Abstract

In this paper, we generalize Malfatti's problem as a continuation of works [6,7]. The problem has been formulated as a global optimization problem. To solve Malfatti's problem numerically, we propose the co-called ''Hill method'' which is based on a heuristic approach. Some computational results for two and three-dimensional test problems are provided.

Keywords:

Mathematics Subject Classification: Primary: 49K, 65K10; Secondary: 90C26.

Citation:

Full Text(HTML)

Figure 1. Three, four, and five circles inscribed in the set $D$ of Test 1

Download: Full-size image PowerPoint slide

Figure 2. Circles for $K=3$ and $K=5$ for test problem 2

Download: Full-size image PowerPoint slide

Figure 3. Circles placed into the test polygon 3 for $K=3, 5$

Download: Full-size image PowerPoint slide

Figure 4. Spheres placed into polyhedron for $K=3$ and $K=5$

Download: Full-size image PowerPoint slide

Figure 5. Spheres placed into test polyhedron 5

Download: Full-size image PowerPoint slide

Table 1. Test Problem 1 for $K=3$

$x^*_1$ $x^*_2$ $r^*$

1.9011 -0.2129 3.6336
6.7104 -0.0751 1.1775
0.4961 -4.5530 0.9282

| Show Table

DownLoad: CSV

Table 2. Test Problem 1 for $K=4$

$x^*_1$ $x^*_2$ $r^*$

1.9609 -0.2849 3.6675
6.7807 -0.0898 1.1563
0.4795 -4.6023 0.8969
0.3978 3.8828 0.7834

| Show Table

DownLoad: CSV

Table 3. Test Problem 1 for $K=5$

$x^*_1$ $x^*_2$ $r^*$

1.9607 -0.2849 3.6677
6.7799 -0.0899 1.1567
0.4796 -4.6020 0.8972
0.3973 3.8822 0.7841
-0.3701 -3.6201 0.4016

| Show Table

DownLoad: CSV

Table 4. Test Problem 2 for $K=3, 4, 5$

K $x^*_1$ $x^*_2$ $r^*$

1 1.2601 3.4685 3.4685
2 5.4923 1.2905 1.2905
3 -2.475 1.0056 1.0056
4 5.2051 3.0559 0.4981
5 3.8888 0.4980 0.4981

| Show Table

DownLoad: CSV

Table 5. Test Problem 3 for $K=3, 4, 5$

$x^*_1$ $x^*_2$ $r^*$

0.7187 3.8509 3.8509
5.7749 1.6597 1.6597
-3.8282 1.3422 1.3422
5.2807 3.9803 0.7129
7.7998 0.6176 0.6176

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	M. Andreatta, A. Bezdek and Jan P. Boroski, The problem of Malfatti: Two centuries of debate, The Mathematical Intelligencer, 33 (2011), 72-76. doi: 10.1007/s00283-010-9154-7.
[2]	N. Andrei, Hybrid conjugate gradient algorithm for unconstrained optimization}, JOTA, 141 (2009), 249-264. doi: 10.1007/s10957-008-9505-0.
[3]	A. Anikin, A. Gornov and A. Andrianov, Computational technologies for Morse potential optimization, Abstracts of IV Internetional conference ''Optimization and applications'' (OPTIMA-2013), (2013), 22-23.
[4]	J. W. David and J. P. K. Doye, 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, 28 (1997), 5111-5116.
[5]	R. Enkhbat, An algorithm for maximizing a convex function over a simple set}, Journal of Global Optimization, 8 (1996), 379-391. doi: 10.1007/BF02403999.
[6]	R. Enkhbat, Global optimization approach to Malfatti's problem}, Journal of Global Optimization, 65 (2016), 33-39. doi: 10.1007/s10898-015-0372-6.
[7]	R. Enkhbat, M. V. Barkova and M. V. Strekalovsky, Solving Malfatti's high dimensional problem by global optimization}, Numerical Algebra, Control and Optimization, 6 (2016), 153-160. doi: 10.3934/naco.2016005.
[8]	R. P. Fedorenko, Approximate solution of some optimal control problems}, USSR Computational Mathematics and Mathematical Physics, 4 (1964), 89-116.
[9]	H. Gabai and E. Liban, On Goldberg's inequality associated with the Malfatti problem}, Math. Mag., 41 (1967), 251-252.
[10]	N. Gernet, The Fundamental Problem of the Calculus of Variations, St. Petersburg, Erlich, (1913), [in Russian].
[11]	M. Goldberg, On the original Malfatti problem, Math. Mag., 40 (1967), 241-247.
[12]	H. Lob and H. W. Richmond, On the solutions of the Malfatti problem for a triangle, Proc. London Math. Soc., 2 (1930), 287-301. doi: 10.1112/plms/s2-30.1.287.
[13]	G. A. Los, Malfatti's optimization problem, Dep. Ukr. NIINTI, July 5,1988, in Russian.
[14]	G. Malfatti, Memoria sopra una problema stereotomico, Memoria di Matematica e di Fisica della Societa italiana della Scienze, 10 (1803), 235-244.
[15]	H. Melissen, Packing and Covering with Circles, Thesis, Univ. Utrecht, 1997.
[16]	B. T. Polyak, The conjugate gradient method in extremal problems, USSR Computational Mathematics and Mathematical Physics, 9 (1969), 94-112.
[17]	M. Pervin, S. K. Roy and G. W. Weber, A Two-echelon inventory model with stock-dependent demand and variable holding cost for deteriorating items, Numerical Algebra, Control and Optimization, 7 (2016), 21-50. doi: 10.3934/naco.2017002.
[18]	M. Pervin, S. K. Roy and G. W. Weber, Analysis of inventory control model with shortage under time-dependent demand and time-varying holding cost including stochastic deterioration, Annals of Operations Research, (2016), DOI: 10. 1007/s10479-016-2355-5. doi: 10.1007/s10479-016-2355-5.
[19]	S. K. Roy, G. Maity, G. W. Weber and S. Z. Alparslan Gok, Conic Scalarization approach to solve multi-choice multi-objective transportation problem with interval goal, Annals of Operations Research, (2016), DOI: 10. 1007/s10479-016-2283-4. doi: 10.1007/s10479-016-2283-4.
[20]	S. K. Roy, G. Maity and G. W. Weber, Multi-objective two-stage grey transportation problem using utility function with goals, Central European Journal of Operations Research, 25 (2017), 417-439. doi: 10.1007/s10100-016-0464-5.
[21]	A. S. Strekalovsky, On the global extrema problem, Soviet Math. Doklad, 292 (1987), 1062-1066.
[22]	K. L. Teo, C. J. Goh and K. H. Wong, A unified computational approach to optimal control problems, Pitman Monographs and Surveys in Pure and Applied Mathematics. New York, Longman Scientific & Technical, 1991.
[23]	F. A. Valentine, The problem of Lagrange with differential inequalities as added side conditions, Dissertation Univ. of Chicago, 1937.
[24]	V. A. Zalgaller and G. A. Los, The solution of Malfatti's problem, Journal of Mathematical Sciences, 72 (1994), 3163-3177. doi: 10.1007/BF01249514.