Please use this identifier to cite or link to this item:
http://srd.pgasa.dp.ua:8080/xmlui/handle/123456789/3064
Title: | Полуопределенная оптимизация для решения квадратичных задач с булевыми переменными |
Other Titles: | Напіввизначена оптимізація для розв'язування квадратичних задач з булевими змінними Semidefinite optimization for solving boolean quadratic problems |
Authors: | Косолап, Анатолий Иванович Косолап, Анатолій Іванович Kosolap, Anatoli Перетятько, Анастасия Сергеевна Перетятько, Анастасія Сергіївна Peretiatko, Anastasiia |
Keywords: | квадратичная оптимизация булевая оптимизация квадратичные задачи с булевыми переменными полуопределенная оптимизация полуопределенная релаксация нижние и верхние оценки квадратична оптимізація булева оптимізація квадратичні задачі з булевими змінними напіввизначена оптимізація напіввизначена релаксація нижні і верхні оцінки quadratic optimization boolean optimization boolean quadratic problems semidefinite optimization semidefinite relaxation lower and upper bounds |
Issue Date: | Sep-2016 |
Citation: | Косолап А. И. Полуопределенная оптимизация для решения квадратичных задач с булевыми переменными / А. И. Косолап, А. С. Перетятько // Строительство, материаловедение, машиностроение : сб. науч. тр. / Приднепр. гос. акад. стр-ва и архитектуры. – Днепр, 2016. – Вып. 94. – С. 101-106. – (Компьютерные системы и информационные технологии в образовании, науке и управлении). |
Abstract: | RU: Цель. В работе рассматривается класс задач квадратичной оптимизации с булевыми переменными. Такие задачи возникают в области рыночной экономики, планировании, управлении проектами, искусственном интеллекте, оптимальном проектировании и являются NP-сложными. В данной работе предлагается процедура для нахождения нижних и верхних оценок целевых функций квадратичных задач с булевыми переменными. Методика. В данной работе предлагается преобразовывать квадратичные задачи с булевыми переменными в общую задачу квадратичной оптимизации, а затем применять для ее решения метод полуопределенной релаксации. Результаты. Применение полуопределенной релаксации позволило находить нижние оценки целевой функции в квадратичных задачах с булевыми переменными или точку глобального минимума с заданной точностью. Причем, в отличие от других методов, проверка оптимальности найденного решения не требует экспоненциального времени и достаточно проста. Верхняя оценка целевой функции, которая находится с помощью использования нижней оценки полуопределенной релаксации в качестве начальной точки при решении исходной задачи методами локального поиска, в 91 % случаев совпала с глобальным минимумом начальной задачи. Научная новизна. Разработана новая процедура нахождения верхних и нижних оценок целевой функции. Практическая значимость. Рассмотренная методика решения может быть использована для нахождения решения прикладных задач, которые могут быть сформулированы в виде квадратичных задач с булевыми переменными. Сравнительные эксперименты подтверждают эффективность данного подхода для решения таких задач. UK: Мета. У роботі розглядається клас задач квадратичної оптимізації з булевими змінними. Такі задачі виникають в області ринкової економіки, планування, управління проектами, штучному інтелекті, оптимальному проектуванні та є NP-складними. У даній роботі пропонується процедура для знаходження нижніх і верхніх оцінок цільових функцій квадратичних задач з булевими змінними. Методика. У даній роботі пропонується перетворювати квадратичні задачі з булевими змінними в загальну задачу квадратичної оптимізації, а потім застосовувати для її розв'язання метод напіввизначеної релаксації. Результати. Застосування напіввизначеної релаксації дозволило знаходити нижні оцінки цільової функції в квадратичних задачах з булевими змінними або точку глобального мінімуму з заданою точністю. Причому, на відміну від інших методів, перевірка оптимальності знайденого розв'язку не вимагає експоненціального часу і є досить простою. Верхня оцінка цільової функції, яка знаходиться за допомогою використання нижньої оцінки напіввизначеної релаксації в якості початкової точки під час розв'язування вихідної задачі методами локального пошуку, в 91% випадків збіглася з глобальним мінімумом початкової задачі. Наукова новизна. Розроблено нову процедуру знаходження верхніх і нижніх оцінок цільової функції. Практична значимість. Розглянута методика розв'язання може бути використана для знаходження розв'язку прикладних задач, які можуть бути сформульовані у вигляді квадратичних задач з булевими змінними. Порівняльні експерименти підтверджують ефективність даного підходу для розв'язування таких задач. EN: Purpose. We consider boolean quadratic optimization problems. Such problems arise in market economy, planning, project management, artificial intelligence, optimal design and are NP-hard. In this paper we propose a procedure for finding the lower and upper bounds of the objective functions of boolean quadratic problems. Methodology. In this paper we propose to convert the boolean quadratic problem to the general quadratic optimization problem, and then apply semi definite relaxation to it. Findings. The using of semidefinite relaxation has allowed us to find lower bounds of the objective function or global minimum point with a given accuracy in boolean quadratic problems. Moreover, unlike other methods, testing the optimality of the found solution doesn`t require exponential time and is quite simple. The upper bound of the objective function, which is found by using the lower es timate of semidefinite relaxation as a starting point for solving the original problem by local search methods, in 91% of cases coincided with the global minimum of the initial problem. Originality. A new procedure for finding the upper and lower bounds of objective function was proposed. Practical value. The considered method of solution can be used for finding the solution in applications that can be formulated as boolean quadratic problems. Comparative numerical experiments confirm the efficiency of this approach to solvin g such problems. |
URI: | http://srd.pgasa.dp.ua:8080/xmlui/handle/123456789/3064 |
Other Identifiers: | http://smm.pgasa.dp.ua/article/view/107149 |
Appears in Collections: | Вып. 94 |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Kosolap.pdf | 826,22 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.