Давайте сегодня поговорим об оптимизации с ограничениями. Для начала пусть переменных всего две. Надо найти максимум (или минимум) функции, но так, чтобы выполнялось ограничение вида g(x,y) = 0. Максимум подразумевается локальный. Без ограничения --- это поиск вершин холмов; с ограничением --- поиск самых высоких положений на тропинке, проложенной по холмистой местности.
Вообще-то, если переменных две, то из ограничения можно выразить одну через другую и переменная окажется всего одна. Но даже в простых случаях выражение будет очень громоздким, да и существует метод получше.
Как мы уже обсуждали, вектор-градиент указывает направление скорейшего роста функции в данной точке. В направлениях под острым углом к градиенту функция тоже растет (хотя бы маленький шажок, но с увеличением высоты над уровнем моря --- можно сделать), а под тупым --- убывает. В точке условного максимума рост возможен, но только под прямым углом к тропинке. В поиске максимума мы будем идти вверх по тропинке, пока "вверх" не будет строго под прямым углом --- тогда уже надо с тропинки сходить, так как по ней далее будет "вниз".
Разумеется, мы обсуждаем необходимые условия! В точке максимума точно так, но так может быть и не в точке максимума.
Теперь рассмотрим функцию g(x,y). Она должна быть равна нулю, то есть ограничение --- наша тропинка --- это линия уровня функции. Ее градиент перпендикулярен к линии уровня, потому что на ней функция постоянна --- не растет и не убывает. Таким образом, оба градиента лежат на одной прямой в точке максимума:
Можно выразиться иначе, записав функцию Лагранжа L(x,y,λ) = f(x,y) + λg(x,y) и решая задачу о поиске ее максимума без ограничений.
Формально надо добавить еще множитель к f(x,y) и тогда он либо равен единице (нормальный случай), либо нулю --- случаи вырожденные, в которых решение от оптимизируемого критерия не зависит.
Можно трактовать множитель λ как ставку величины штрафа за нарушения ограничения. То есть, вместо задачи "найдите самое высокое место на тропинке" мы говорим "найдите самое высокое место; результат будет уменьшен пропорционально расстоянию до тропинки". При правильно подобранной ставке ограничение нарушено не будет. Помимо решения задачи, мы узнаем еще "цену ограничения" --- этот самый множитель λ. Если он близок к нулю, то ограничение маловажно, оно и так не нарушится или нарушится не сильно.
Можно уточнить этот принцип. Пусть ограничение имеет вид G(x,y)-b=0. Это естественно, если нельзя превзойти запас ресурса. То, что он весь будет издержан --- ясно, но больше никак нельзя. Величина b --- это и есть запас. Решение и оптимальное значение зависят от b. Найдем производную f'=df/db от оптимального значения по b --- она и покажет чувствительность оптимума к этой величине, так как выигрыш от изменения запаса на db равен, с точностью до бесконечно малых, f'db.
Получается, что реакция прибыли на вариацию запаса равна множителю Лагранжа с обратным знаком. Если λ<0, то рост запаса повышает прибыль, и мы точно знаем, насколько. В бесконечно-малом, конечно, но дальнейший анализ --- уже дело техники.
Для многих переменных все точно так же. Все ограничения добавляются к функции, каждое со своим множителем.
Рассмотрим два примера. Пусть местность описывается уравнением
z=1-x^2-y^2,
а ограничение имеет вид y/x - b = 0. Решая задачу, получаем λ=0. То есть, ограничение роли не играет. Максимум все равно в нуле, в каком направлении не проводи через него тропинки.
Второй пример --- классика. Надо отгородить забором данного периметра P прямоугольный участок максимальной площади. Просто огородить, со всех сторон, и у реки --- с трех сторон. И между рекой и дорогой --- с двух сторон. Площадь равна xy, а половина периметра равна x+y.
Запишем функцию Лагранжа: xy+λ(x+y-P/2) и найдем ее производные по x и y: y+λ=0, x+λ=0. Отсюда следует, что x=y, а λ<0. Первое уравнение решает задачу --- искомый участок квадратный, а второе дает ценную информацию: увеличение периметра увеличит и площадь.
Для реки все похоже, только формула для периметра другая и ответ, соответственно: x=L/4, y=L/2: сторона вдоль реки вдвое длиннее.
Третья задача немного коварна. Периметр от y не зависит вообще! Формально получается x=0, но это не максимум и даже не минимум. Максимума вообще нет, потому что два куска забора между рекой и дорогой могут сколь угодно далеко друг от друга располагаться и отгораживать, тем самым, любую площадь.
Поучительно рассмотреть аналогичную задачу о цилиндрической бочке максимального объема при заданной площади поверхности. Бочка с дном и крышкой, бочка без крышки, бочка без дна. Последняя задача не имеет решения: можно делать бочку-блюдце, очень большого радиуса и малой высоты: площадь будет какая задана, а объем --- сколь угодно велик.
Последний пример. В заметке про энтропийные распределения мы искали максимум функции с ограничением. Метод Лагранжа показывает, что все переменные равны, причем всегда, если функция есть сумма одинаковых слагаемых для всех переменных.
Можно применить метод и для бесконечного числа переменных, принцип тот же. Там решение "все переменные равны" уже не подходит, ведь сумма бесконечного числа равных величин никак не может равняться единице. Надо добавить еще ограничение, задав матожидание --- и получить геометрическое распределение. Множители дают дополнительную информацию, хотя и не очень ценную в данном случае.
Давайте теперь рассмотрим ограничения-неравенства g(x,y)≥0. Их можно свести с неравенствам вида x≥0, если ввести дополнительные переменные h --- остатки ресурса --- и записать ограничения-равенства g(x,y)-h=0. Переменная h входит только в ограничение и для нее условие на обнуление производной приводит к "условию дополняющей нежесткости" λh=0. Это означает, что либо h=0, то есть ресурс будет исчерпан весь, ограничение насыщенно (обращается в равенство); либо λ=0, то есть условие не существенно, ресурс в избытке, он не будет весь издержан, поэтому небольшие вариации запаса (самого ограничения) не повлияют на решение задачи.
Здесь множители Лагранжа дают очень ценную информацию! По существу, они различают критичные ограничения от менее существенных. Это важно еще и для устойчивости, ведь нехватка критического ресурса испортит сразу все. Впрочем, об устойчивости поговорим в другой раз...