А.Г.Трифонов. Оптимизация при наличии ограничений Как правило, общий подход к решению задач оптимизации при наличии ограничений состоит в замене исходной задачи с ограничениями на другую более легко реализуемую задачу и которая в последующем используется как основа для некоторых итерационных процессов. В качестве основной особенности первоначально предложенных методов можно отметить следующее: исходная задача с ограничениями заменяется на задачу без ограничений, но с применением метода штрафных функций вблизи или около налагаемых значений для ограничений. При таком подходе задача оптимизации при наличии ограничений решалась через введение некой последовательности параметризованных задач оптимизации без наложения ограничений, которые в пределе (выбранной последовательности) сходились к искомой задаче с ограничениями. В настоящее время такой подход считается относительно малоэффективным и, соответственно, был заменен на методы решения, основанными на формулировке и последующем решении так называемых уравнений Куна-Такера (КТ). В уравнениях КТ вводятся дополнительные предположения о характере ограничений и понятии оптимальности для задачи оптимизации при наличии ограничений. Если поставленная задача является так называемой задачей выпуклого программирования, то есть и являются выпуклыми функциями, то уравнения КТ являются необходимыми и достаточными условиями для общей постановки задачи. Применительно к уравнению (3-1) (GP) уравнения Куна-Таккера записываются в виде (3-26) Первые уравнения представляют собой описание процесса исчезновения градиента между целевой функцией и активными ограничениями в точке решения. Поскольку градиенты подлежат выходу на нулевые значения, то множители Лагранжа () будут необходимы для того, что бы уравновесить отклонения по величине данной целевой функции и градиентов ограничений. Поскольку только активные ограничения вовлечены в данную процедуру оюнуления, то ограничения не активны и не должны подвергаться данной процедуре и поэтому соответствующие множители Лагранжа будут равны нулю. Это обстоятельство неявно выражено в двух последних уравнениях 3-26. Подобное решение уравнений Куна-Таккера служит основой для большинства алгоритмов нелинейного программирования. В этих алгоритмах часто используется прямое вычисление множителей Лагранжа. Квазиньютоновские методы обеспечивают сверхлинейную сходимость путем накопления информации второго порядка относительно уравнений Куна-Таккера, использующих процедуры квазиньютоновской корректировки. В общем случае эти методы можно отнести к задачам Последовательного квадратичного программирования (SQP), поскольку проблема QP решается на каждой главной итерации (иногда их еще называют методами Итерационного квадратичного программирования, Рекурсивного квадратичного программирования или Переменной метрики при наличии ограничений). Последовательное квадратичное программирование SQP SQP метод является одним из самых современных методов в области нелинейного программирования. Шитковский [38], к примеру, успешно реализовал и провел тестовые расчеты по данной версии оптимизации и получил всестороннее превосходство, по сравнению с другими тестовыми методами, в части эффективности, точности и процента успешного решения задачи для большого числа тестовых задач. Основанный на работах Бигса [1], Хана [24] и Пауэлла ([34], [35]) данный метод позволяет достаточно точно имитировать метод Ньютона для оптимизации при наличии ограничений, как это сделано для оптимизации без наличия ограничений. На каждой основной итерации осуществляется аппроксимация Гессиана для функций Лагнранжа при помощи квазиньютоновского модифицированного метода. Такой подход далее будет востребован для постановки подзадачи QP, решение которой далее уже используется для формирования направления поиска в процедуре линейного поиска. Обзор методов SQP можно найти в работах Флетчера [15], Гиль и др. [21], Пауэлла [37] и Шитковского [25]. Тем не менее, далее приводится описание обобщенного метода. Согласно описанию задачу метода GP (уравнение 3-1) основная идея постановки подзадачи QP заключается в квадратичной аппроксимации функции Лагранжа. (3-27) Последнее представляет собой упрощение уравнения 3-1 при предположении, что связанные ограничения могут быть представлены через ограничения в виде неравенств. Посредством линеаризации нелинейных ограничений можно получить подзадачу QP. Подзадача квадратичного программирования (QP) (3-27) Данная подзадача может быть решена посредством применения алгоритма QP (см., например, раздел Решение квадратичного программирования). Такое решение основано на формировании новой итерации следующего вида Параметр при длине шага определяется из соответствующей процедуры линейного поиска, которая обеспечивает приемлемое уменьшение получаемой функции выгоды (см. раздел Корректировка матрицы Гессе). Матрица является положительно определенной аппроксимацией матрицей Гессе для Лагранжевой функции. (уравнение 3-27). может быть корректироваться посредством любого из квазиньютоновских методов, хотя метод BFGS (смотри раздел Корректировка матрицы Гессе), скорее всего, является наиболее популярным. В отличие от решения методом SQP для задач без ограничений, нелинейные задачи при наличии ограничений решаются за некоторое число итераций. Одной из причин такого факта является то, что, вследствие наличия пределов на обозримые области, оптимизатор может принимать осознанные решения относительно направлений поиска и размера шага. Рассмотрим функцию Розенброка (уравнение 3-2) при наличии дополнительных нелинейных ограничений в виде неравенств, g(x), (3-29) При применении метода SQP эта задача решается за 96 итераций по сравнению с 140 итерациями для задач без ограничений. На рисунке 3-6 представлен путь к точке решения начиная со стартовой точки . Рис. 3-6. Применение метода SQP для функции Розенброка (уравнение 3-2) с линеаризованными нелинейными ограничениями Реализация метода SQP Реализация метода SQP состоит из трех основных стадий, которые далее кратко обсуждаются в следующих подразделах Корректировка матрицы Гессе для Лагранжевой функции. Решение задачи квадратичного программирования. Вычисление линейного поиска и функции выгоды Корректировка матрицы Гессе На каждой главной итерации положительно определенная квазиньютоновская аппроксимация для функции Лагранжа , H, рассчитывается с помощью метода BFGS, где представляют собой оценку множителей Лагранжа. , где (3-30) Пауэл вообще [35] рекомендует поддерживать значения матрицы Гессе положительно определенными, даже не смотря на то, что в точке эти решения могут и не иметь положительные решения. Положительные значения матрицы Гессе поддерживаются в том случае, если величина будет больше нуля для каждой корректировки и, что H инициализируется как положительно определенная матрица. Когда величина не является положительной, то параметр модифицируется поэлементно, шаг за шагом, так что бы выполнялось условие . Обобщенная цель такой модификации заключается в том, что бы несколько изменить элементы , которые составляют основной вклад в положительно определенную корректировку, как можно меньше. Таким образом, на начальной стадии принятой модификации, отрицательный наибольший элемент их набора последовательно уменьшается на половину. Такая процедура продолжается до тех пор, пока больше или равна 1e-5. Если после такой процедуры все равно остается положительной, то производится модификация y путем добавления некого вектора v, умноженного на некую скалярную постоянную w, а именно, (3-31) где если
Комментариев нет:
Отправить комментарий