Универсальное программное обеспечение для оптимизации сложных систем

Abstract

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

Методика. В работе предлагается преобразовывать рассмотренные классы задач к единому каноническому виду, что позволяет ограничиться одним методом и использовать единое программное обеспечение.

Результаты. Для преобразования задач к каноническому виду используется точная квадратичная регуляризация, которая позволяет находить глобальные решения в задачах нелинейной оптимизации. Канонический вид является задачей максимизации нормы вектора на выпуклом множестве. Такая задача методом Келли преобразуется к максимизации нормы вектора на выпуклом многограннике. Используя точную квадратичную регуляризацию, выпуклый многогранник преобразуем к пересечению шаров. Задача максимума нормы вектора на пересечении шаров эффективно решается двойственным методом при помощи того же программного обеспечения.

Научная новизна. Разработана новая методология решений сложных оптимизационных задач, которые возникают при моделировании сложных систем.

Практическая значимость. Рассмотренная методика решения сложных задач нелинейной оптимизации реализована в виде программного обеспечения. Сравнительные эксперименты подтверждают эффективность данной методики при решении классов задач нелинейной оптимизации.

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

Методика. У роботі пропонується перетворювати розглянуті класи задач до єдиного канонічного вигляду, що дозволяє обмежиться одним методом та використовувати єдине програмне забезпечення.

Результати. Для перетворення задач до канонічного вигляду використовується точна квадратична регуляризація, яка дозволяє знаходити глобальні розв’язки в задачах нелінійної оптимізації. Канонічний вигляд є задачею максимізації норми вектора на опуклій множині. Така задача методом Келлі перетвориться до максимізації норми вектора на опуклому многограннику. Використовуючи точну квадратичну регуляризацію, опуклий многогранник перетворюємо до перетину куль. Задача максимуму норми вектора на перетині куль ефективно розв’язується двоїстим методом за допомогою того ж програмного забезпечення.

Наукова новизна. Розроблена нова методологія розв’язування складних оптимізаційних задач, які виникают при моделюванні складних систем.

Практична значимість. Розглянута методика розв’язування складних задач нелінійної оптимізації реалізована у вигляді програмного забезпечення. Порівняльні експерименти підтверджують ефективність даної методики при розв’язуванні класів задач нелінійної оптимізації.

EN: Purpose. We consider the class of problems of nonlinear optimization. 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 non-smooth functions. For each class of such problems developed many different methods and software that creates difficulties in solving them.

Methodology. We transform classes of problems to a single canonical form that allows to use only one method and use a single software.

Findings. Transformation use of the exact quadratic regularization, which allows us to find global solutions to the problems of nonlinear optimization. The canonical form is the task of maximizing the norm of a vector on a convex set. The method Kelly converted to the maximization norm of a vector on a convex polyhedron. At using exact quadratic regularization of a convex polyhedron transform to the intersection of the balls. The problem of the maximum norm of the vector at the intersection of the balls effectively solved the dual method using the same software.

Originality. We have developed new methodology for the solution of difficult optimizing problems which arise at modelling of difficult systems.

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.