Эффективное решение квадратичных задач методами полуопределенной оптимизации

Abstract

RU: Цель. Целью данной статьи является разработка новых и эффективных методов решения квадратичных задач. Такие задачи возникают в экономике, финансах, управлении, технологических процессах, информатике и других областях. Отличительной особенностью этих задач является их большая размерность и сложность для численного решения. В работе рассматривается модификация задач полуопределенной оптимизации, которая позволяет находить более точные оценки решений квадратичных задач. Методика. В данной работе квадратичные задачи преобразовываются в общую задачу полуопределенной оптимизации, а затем для ее решения применяется метод локального поиска. Условия неотрицательности переменных записываются в виде квадратичных ограничений хі (хі - а) ≤ 0. Число таких ограничений равно n. Вид таких ограничений в формулировке задачи полуопределенной оптимизации представляет собой матрицы с последовательным сдвигом ненулевых элементов. Значение a выбирается таким, чтобы выполнялось условие x ≤ a. При решении задач полуопределенной оптимизации использовалась вариация параметра a. Результаты. Были проведены сравнительные вычислительные эксперименты с задачами разной размерности. Для решения использовался эволюционный поиск и полуопределенная оптимизация. Во всех случаях метод полуопределенной оптимизации с локальным поиском давал лучшее решение. Как показали численные эксперименты, величина параметра a влияет на точность оценки решения исходной квадратичной задачи. Уменьшение этого параметра позволяет получать более точные оценки решения. Научная новизна. В работе предлагается для решения общих квадратичных задач использовать методы полуопределенной оптимизации с локальным поиском, а для уточнения полуопределенной релаксации – производить последовательное сужение допустимой области путем вариации параметра а. Практическая значимость. Рассмотренная методика поиска решения может быть использована для нахождения решения прикладных задач, которые могут быть сформулированы в виде общих задач квадратичной оптимизации. Сравнительные эксперименты подтверждают эффективность данного подхода для решения таких задач.

UK: Мета. Метою даної статті є розробка нових і ефективних методів розв'язання квадратичних задач. Такі задачі виникають в економіці, фінансах, управлінні, технологічних процесах, інформатиці та інших областях. Відмінною особливістю цих задач є їх велика розмірність і складність для чисельного розв’язування. В роботі розглядається модифікація задач напіввизначеної оптимізації, яка дозволяє знаходити більш точні оцінки розв’язків квадратичних задач. Методика. У даній роботі квадратичні задачі перетворюються в загальну задачу напіввизначеної оптимізації, а потім для її розв’язання застосовується метод локального пошуку. Умови невід'ємності змінних записуються у вигляді квадратичних обмежень хі (хі - а) ≤ 0. Число таких обмежень дорівнює n. Вид таких обмежень в формулюванні задачі напіввизначеної оптимізації являє собою матриці з послідовним зсувом ненульових елементів. Значення a обирається таким, щоб виконувалася умова x ≤ a. При розв’язуванні задач напіввизначеної оптимізації використовувалася варіація параметра a. Результати. Були проведені порівняльні обчислювальні експерименти з задачами різної розмірності. Для розв’язання використовувався еволюційний пошук і напіввизначена оптимізація. У всіх випадках метод напіввизначеної оптимізації з локальним пошуком давав кращий розв’язок. Як показали чисельні експерименти, величина параметра a впливає на точність оцінки розв’язку вихідної квадратичної задачі. Зменшення цього параметра дозволяє отримувати більш точні оцінки розв’язку. Наукова новизна. У роботі для розв’язання загальних квадратичних задач пропонується використовувати методи напіввизначеної оптимізації з локальним пошуком, а для уточнення напіввизначеної релаксації – виконувати послідовне звуження допустимої області шляхом варіації параметра а. Практична значимість. Розглянута методика пошуку розв’язку може бути використана для знаходження розв’язку прикладних задач, які можуть бути сформульовані у вигляді загальних квадратичних задач. Порівняльні експерименти підтверджують ефективність даного підходу для розв’язання таких задач.

EN: Purpose. The purpose of this article is to develop new and effective methods for solving quadratic problems. Such tasks arise in economy, finance, management, technological processes, informatics and other fields. A distinctive feature of these problems is their large dimension and complexity for the numerical attack. In this paper a modification of semidefinite optimization problems is considered, which makes it possible to find more accurate bounds of quadratic problems solutions. Methodology. In this paper quadratic problems are transformed into general semidefinite optimization problem, and then a local search method is applied to solve it. The nonnegativity constraint of variables are written in the form of quadratic constraints xi (xi - a) ≤ 0. The number of such constraints is n. The form of such constraints in the formulation of semidefinite optimization problem is matrix with successive shift of non-zero elements. The value of a is chosen such that the condition x ≤ a is satisfied. When we solve semidefinite optimization problems, we use the variation of the parameter a. Findings. Comparative computational experiments were conducted with the problems of different dimensions. Evolutionary search and semidefinite optimization were used. In all cases, the method of semidefinite optimization with local search gave the best solution. As numerical experiments have shown, the value of parameter a affects the accuracy of bounds of the original quadratic problem solution. Parameter increment allows obtaining more accurate bounds of the solution. Originality. In this paper we propose to use semidefinite optimization methods with local search for solving general quadratic problems, and for improvement the semidefinite relaxation we propose to produce a successive restriction of feasible region by varying the parameter a. Practical value. The considered method can be used to find solution of applications that can be formulated as general quadratic programming problems. Comparative experiments confirm the effectiveness of this approach for solving such problems.