Как правило, общий подход к решению задач оптимизации при наличии ограничений состоит в замене исходной задачи с ограничениями на другую более легко реализуемую задачу и которая в последующем используется как основа для некоторых итерационных процессов. В качестве основной особенности первоначально предложенных методов можно отметить следующее: исходная задача с ограничениями заменяется на задачу без ограничений, но с применением метода штрафных функций вблизи или около налагаемых значений для ограничений. При таком подходе задача оптимизации при наличии ограничений решалась через введение некой последовательности параметризованных задач оптимизации без наложения ограничений, которые в пределе (выбранной последовательности) сходились к искомой задаче с ограничениями. В настоящее время такой подход считается относительно малоэффективным и, соответственно, был заменен на методы решения, основанными на формулировке и последующем решении так называемых уравнений Куна-Такера (КТ). В уравнениях КТ вводятся дополнительные предположения о характере ограничений и понятии оптимальности для задачи оптимизации при наличии ограничений. Если поставленная задача является так называемой задачей выпуклого программирования, то есть и являются выпуклыми функциями, то уравнения КТ являются необходимыми и достаточными условиями для общей постановки задачи.
Применительно к уравнению (3-1) (GP) уравнения Куна-Таккера записываются в виде
(3-26) |
Первые уравнения представляют собой описание процесса исчезновения градиента между целевой функцией и активными ограничениями в точке решения. Поскольку градиенты подлежат выходу на нулевые значения, то множители Лагранжа () будут необходимы для того, что бы уравновесить отклонения по величине данной целевой функции и градиентов ограничений. Поскольку только активные ограничения вовлечены в данную процедуру оюнуления, то ограничения не активны и не должны подвергаться данной процедуре и поэтому соответствующие множители Лагранжа будут равны нулю. Это обстоятельство неявно выражено в двух последних уравнениях 3-26.
Подобное решение уравнений Куна-Таккера служит основой для большинства алгоритмов нелинейного программирования. В этих алгоритмах часто используется прямое вычисление множителей Лагранжа. Квазиньютоновские методы обеспечивают сверхлинейную сходимость путем накопления информации второго порядка относительно уравнений Куна-Таккера, использующих процедуры квазиньютоновской корректировки. В общем случае эти методы можно отнести к задачам Последовательного квадратичного программирования (SQP), поскольку проблема QP решается на каждой главной итерации (иногда их еще называют методами Итерационного квадратичного программирования, Рекурсивного квадратичного программирования или Переменной метрики при наличии ограничений).