Multi-objective Optimization Approach to Malfatti’s Problem

Authors

  • Rentsen Enkhbat Institute of Mathematics and Digital Technology, Academy of Sciences of Mongolia, Ulaanbaatar, Mongolia
  • Gompil Battur Department of Applied Mathematics, National university of Mongolia, Ulaanbaatar, Mongolia

DOI:

https://doi.org/10.21638/11701/spbu31.2021.07

Abstract

In this work, we consider the multi-objective optimization problem based on the circle packing problem, particularly, extended Malfatti's problem (Enkhbat, 2020) with k disks. Malfatti's problem was examined for the first time from a view point of global optimization theory and algorithm in (Enkhbat, 2016). Also, a game theory approach has been applied to Malfatti's problem in (Enkhbat and Battur, 2021). In this paper, we apply the the multi-objective optimization approach to the problem. Using the weighted sum method, we reduce this problem to optimization problem with nonconvex constraints. For solving numerically the weighted sum optimization problem, we apply KKT conditions and find Pareto stationary points. Also, we estimate upper bounds of the global value of the objective function by Lagrange duality. Numerical results are provided.

Keywords:

circle packing problem, triangle set, k disks, multi-objective optimization problem, upper bound

Downloads

Download data is not yet available.
 

References

Nguyen, V. H. and J. J. Strodiot (1992). Computing a Global Optimal Solution to a Design Centering Problem. Mathematical Programming, 53, 111–123

Vidigal, L. M. and S. W. Director (1982). A Design Centering Algorithm for Nonconvex Regions of Acceptability. IEEE Transactions on Computer-Aided-Design of Integrated Circuits and Systems, CAD-1 pp. 13–24

Fraser, H. J. and J. A. George (1994). Integrated container loading software for pulp and paper industry. European Journal of Operational Research, 77, 466–474

Dowsland, K. A. (1991). Optimising the palletisation of cylinders in cases. OR Spectrum 13, 204–212

Enkhbat, R. (1996). An algorithm for maximizing a convey function over a simple set. Journal of Global Optimization, 8, 379–391

Enkhbat, R. (2016). Global optimization approach to Malfatti's problem. Journal of Global Optimization, 65, 33–39

Enkhbat, R. and M. Barkova (2019). Global search method for solving Malfatti's four-circle problem. The Bulletin of Irkutsk State University. Series Mathematics, 15, 38–49

Enkhbat, R. (2020). Convex Maximization Formulation of General Sphere Packing Problem. The Bulletin of Irkutsk State University. Series Mathematics, 31, 142–149

Enkhbat, R., Battur, G. (2021). Generalized Nash equilibrium problem based on Malfatti's problem. Numerical Algebra, Control and Optimization, 11(2), 209–220

Andreatta, M., Bezdek, A., Boronski, J. P.(2011). The Problem of Malfatti: Two Centuries of Debate. The Mathematical Intelligencer, 33(1), 72–76

Nefedov, V. N. (1987). Finding the Global Maximum of a Function of Several Variables on a Set Given by Inequality Constraints. Journal of Numerical Mathematics and Mathematical Physics, 27(1), 35–51

Strekalovsky, A. S. (1987). On the global extrema problem. Soviet Math. Doklad, 292(5), 1062–1066

Zalgaller, V. A. (1991). An inequality for acute triangles. Ukr. Geom. Sb., 34, 10–25

Zalgaller, V. A. and G. A. Los (1994). The solution of Malfatti's problem. Journal of Mathematical Sciences, 72(4), 3163–3177

Los, G. A. (1988). Malfatti's Optimization Problem [in Russian], Dep. Ukr. NIINTI July 5, 1988

Saaty, T. (1973). Integer Optimization Methods and Related Extremal Problems [Russian translation], Moscow

Gabai, H. and E. Liban (1967). On Goldberg's inequality associated with the Malfatti problem. Math. Mag., 41(5), 251–252

Goldberg, M. (1967). On the original Malfatti problem. Math. Mag., 40(5), 241–247

Lob, H. and H. W. Richmond (1930). On the solutions of the Malfatti problem for a triangle. Proc. London Math. Soc., 2(30), 287–301

Malfatti, C. (1803). Memoria sopra una problema stereotomico. Memoria di Matematica e di Fisica della Societa ttaliana della Scienze, 10(1), 235–244

Boyd, S. and L. Vandenberghe (2004). Convex Optimization, Cambridge University Press

Bertsekas, D. P. (2016). Nonlinear programming

Ehrgott, M. (2005). Multicriteria Optimization, Springer Berlin-Heidelberg

Downloads

Published

2021-10-30

How to Cite

Enkhbat, R., & Battur, G. (2021). Multi-objective Optimization Approach to Malfatti’s Problem. Contributions to Game Theory and Management, 14, 82–90. https://doi.org/10.21638/11701/spbu31.2021.07

Issue

Section

Articles

Most read articles by the same author(s)