American Institute of Mathematical Sciences

Advanced
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.21293.6336
6.7104-0.07511.1775
0.4961-4.55300.9282
Table Options

Download as excel

$x^*_1$$x^*_2$$r^*$
1.9011-0.21293.6336
6.7104-0.07511.1775
0.4961-4.55300.9282
Table 2.  Test Problem 1 for $K=4$
$x^*_1$$x^*_2$$r^*$
1.9609-0.28493.6675
6.7807-0.08981.1563
0.4795-4.60230.8969
0.39783.88280.7834
Table Options

Download as excel

$x^*_1$$x^*_2$$r^*$
1.9609-0.28493.6675
6.7807-0.08981.1563
0.4795-4.60230.8969
0.39783.88280.7834
Table 3.  Test Problem 1 for $K=5$
$x^*_1$$x^*_2$$r^*$
1.9607-0.28493.6677
6.7799-0.08991.1567
0.4796-4.60200.8972
0.39733.88220.7841
-0.3701-3.62010.4016
Table Options

Download as excel

$x^*_1$$x^*_2$$r^*$
1.9607-0.28493.6677
6.7799-0.08991.1567
0.4796-4.60200.8972
0.39733.88220.7841
-0.3701-3.62010.4016
Table 4.  Test Problem 2 for $K=3, 4, 5$
K$x^*_1$$x^*_2$$r^*$
11.26013.46853.4685
25.49231.29051.2905
3-2.4751.00561.0056
45.20513.05590.4981
53.88880.49800.4981
Table Options

Download as excel

K$x^*_1$$x^*_2$$r^*$
11.26013.46853.4685
25.49231.29051.2905
3-2.4751.00561.0056
45.20513.05590.4981
53.88880.49800.4981
Table 5.  Test Problem 3 for $K=3, 4, 5$
$x^*_1$$x^*_2$$r^*$
0.71873.85093.8509
5.77491.65971.6597
-3.82821.34221.3422
5.28073.98030.7129
7.79980.61760.6176
Table Options

Download as excel

$x^*_1$$x^*_2$$r^*$
0.71873.85093.8509
5.77491.65971.6597
-3.82821.34221.3422
5.28073.98030.7129
7.79980.61760.6176
[1]

Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045
[2]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031
[3]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[4]

Mengni Li. Global regularity for a class of Monge-Ampère type equations with nonzero boundary conditions. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020267
[5]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115
[6]

Haiyu Liu, Rongmin Zhu, Yuxian Geng. Gorenstein global dimensions relative to balanced pairs. Electronic Research Archive, 2020, 28 (4) : 1563-1571. doi: 10.3934/era.2020082
[7]

Jianhua Huang, Yanbin Tang, Ming Wang. Singular support of the global attractor for a damped BBM equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020345
[8]

João Marcos do Ó, Bruno Ribeiro, Bernhard Ruf. Hamiltonian elliptic systems in dimension two with arbitrary and double exponential growth conditions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 277-296. doi: 10.3934/dcds.2020138
[9]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251
[10]

Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253
[11]

Cheng He, Changzheng Qu. Global weak solutions for the two-component Novikov equation. Electronic Research Archive, 2020, 28 (4) : 1545-1562. doi: 10.3934/era.2020081
[12]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077
[13]

Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384
[14]

H. M. Srivastava, H. I. Abdel-Gawad, Khaled Mohammed Saad. Oscillatory states and patterns formation in a two-cell cubic autocatalytic reaction-diffusion model subjected to the Dirichlet conditions. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020433
[15]

Pengyu Chen. Non-autonomous stochastic evolution equations with nonlinear noise and nonlocal conditions governed by noncompact evolution families. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020383
[16]

Ahmad Z. Fino, Wenhui Chen. A global existence result for two-dimensional semilinear strongly damped wave equation with mixed nonlinearity in an exterior domain. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5387-5411. doi: 10.3934/cpaa.2020243
[17]

Bo Chen, Youde Wang. Global weak solutions for Landau-Lifshitz flows and heat flows associated to micromagnetic energy functional. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020268
[18]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453
[19]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075
[20]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

 Impact Factor: 

Tools

Metrics

  • PDF downloads (98)
  • HTML views (130)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences