ДВОЙСТВЕННЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ СЕПАРАБЕЛЬНОГО КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ С ОДНИМ ОГРАНИЧЕНИЕМ И ГРАНИЦАМИ НА ПЕРЕМЕННЫЕ

  • P. I. Stecyuk
  • A. V. Fesyuk
Ключові слова: задача квадратичного программирования, сепарабельная квадратичная функция, двусторонние ограничения на переменные, частичная функция Лагранжа, двойственная задача, метод дихотомии, сдвиг по рекорду вогнутой функции, вычислительный эксперимент

Анотація

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

Переглядів анотації: 39
Завантажень PDF: 19