to English

Квадратичное программирование

Произвольная матрица квадратичной формы

Рассматривается задача о поиске наибольшего или наименьшего значения целевой функции F = (X,AX) + (L,X) + C в случае произвольной матрицы "A" квадратичной формы. Область изменения аргументов "X" задается системой линейных ограничений-равенств и линейных ограничений-неравенств. Упрощающих требований о положительной определенности квадратичной формы при минимизации функции или отрицательной определенности квадратичной формы при максимизации функции здесь не накладывается. Квадратичной функцией можно аппроксимировать произвольную нелинейную функцию (решая проблему математического программирования), при этом, знакопостоянства квадратичной формы, как правило, не ожидается. В этом случае необходимо решать задачу оптимизации с произвольной матрицей квадратичной формы.

Точное решение

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

Бесплатная апробация метода

Всем желающим предлагается бесплатная возможность проверить описанную выше идею на конкретных примерах. Для чистоты эксперимента примеры Вы создаете сами и предлагаете автору решить их. Получив решение, можете всесторонне его проанализировать, чтобы убедиться в работоспособности предложенного алгоритма или забраковать его.
Программная апробация. Для того, чтобы избежать недоразумений в описании примера, составлена программа. Ее можно скачать здесь. Этот файл является самораскрывающимся архивом, содержащим четыре файла: qpu.exe, qpu.aux, qpu.t0 и qpu.t1. Все четыре файла должны располагаться в одной папке, исполнимый файл - qpu.exe. Программа qpu.exe позволяет задать числовые параметры задачи квадратичного программирования и запишет их в файл специального формата. Этот файл можно отправить автору bgs@krm.net.ua, который обязуется решить любую присланную задачу или заявить о неспособности получить результат с помощью заявленного алгоритма. В любом случае Вы получите ответ на свою электронную почту.
Задания для апробации online. Числовые параметры задачи квадратичного программирования небольшой размерности, в стандартном виде можно ввести и непосредственно: Структура задачи -> Числовые данные. В этом случае ответ появится на этом сайте через несколько дней на странице Решения задач квадратичного программирования (автор посещает сайт 1-2 раза в неделю).

Примеры

Пример 1   Пример 2   Пример 3

<

Автор

Буланов Геннадий Станиславович, 1948 г.р., кандидат физ.-мат. наук, доцент кафедры высшей математики Донбасской государственной машиностроительной академии, г. Краматорск, Донецкой области, Украина.

bgs@krm.net.ua

Из методических разработок Буланова Г.С. для учебных целей

Автоматизированный задачник по функциональному анализу