Метод последовательного квадратичного программирования
Цель работы состоит в практическом освоении метода последовательного квадратичного программирования и особенностей его применения в ходе поисковой оптимизации.
2. ПРАКТИЧЕСКОЕ ЗАДАНИЕ И МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ЕГО ВЫПОЛНЕНИЮ
В соответствии с разработанным в ходе выполнения практических заданий № 1, 2 математическим обеспечением оптимального проектирования исследовать возможность и целесообразность применения метода последовательного квадратичного программирования в ходе оптимизационных процедур.
Методические указания по выполнению практического задания
Если метод проекции градиента можно рассматривать как адаптацию стандартных градиентных методов (т. е. методов первого порядка) к ситуации с ограничениями, то последовательное квадратичное программирование представляет собой попытку адаптировать к такой же ситуации методы второго порядка (ньютоноподобные методы). Вместо того, чтобы явно учитывать ограничения, строится процедура численного решения уравнений Куна — Таккера [3].
Общий подход к решению задач оптимизации при наличии ограничений состоит в замене исходной задачи с ограничениями на другую более легко реализуемую задачу и которая в последующем используется как основа для некоторых итерационных процессов [2].
В качестве основной особенности первоначально предложенных методов можно отметить следующее: исходная задача с ограничениями заменяется на задачу без ограничений, но с применением метода штрафных функций вблизи или около налагаемых значений для ограничений.
При таком подходе задача оптимизации при наличии ограничений решалась через введение некой последовательности параметризованных задач оптимизации без наложения ограничений, которые в пределе (выбранной последовательности) сходились к искомой задаче с ограничениями.
В настоящее время такой подход считается относительно малоэффективным и, соответственно, был заменен на методы решения, основанными на формулировке и последующем решении так называемых уравнений Куна-Такера (КТ). В уравнениях КТ вводятся дополнительные предположения о характере ограничений и понятии оптимальности для задачи оптимизации при наличии ограничений.
Если поставленная задача является так называемой задачей выпуклого программирования, то есть f(x) и Gi(x), i = 1,…,m являются выпуклыми функциями, то уравнения КТ являются необходимыми и достаточными условиями для общей постановки задачи.
Применительно к уравнению (GP) уравнения Куна-Таккера записываются в виде
Первые уравнения представляют собой описание процесса исчезновения градиента между целевой функцией и активными ограничениями в точке решения. Поскольку градиенты подлежат выходу на нулевые значения, то множители Лагранжа (λ, i = 1,…,m) будут необходимы для того, что бы уравновесить отклонения по величине данной целевой функции и градиентов ограничений. Поскольку только активные ограничения вовлечены в данную процедуру обнуления, то ограничения не активны и не должны подвергаться данной процедуре и поэтому соответствующие множители Лагранжа будут равны нулю. Это обстоятельство неявно выражено в двух последних уравнениях.
Подобное решение уравнений Куна-Таккера служит основой для большинства алгоритмов нелинейного программирования. В этих алгоритмах часто используется прямое вычисление множителей Лагранжа. Квазиньютоновские методы обеспечивают сверхлинейную сходимость путем накопления информации второго порядка относительно уравнений Куна-Таккера, использующих процедуры квазиньютоновской корректировки. В общем случае эти методы можно отнести к задачам последовательного квадратичного программирования (SQP), поскольку проблема QP решается на каждой главной итерации (иногда их еще называют методами итерационного квадратичного программирования, рекурсивного квадратичного программирования или переменной метрики при наличии ограничений).
SQP метод является одним из самых современных методов в области нелинейного программирования. Шитковский, к примеру, успешно реализовал и провел тестовые расчеты по данной версии оптимизации и получил всестороннее превосходство, по сравнению с другими тестовыми методами, в части эффективности, точности и процента успешного решения задачи для большого числа тестовых задач [3].
Данный метод позволяет достаточно точно имитировать метод Ньютона для оптимизации при наличии ограничений, как это сделано для оптимизации без наличия ограничений. На каждой основной итерации осуществляется аппроксимация Гессиана для функций Лагнранжа при помощи квазиньютоновского модифицированного метода. Такой подход далее будет востребован для постановки подзадачи QP, решение которой далее уже используется для формирования направления поиска в процедуре линейного поиска. Далее приводится описание обобщенного метода.
Согласно описанию задачу метода GP (4.9) основная идея постановки подзадачи QP заключается в квадратичной аппроксимации функции Лагранжа [2].
Последнее представляет собой упрощение (11) при предположении, что связанные ограничения могут быть представлены через ограничения в виде неравенств. Посредством линеаризации нелинейных ограничений можно получить подзадачу QP.
Подзадача квадратичного программирования (QP)
Данная подзадача может быть решена посредством применения алгоритма QP. Такое решение основано на формировании новой итерации следующего вида:
Параметр при длине шага αk определяется из соответствующей процедуры линейного поиска, которая обеспечивает приемлемое уменьшение получаемой функции выгоды. Матрица Hk является положительно определенной аппроксимацией матрицей Гессе для Лагранжевой функции. (12). Hk может корректироваться посредством любого из квазиньютоновских методов, хотя метод BFGS (Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно), является наиболее популярным. Это итерационный метод численной оптимизации, предназначенный для нахождения локального максимума/минимума нелинейного функционала без ограничений [3]. BFGS — один из наиболее широко применяемых квазиньютоновских методов. В квазиньютоновских методах не вычисляется напрямую гессиан функции. Вместо этого гессиан оценивается приближенно, исходя из сделанных до этого шагов.
В отличие от решения методом SQP для задач без ограничений, нелинейные задачи при наличии ограничений решаются за некоторое число итераций. Одной из причин такого факта является то, что, вследствие наличия ограничений, проектировщик должен принимать относительно направлений поиска и размера шага.
Реализация метода SQP состоит из трех основных стадий:
— корректировка матрицы Гессе для Лагранжевой функции;
— решение задачи квадратичного программирования;
— вычисление линейного поиска и функции выгоды;
— корректировка матрицы Гессе.
На каждой главной итерации положительно определенная квазиньютоновская аппроксимация для функции Лагранжа, H, рассчитывается с помощью метода BFGS, где представляют собой оценку множителей Лагранжа.
Пауэл рекомендует поддерживать значения матрицы Гессе положительно определенными, даже не смотря на то, что в точке эти решения могут и не иметь положительных решений [2]. Положительные значения матрицы Гессе поддерживаются в том случае, если величина будет больше нуля для каждой корректировки и, что H инициализируется как положительно определенная матрица. Когда величина не является положительной, то параметр qk модифицируется поэлементно, шаг за шагом, так чтобы выполнялось условие >0. Обобщенная цель такой модификации заключается в том, чтобы изменять элементы qk, которые составляют основной вклад в положительно определенную корректировку, как можно меньше. Таким образом, на начальной стадии принятой модификации, отрицательный наибольший элемент из набора qk×sk последовательно уменьшается на половину. Такая процедура продолжается до тех пор, пока больше или равна 10 -5 .
На каждой основной итерации метода SQP решается задача квадратичного программирования в следующей форме, где Аi относится к i-й стоке матрицы A.
В алгоритме инициализации для успешного начала работы требуется некая допустимая стартовая точка.
Решение подзадачи QP приводит к формированию вектора dk, который, в свою очередь, используется при формировании новой итерации типа
Для того, чтобы получить достаточное уменьшение функции выгоды (целевой функции) оценивается параметр длины шага αk. Реализованная в данном алгоритме функция выгоды была ранее использована Наном и Пауэлом и имеет следующий вид [2].
Пауэл рекомендует введение следующего штрафного параметра
4.6. Квадратичное программирование
Задачи квадратичного программирования имеют следующие особенности: целевая функция представляет собой сумму вида функции, входящие в ограничения, линейны относительно хj, т.е. обычно присутствует требование неотрицательности переменных.
Структура задач квадратичного программирования позволяет широко использовать теорию Куна — Таккера для поиска оптимальных решений. Различные интерпретации необходимых условий существования экстремума (4) (п. 4.4) привели к разработке целого ряда алгоритмов, многие из которых преследуют цель свести решение исходной квадратичной задачи к вариантам линейного программирования. Что касается достаточных условий экстремума, то в данном случае они выражены в требовании выпуклости (вогнутости) функции . Можно показать, что рассматриваемая квадратичная форма обладает свойством выпуклости (вверх), если она является неположительно (или отрицательно) определенной в U, т.е. для всех хj, xk, удовлетворяющих принятым ограничениям.
Учитывая сказанное, обратимся к задаче: найти
Положив , говорить в дальнейшем только о глобальном экстремуме z. .
Рассмотрим необходимые условия существования X*, z*. Здесь
Обозначим для удобства через pj — производную , а через производную qi — . Тогда искомые условия можно трактовать так: значения определяются теми решениями системы
которые удовлетворяют требованиям
Переход к системе (6) позволяет в большинстве случаев упростить процедуру отыскания за счёт использования симплекс-алгоритма. Возвращаясь к (6), заметим, что рассматриваемая система содержит т+п линейных уравнений с 2(n+m) неизвестными . Предполагая уравнения (6) независимыми (поскольку независимы условия, из которых они получены), можно сказать, что п+т из названных 2(п+т) переменных являются свободными.
Если некоторое решение (6) удовлетворяет требованиям
то среди его компонент должно быть как минимум п+т равных нулю; таким образом, оно может иметь вид «ровно п+т компонент отличны от нуля, ровно п+т компонент равны нулю» или «менее п+т компонент отличны от нуля, более п+т компонент равны нулю».
Очевидно, подобные решения являются базисными, и для отыскания X* должен существовать метод, аналогичный симплекс-методу, оперирующему с базисными решениями. Возникает вопрос: нельзя ли сразу, выбрать произвольно п+т свободных переменных среди положить их равными нулю, а затем определить через них остальные переменные в соответствии, с уравнениями (6)? Ответ, здесь может быть только отрицательным, потому что произвольный выбор решения может привести к нарушению условий . Приходится обращаться к специальным методам определения . Одним из них является так называемый метод Вольфа, предусматривающий исследование задач линейного программирования с целью получить решения задачи квадратичного программирования.