Уточнение оценок решений в полуопределенном программировании

Abstract

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

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

EN: Purpose. We develop new methods for solving optimization models of complex systems. Such models arise in technology, artificial intelligence, design, construction and management of complex systems. Solving such optimization problems is a complex computational problem. This problem is to develop effective methods for solving such classes. Methodology. In this paper, we propose to transform the classes of problems to problems of semidefinite programming and to use their solutions for primer-dual interior point methods. We propose an iterative procedure for modifying the corresponding problem of semidefinite programming, which makes it possible to find exact solutions of the original problem. Findings. To solve the problems of quadratic optimization, semi-definite relaxation and a direct-dual method of the interior point are used. An iterative procedure for modifying semidefinite programming problems is constructed, which makes it possible to obtain an exact solution of the original problem. The obtained results are confirmed by numerical experiments. Originality. A new methodology for solving complex optimization problems that arise in modeling complex systems using semidefinite relaxation is developed. A sequential modification of the problems of semidefinite optimization is proposed. Practical value. We considered technique for solving complex quadratic optimization problems is realized in the form of software. Comparative experiments confirm the effectiveness of this technique in solving classes of problems of quadratic optimization.