О глобальном минимуме целевой функции в задаче равновесной упаковки кругов

• Published in: Доповіді НАН України
• Date: 2014
• Main Authors: Стецюк, П.И., Романова, Т.Е., Шайтхауэр, Г.
• Format: Article
• Language: Russian
• Published: Видавничий дім "Академперіодика" НАН України 2014
• Subjects: Інформатика та кібернетика
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/87814
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: О глобальном минимуме целевой функции в задаче равновесной упаковки кругов / П.И. Стецюк, Т.Е. Романова, Г. Шайтхауэр // Доповiдi Нацiональної академiї наук України. — 2014. — № 6. — С. 53-57. — Бібліогр.: 6 назв. — рос.

Рассматривается задача равновесной упаковки семейства кругов в круге минимального радиуса в виде многоэкстремальной задачи нелинейного программирования. С помощью негладких штрафов задача сводится к задаче безусловной минимизации негладкой функции. Предлагается алгоритм поиска локальных экстремумов негладкой функции и алгоритм уточнения оценки снизу для значения глобального минимума целевой функции, которые базируются на использовании методов оптимизации негладких функций с применением модификации r-алгоритма Шора. Приводятся результаты тестовых экспериментов. Розглядається задача рiвноважної упаковки сiмейства кругiв у круг мiнiмального радiуса у виглядi багатоекстремальної задачi нелiнiйного програмування. За допомогою негладких штрафiв задача зводиться до задачi безумовної мiнiмiзацiї негладкої функцiї. Пропонується алгоритм пошуку локальних екстремумiв негладкої функцiї i алгоритм уточнення оцiнки знизу для значення глобального мiнiмуму цiльової функцiї, якi базуються на застосуваннi методiв оптимiзацiї негладких функцiй iз використанням модифiкацiї r-алгоритму Шора. Наводяться результати тестових експериментiв. 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.