Глобальная оптимизация сложных систем

Abstract

RU: Цель. В работе рассматриваются оптимизационные модели сложных систем. Такие модели возникают при проектировании, построении и управлении сложными системами. Оптимизационные модели сложных систем являются многоэкстремальными. Они включают оптимизацию с непрерывными, целочисленными, булевыми переменными, задачи на перестановках, задачи с гладкими и негладкими функциями. Задача состоит в том, чтобы разработать эффективные методы для решения таких классов. Методика. В работе предлагается преобразовывать рассмотренные классы задач к единому каноническому виду с помощью точной квадратичной регуляризации и использовать предложенную модификацию двойственности для канонической задачи. Результаты. Для преобразования задач к каноническому виду используется точная квадратичная регуляризация, которая позволяет находить глобальные решения в задачах нелинейной оптимизации. Канонический вид является задачей максимизации нормы вектора на выпуклом множестве. Это множество аппроксимируется пересечением шаров. Задача максимума нормы вектора на пересечении шаров эффективно решается двойственным методом. Научная новизна. Разработана новая методология решений сложных оптимизационных задач, которые возникают при моделировании сложных систем. Модифицирована теория двойственности для решения многоэкстремальных задач. Практическая значимость. Рассмотренная методика решения сложных задач нелинейной оптимизации реализована в виде программного обеспечения. Сравнительные эксперименты подтверждают эффективность данной методики при решении классов задач нелинейной оптимизации.

UK: Мета. У роботі розглядаються оптимізаційні моделі складних систем. Такі моделі виникають при проектуванні, побудові та управлінні складними системами. Оптимізаційні моделі складних систем є багатоекстремальними. Ці класи задач включають оптимізацію з неперервними, цілочисельними, булевими змінними, задачами на перестановках, задачами з гладкими та негладкими функціями. Задача полягає в тому, щоб розробити ефективні методи для розв’язку цього класу задач. Методика. У роботі пропонується перетворювати розглянуті класи задач до єдиного канонічного вигляду та використати запропоновану модифікацію двоїстості для канонічної задачі. Результати. Для перетворення задач до канонічного вигляду використовується точна квадратична регуляризація, яка дозволяє знаходити глобальні розв’язки в задачах нелінійної оптимізації. Канонічний вигляд є задачею максимізації норми вектора на опуклій множині. Ця множина апроксимується перетином куль. Задача максимуму норми вектора на перетині куль ефективно розв’язується двоїстим методом. Наукова новизна. Розроблена нова методологія розв’язування складних оптимізаційних задач, які виникають при моделюванні складних систем. Модифікована теорія двоїстості для розв’язку багатоекстремальных задач. Практична значимість. Розглянута методика розв’язування складних задач нелінійної оптимізації реалізована у вигляді програмного забезпечення. Порівняльні експерименти підтверджують ефективність даної методики при розв’язуванні класів задач нелінійної оптимізації.

EN: Purpose. We consider the optimization models of complex systems. Such problems arise in the design, construction and management of complex systems. In most cases, such problems are multiextremal. These classes include optimization problems with continuous, integer, Boolean variables, the problem on permutations, the problem with smooth and nonsmooth functions. We develop effective methods for the solution of such classes of problems. Methodology. We transform classes of problems to a single canonical form that allows to use the offered modification of a duality for a canonical problem. Findings. Transformation use of the exact quadratic regularization, which allows us to find global solutions to the problems of nonlinear optimization. The canon ical form is the task of maximizing the norm of a vector on a convex set. This set we is approximate by intersection of balls. The problem of the maximum norm of the vector at the intersection of the balls effectively solved the dual method. Originality. We have developed new methodology for the solution of difficult optimizing problems which arise at modelling of difficult systems. We modify the theory of a duality for the solution of multiextreme problems. Practical value. The considered technique for solving complex problems of nonlinear optimization is implemented in software. Comparative experiments confirm the effectiveness of this method for solving problems of nonlinear optimization classes.