Главная > Интеллектуальные системы > Зрение роботов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

П.5. Множители Лагранжа

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

П.5.1. Случай одного ограничения

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

Рассмотрим кривую, заданную уравнением Пусть — параметр, изменяющийся при движении вдоль кривой. Тогда

и наклон кривой определяется выражением

Подставляя его в полученное ранее уравнение для экстремума вместо получаем

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

Теперь рассмотрим экстремум функции

Дифференцируя по и X, получим

Если мы исключим X, то вновь получим

Таким образом, экстремум функции при ограничении можно найти, отыскивая экстремум функции .

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

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

в то время как линии уровня функции перпендикулярны к градиенту:

Эти два градиента должны быть параллельны.

Рассмотрим теперь экстремум функции . Дифференцирование дает

что и является условием параллельности двух градиентов. Множитель это просто отношение длин двух градиентов.

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

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

П.5.2. Случай нескольких ограничений

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

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

В качестве примера рассмотрим задачу определения размеров прямоугольного короба наибольшего объема при условии, что одна из его граней имеет единичную площадь, а сумма ширины, высоты и глубины короба равна 4. Обозначим размеры короба через и с. Нам необходимо найти максимум функции . Дифференцирование по и с дает Исключая из этих уравнений X и получаем Из первого ограничения следует, что Второе ограничение приводит к

П.5.3. Общий случай

Пусть — вектор в -мерном пространстве. Множество значений х, удовлетворяющих ограничению образует подпространство. Рассмотрим некоторую кривую, полностью лежащую в этом подпространстве. Пусть — параметр, изменяющийся при движении вдоль этой кривой. Направление кривой в точке характеризуется касательным вектором

Скорость изменения функции с изменением параметра дается формулой

— градиент

Поскольку кривая остается в подпространстве, где имеем

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

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

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

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

для любого касательного вектора, удовлетворяющего условиям

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

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

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

так как — линейная комбинация Поскольку при мы можем выбрать кривую, для которой . В этом случае Это противоречит условию экстремума, и потому с должна быть равна нулю. Значит должен быть линейной комбинацией градиентов Мы можем записать это условие в виде

где X — некоторые коэффициенты.

Теперь рассмотрим функцию

Если попытаться найти ее экстремум дифференцированием по X, то получим

Это именно то уравнение, которое, как было показано, удовлетворяется в точке экстремума функции

Подводя итоги сказанному, заключаем, что экстремум функции при ограничениях можно определить путем нахождения экстремума функции

при тех же ограничениях. Здесь х — вектор с компонентами, причем

<< Предыдущий параграф Следующий параграф >>
Оглавление