On the global minimum ot the objective function in a balanced circular packing problem

1Stetsyuk, PI, 2Romanova, TE, 3Schiethauer, G
1V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
2A. N. Podgorny Institute for Mechanical Engineering Problems of the NAS of Ukraine, Kharkiv
3Institute of Scientific Computing of Technische Universität Dresden, Germany
Dopov. Nac. akad. nauk Ukr. 2014, 6:53-57
Section: Information Science and Cybernetics
Language: Russian

The paper considers the balanced packing problem of a given family of circles into a larger circle of the minimal radius as a multiextremal nonlinear programming problem. We reduce the problem to an unconstrained minimization problem of a non-smooth function by means of nonsmooth penalty functions. We propose an efficient algorithm to search for local extrema, as well as an algorithm of improvement of a lower estimate of the global minimum of the objective function. The algorithms use non-differentiable optimization methods based on Shor's r-algorithm. Computational test results are given.

Keywords: balanced circular packing, global minimum, objective function

1. Kovalenko A. A., Pankratov A. V., Romanova T. E., Stetsyuk P. I. Zhurn. obchysl. ta prykl. matematyky, 2013, No. 1(111): 126–134 (in Russian).
2. Stoyan Yu., Romanova T. Mathematical models of placement optimisation: two- and three-dimensional problems and applications. In: Fasano G., Pinter J. D. (Eds.). Modeling and Optimization in Space Engineering. New York: Springer, 2012: 363–388. https://doi.org/10.1007/978-1-4614-4469-5_15
3. Nenakhova E. I., Romanova T. E., Stetsyuk P. I. Equilibrium packing of circles in a circle of minimum radius. In: The theory of optimal solutions. Kyiv: Inst. of Cybernetics. Glushkov NAS of Ukraine, 2013: 143–153 (in Russian).
4. Shor N. Z., Stetsyuk P. I. Kibernetika i sistem. analiz., 1997, 4: 28–49 (in Russian).
5. Octave Retrieved from http://www.octave.org.
6. Shor N. Z. Nondifferentiable optimization and polynomial problems. Dordrecht: Kluwer, 1998. https://doi.org/10.1007/978-1-4757-6015-6