Можно показать, что. Метод обобщенного Лагранжиана

↑

▷ Содержание

Стр 1 из 3Следующая ⇒

Рассмотрим условия Куна-Такера в несколько другом виде.

Пусть имеем задачу оптимизации с ограничениями в виде равенств:

              z = f(x₁, x₂, …, xn) ® min

при условиях:

              g₁(x₁, x₂, . . . , x_n) = 0,

              g₂(x₁, x₂, . . . , x_n) = 0,

              .   .   .   .   .       

              g_n(x₁, x₂, . . . , x_n) = 0.

Точка условного минимума функции f совпадает с седловой точкой функции Лагранжа:

              ,

при этом седловая точка должна обеспечивать минимум по своим переменным xi и максимум по переменным lj.

Необходимые условия стационарной точки - равенство нулю частных производных первого порядка по всем переменным:

Отметим, что из второго уравнения следует, что только допустимые точки будут удовлетворять необходимым условиям.

Для получения достаточного условия существования минимума необходимо добавить требование положительной определенности гессиана целевой функции.

Рассмотрим общую задачу математического программирования:

                       Z = f(X) ® min,

при условиях:

              gi(X) £ bi, (i = 1, …, m).

Ограничения в виде неравенств могут быть преобразованы в ограничения в виде равенств добавлением к каждому из них ослабляющих переменных

.

Сформируем функцию Лагранжа:

Тогда необходимые условия минимума принимают вид:      

Второе уравнение можно преобразовать, отбросив ослабляющие переменные и переходя к ограничениям-неравенствам. Получим ограничения исходной задачи. Третье уравнение можно умножить на ui/2 и заменить ослабляющие переменные, выразив их из второго уравнения системы.

Есть еще одно условие, которое должно выполняться в точке минимума. Это условие: li > 0, которое является следствием анализа физического смысла коэффициентов функции Лагранжа.

Можно показать, что

,

где  - коэффициент Лагранжа в точке минимума, f* - оптимальное значение функции.

Очевидно, что при возрастании bi допустимая область расширяется, а это значит, что минимальное значение может только уменьшаться, то есть производная должна быть отрицательной. Следовательно, li ³ 0 в точке условного минимума.

Окончательно получаем необходимые условия для условного минимума:

Выражения во второй строке гарантируют, что оптимальная точка будет допустимой.

Третья строка содержит следующую информацию: если ограничение активно (т.е. выражение в скобках равно нулю), то соответствующий коэффициент Лагранжа строго положителен. Положительность коэффициента Лагранжа означает активность соответствующего ограничения, т.е. то, что это ограничение является дефицитным, именно оно останавливает дальнейшее улучшение целевой функции. Если же ограничение не активно (т.е. выражение в скобках не равно нулю), то соответствующий коэффициент Лагранжа должен быть равен нулю, т.е. это ограничение не дефицитно, оно не оказывает влияния на дальнейшее улучшение целевой функции.

Для точки условного максимума коэффициенты Лагранжа меняют знак на противоположный (т.к. оптимальное значение целевой функции в точке условного максимума должно возрастать).

Приведенные условия эквивалентны теореме Куна-Такера и часто называются так же.

Достаточным условием для минимума (максимума) является выпуклость (вогнутость) целевой функции в стационарной точке. Это значит, что гессиан должен быть положительно (отрицательно) определен.

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

В настоящее время нет метода, гарантирующего существование решения любой общей задачи математического программирования.

Все методы условной оптимизации в том или ином виде сводят ее к одной или к последовательности задач безусловной оптимизации.

Идея метода состоит в следующем. 

Если нам были бы известны коэффициенты Лагранжа в точке условного минимума, то можно было бы искать седловую точку функции Лагранжа, выполняя безусловную минимизацию по объектным переменным, зафиксировав (оптимальные) коэффициенты Лагранжа.

Если бы нам были известны объектные переменные в точке условного минимума, то можно было бы искать седловую точку функции Лагранжа, выполняя безусловную максимизацию этой функции по коэффициентам Лагранжа, зафиксировав (оптимальные) объектные переменные.

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

Методы прямого поиска для решения задач условной оптимизации

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

Неудачной оказывается и модификация метода Нелдера-Мида ввиду того, что вблизи границы многогранник "уплощается" и стягивается, что и останавливает метод (или резко замедляет его после того, как данное ограничение перестало быть активным). Прямая модификация других методов прямого поиска также не была особенно успешной, за исключением, быть может, случайного поиска. Однако алгоритмы случайного поиска мы не будем рассматривать в этом разделе.

Познавательные статьи:



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману