Global optimization reduction of generalized Malfatti's problem

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

June 2017, 7(2): 211-221. doi: 10.3934/naco.2017015

Global optimization reduction of generalized Malfatti's problem

Rentsen Enkhbat ^1,, , Evgeniya A. Finkelstein ^2, , Anton S. Anikin ^2, and Alexandr Yu. Gornov ^2,

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

Received December 2016 Revised May 2017 Published June 2017

Fund Project: 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

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: Malfatti's problem, global optimization, algorithm, optimality conditions.

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

Citation: Rentsen Enkhbat, Evgeniya A. Finkelstein, Anton S. Anikin, Alexandr Yu. Gornov. Global optimization reduction of generalized Malfatti's problem. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 211-221. doi: 10.3934/naco.2017015

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. Google Scholar
[2]	N. Andrei, Hybrid conjugate gradient algorithm for unconstrained optimization}, JOTA, 141 (2009), 249-264. doi: 10.1007/s10957-008-9505-0. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[8]	R. P. Fedorenko, Approximate solution of some optimal control problems}, USSR Computational Mathematics and Mathematical Physics, 4 (1964), 89-116. Google Scholar
[9]	H. Gabai and E. Liban, On Goldberg's inequality associated with the Malfatti problem}, Math. Mag., 41 (1967), 251-252. Google Scholar
[10]	N. Gernet, The Fundamental Problem of the Calculus of Variations, St. Petersburg, Erlich, (1913), [in Russian].Google Scholar
[11]	M. Goldberg, On the original Malfatti problem, Math. Mag., 40 (1967), 241-247. Google Scholar
[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. Google Scholar
[13]	G. A. Los, Malfatti's optimization problem, Dep. Ukr. NIINTI, July 5,1988, in Russian.Google Scholar
[14]	G. Malfatti, Memoria sopra una problema stereotomico, Memoria di Matematica e di Fisica della Societa italiana della Scienze, 10 (1803), 235-244. Google Scholar
[15]	H. Melissen, Packing and Covering with Circles, Thesis, Univ. Utrecht, 1997.Google Scholar
[16]	B. T. Polyak, The conjugate gradient method in extremal problems, USSR Computational Mathematics and Mathematical Physics, 9 (1969), 94-112. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[21]	A. S. Strekalovsky, On the global extrema problem, Soviet Math. Doklad, 292 (1987), 1062-1066. Google Scholar
[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. Google Scholar
[23]	F. A. Valentine, The problem of Lagrange with differential inequalities as added side conditions, Dissertation Univ. of Chicago, 1937. Google Scholar
[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. Google Scholar

show all references

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. Google Scholar
[2]	N. Andrei, Hybrid conjugate gradient algorithm for unconstrained optimization}, JOTA, 141 (2009), 249-264. doi: 10.1007/s10957-008-9505-0. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[8]	R. P. Fedorenko, Approximate solution of some optimal control problems}, USSR Computational Mathematics and Mathematical Physics, 4 (1964), 89-116. Google Scholar
[9]	H. Gabai and E. Liban, On Goldberg's inequality associated with the Malfatti problem}, Math. Mag., 41 (1967), 251-252. Google Scholar
[10]	N. Gernet, The Fundamental Problem of the Calculus of Variations, St. Petersburg, Erlich, (1913), [in Russian].Google Scholar
[11]	M. Goldberg, On the original Malfatti problem, Math. Mag., 40 (1967), 241-247. Google Scholar
[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. Google Scholar
[13]	G. A. Los, Malfatti's optimization problem, Dep. Ukr. NIINTI, July 5,1988, in Russian.Google Scholar
[14]	G. Malfatti, Memoria sopra una problema stereotomico, Memoria di Matematica e di Fisica della Societa italiana della Scienze, 10 (1803), 235-244. Google Scholar
[15]	H. Melissen, Packing and Covering with Circles, Thesis, Univ. Utrecht, 1997.Google Scholar
[16]	B. T. Polyak, The conjugate gradient method in extremal problems, USSR Computational Mathematics and Mathematical Physics, 9 (1969), 94-112. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[21]	A. S. Strekalovsky, On the global extrema problem, Soviet Math. Doklad, 292 (1987), 1062-1066. Google Scholar
[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. Google Scholar
[23]	F. A. Valentine, The problem of Lagrange with differential inequalities as added side conditions, Dissertation Univ. of Chicago, 1937. Google Scholar
[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. Google Scholar

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

Figure Options

Download full-size image

Download as PowerPoint slide

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

Figure Options

Download full-size image

Download as PowerPoint slide

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

Figure Options

Download full-size image

Download as PowerPoint slide

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

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5. Spheres placed into test polyhedron 5

Figure Options

Download full-size image

Download as 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

Table Options

Download as excel

$x^*_1$	$x^*_2$	$r^*$
1.9011	-0.2129	3.6336
6.7104	-0.0751	1.1775
0.4961	-4.5530	0.9282

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

Table Options

Download as excel

$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

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

Table Options

Download as excel

$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

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

Table Options

Download as excel

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

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

Table Options

Download as excel

$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

[1]	Rentsen Enkhbat, M. V. Barkova, A. S. Strekalovsky. Solving Malfatti's high dimensional problem by global optimization. Numerical Algebra, Control & Optimization, 2016, 6 (2) : 153-160. doi: 10.3934/naco.2016005
[2]	Yong Xia. New sufficient global optimality conditions for linearly constrained bivalent quadratic optimization problems. Journal of Industrial & Management Optimization, 2009, 5 (4) : 881-892. doi: 10.3934/jimo.2009.5.881
[3]	Ying Gao, Xinmin Yang, Kok Lay Teo. Optimality conditions for approximate solutions of vector optimization problems. Journal of Industrial & Management Optimization, 2011, 7 (2) : 483-496. doi: 10.3934/jimo.2011.7.483
[4]	Gaoxi Li, Zhongping Wan, Jia-wei Chen, Xiaoke Zhao. Necessary optimality condition for trilevel optimization problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2018140
[5]	Henri Bonnel, Ngoc Sang Pham. Nonsmooth optimization over the (weakly or properly) Pareto set of a linear-quadratic multi-objective control problem: Explicit optimality conditions. Journal of Industrial & Management Optimization, 2011, 7 (4) : 789-809. doi: 10.3934/jimo.2011.7.789
[6]	Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67
[7]	Monika Laskawy. Optimality conditions of the first eigenvalue of a fourth order Steklov problem. Communications on Pure & Applied Analysis, 2017, 16 (5) : 1843-1859. doi: 10.3934/cpaa.2017089
[8]	Chia-Huang Wu, Kuo-Hsiung Wang, Jau-Chuan Ke, Jyh-Bin Ke. A heuristic algorithm for the optimization of M/M/$s$ queue with multiple working vacations. Journal of Industrial & Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1
[9]	Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089
[10]	Tadeusz Antczak, Najeeb Abdulaleem. Optimality conditions for $ E $-differentiable vector optimization problems with the multiple interval-valued objective function. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2019089
[11]	Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177
[12]	Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19
[13]	Thierry Horsin, Peter I. Kogut, Olivier Wilk. Optimal $L^2$-control problem in coefficients for a linear elliptic equation. II. Approximation of solutions and optimality conditions. Mathematical Control & Related Fields, 2016, 6 (4) : 595-628. doi: 10.3934/mcrf.2016017
[14]	Ciro D'Apice, Olha P. Kupenko, Rosanna Manzo. On boundary optimal control problem for an arterial system: First-order optimality conditions. Networks & Heterogeneous Media, 2018, 13 (4) : 585-607. doi: 10.3934/nhm.2018027
[15]	Vladimir Gaitsgory, Alex Parkinson, Ilya Shvartsman. Linear programming based optimality conditions and approximate solution of a deterministic infinite horizon discounted optimal control problem in discrete time. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1743-1767. doi: 10.3934/dcdsb.2018235
[16]	Dariusz Idczak, Stanisław Walczak. Necessary optimality conditions for an integro-differential Bolza problem via Dubovitskii-Milyutin method. Discrete & Continuous Dynamical Systems - B, 2019, 24 (5) : 2281-2292. doi: 10.3934/dcdsb.2019095
[17]	B. Bonnard, J.-B. Caillau, E. Trélat. Second order optimality conditions with applications. Conference Publications, 2007, 2007 (Special) : 145-154. doi: 10.3934/proc.2007.2007.145
[18]	Jaroslav Haslinger, Raino A. E. Mäkinen, Jan Stebel. Shape optimization for Stokes problem with threshold slip boundary conditions. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1281-1301. doi: 10.3934/dcdss.2017069
[19]	Jingzhen Liu, Ka Fai Cedric Yiu, Alain Bensoussan. Optimality of (s, S) policies with nonlinear processes. Discrete & Continuous Dynamical Systems - B, 2017, 22 (1) : 161-185. doi: 10.3934/dcdsb.2017008
[20]	Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215

Impact Factor:

Tools

Metrics

Tools

Article outline

Figures and Tables

Impact Factor:

Tools

Figures and Tables

Impact Factor:

American Institute of Mathematical Sciences