Условный экстремум (метод Лагранжа) 🪢

В прошлом уроке ты искал экстремумы функции нескольких переменных так, будто в твоём распоряжении всё пространство целиком: возьми градиент, приравняй к нулю, найди критические точки, проверь вторыми производными, кто из них максимум, а кто минимум. Это честная и правильная процедура — но она работает только в одном частном случае: когда переменные $x$ и $y$ вольны принимать любые значения, никак друг с другом не связанные. А в реальных задачах так почти никогда не бывает. Ты хочешь построить забор максимальной площади, но у тебя всего сто метров сетки. Ты хочешь минимизировать себестоимость производства, но объём выпуска обязан быть ровно тысяча единиц. Ты хочешь максимизировать точность модели, но сумма весов обязана оставаться ограниченной, иначе модель переобучится. Во всех этих случаях экстремум ищется не во всём пространстве, а строго на какой-то поверхности, кривой или линии — на множестве, заданном дополнительным условием, ограничением.

Именно эту задачу — найти экстремум функции $f(x,y)$ при условии, что переменные $x$ и $y$ обязаны удовлетворять некоторому уравнению-ограничению $g(x,y)=0$, — сегодня и разберём. Задача называется задачей на условный экстремум, а главный инструмент её решения — метод множителей Лагранжа — один из самых изящных и одновременно самых практически важных приёмов во всей математике оптимизации. Идея метода удивительно простая на вид: вместо того чтобы напрямую бороться с ограничением, мы построим специальную вспомогательную функцию — функцию Лагранжа, — экстремумы которой (уже без всяких ограничений) в точности совпадают с решениями исходной задачи.

Скажем сразу и без обиняков, почему этот урок для тебя, будущего специалиста по машинному обучению, без преувеличения один из ключевых во всём курсе. Метод множителей Лагранжа — это буквально математический фундамент, на котором выведен метод опорных векторов (Support Vector Machine, SVM) — один из самых элегантных и мощных алгоритмов классификации в машинном обучении. Задача SVM формулируется ровно в терминах, которые мы сегодня разберём: найти такую разделяющую гиперплоскость между двумя классами объектов, чтобы зазор (margin) между ней и ближайшими точками каждого класса был максимален, при условии что каждая точка обучающей выборки классифицируется правильно. «Максимизировать при ограничении» — это ровно условный экстремум. И решается эта задача переходом к так называемой двойственной задаче Лагранжа, где вместо весов модели оптимизируются именно множители Лагранжа $\lambda_i$ — по одному на каждую обучающую точку. Более того, множители Лагранжа помогают понять устройство регуляризации: штраф $\lambda\|w\|^2$, который ты видел в Ridge-регрессии или L2-регуляризации нейросетей, исторически и математически связан ровно с той же самой идеей — ограничением на норму весов, превращённым через множитель Лагранжа в дополнительное слагаемое функции потерь.

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

История: откуда это взялось?

Метод множителей носит имя итало-французского математика Жозефа Луи Лагранжа (1736–1813), одного из величайших математиков XVIII века, чьё имя ты уже встречал в связи с теоремой о среднем значении. Лагранж пришёл к идее условного экстремума не из чистой абстракции, а из вполне земной задачи — механики связанных систем. Представь маятник: груз на нити, закреплённой в одной точке. Груз, конечно, мог бы в принципе занять любую точку трёхмерного пространства — но нить фиксированной длины навязывает жёсткое ограничение: груз может находиться только на сфере определённого радиуса вокруг точки подвеса. Задача найти положение равновесия такой системы (точку минимума потенциальной энергии) — это классическая задача на условный экстремум: минимизировать энергию при ограничении на длину нити.

В своём монументальном труде «Аналитическая механика» (Mécanique analytique), опубликованном в 1788 году, Лагранж предложил универсальный приём для задач такого рода: вместо того чтобы вручную параметризовать движение с учётом всех геометрических связей (что для сложных механических систем — грузов, соединённых нитями, стержнями, шарнирами — превращалось в кошмарную вычислительную задачу), он ввёл дополнительные переменные — множители — по одной на каждое ограничение системы, и показал, что если правильно составить вспомогательную функцию из исходной энергии системы и этих множителей, помноженных на уравнения связей, то условия равновесия связанной системы автоматически превращаются в условия безусловного экстремума этой вспомогательной функции. Механическая связь буквально «растворяется» в математике, оставляя после себя только дополнительное слагаемое и дополнительную неизвестную.

Что особенно красиво в методе Лагранжа — придуманный для задач механики XVIII века (равновесие грузов, движение планет с учётом связей), он оказался универсальным математическим инструментом, применимым к абсолютно любой задаче оптимизации при ограничениях, вне зависимости от физического содержания задачи. В XX веке этот же принцип лёг в основу теории двойственности в линейном и выпуклом программировании (работы Куна и Таккера в середине века обобщили метод Лагранжа на ограничения-неравенства, а не только равенства), а в конце XX и начале XXI века — в основу вывода SVM и многих других алгоритмов машинного обучения. Задача, которую двести с лишним лет назад решали для маятников и планет, сегодня решается внутри библиотек scikit-learn и libsvm миллионы раз в день по всему миру.

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

Что вообще значит «условный экстремум»

Давай разберёмся с самой постановкой задачи, прежде чем лезть в формулы. Обычная (безусловная) задача оптимизации звучит так: найти точки $(x,y)$, в которых функция $f(x,y)$ достигает локального максимума или минимума, причём $(x,y)$ может быть абсолютно любой точкой плоскости. Условная задача добавляет жёсткое требование: точка $(x,y)$ обязана лежать на некотором множестве, заданном уравнением $g(x,y)=0$. Формально задача записывается так:

Функцию $f$ обычно называют целевой функцией, а уравнение $g(x,y)=0$ — ограничением (или связью, constraint). Геометрически множество точек, удовлетворяющих $g(x,y)=0$, — это, как правило, некоторая кривая на плоскости: прямая (если $g$ линейна), окружность или эллипс (если $g$ квадратична), или произвольная более сложная кривая. Задача условного экстремума звучит так: среди всех точек этой конкретной кривой найти ту, где $f$ принимает наибольшее (или наименьшее) значение.

Представь, что ты идёшь по горной тропе, вьющейся вдоль склона горы. Тропа — это твоё ограничение $g(x,y)=0$, жёстко заданный путь, с которого ты не можешь сойти ни на шаг в сторону. Высота местности в каждой точке — это функция $f(x,y)$. Вопрос условного экстремума звучит так: в какой точке именно этой тропы (а не горы вообще) высота максимальна? Обрати внимание — эта точка почти наверняка не совпадает с вершиной горы: вершина горы вообще может находиться далеко в стороне от тропы, там, где ты никогда не окажешься, потому что твоё передвижение ограничено тропой.

Геометрическая интуиция: почему в точке условного экстремума линия уровня касается кривой ограничения

Теперь — центральная идея всего метода, и её стоит прочувствовать по-настоящему, а не просто заучить формулу. Вспомни из прошлого урока про градиент: линии уровня функции $f$ — это кривые $f(x,y)=c$ для разных констант $c$, и градиент $\nabla f$ в каждой точке перпендикулярен линии уровня, проходящей через эту точку.

Представь картину: на плоскости нарисована кривая ограничения $g(x,y)=0$ (наша «тропа»), и поверх неё — целое семейство линий уровня функции $f$, как контурные линии на топографической карте. Двигайся мысленно вдоль тропы и следи, через какие линии уровня ты проходишь. Пока тропа пересекает линии уровня под углом (не касаясь их, а именно пересекая), двигаясь вдоль тропы в одну сторону, ты переходишь на линии уровня со всё большим значением $f$, а в другую сторону — со всё меньшим. Это значит, что в точке пересечения экстремума ещё нет: можно улучшить результат, просто сдвинувшись чуть дальше по тропе в нужную сторону.

А что происходит в точке экстремума? Ровно то же самое, что происходит на вершине холма или на дне ямы: движение в любую сторону вдоль тропы перестаёт улучшать значение функции — оно либо не меняется в первом приближении, либо ухудшается в обе стороны. Геометрически это означает, что в точке условного экстремума тропа не пересекает линию уровня, а касается её — идёт вдоль неё в первом приближении, как касательная прямая. А если кривая ограничения касается линии уровня, значит, у них в этой точке общая касательная прямая — а значит, и общая нормаль (перпендикуляр). Но нормаль к линии уровня $f=c$ — это, как мы уже знаем, ровно градиент $\nabla f$. И точно так же нормаль к кривой ограничения $g=0$ — это градиент $\nabla g$ (по той же самой логике: $g$ постоянна вдоль своей собственной «линии уровня» $g=0$, значит $\nabla g$ ей перпендикулярен). Раз нормали совпадают по направлению, значит, векторы $\nabla f$ и $\nabla g$ в точке условного экстремума параллельны (коллинеарны) друг другу — направлены либо одинаково, либо строго противоположно.

Метод: в точке условного экстремума функции $f(x,y)$ при ограничении $g(x,y)=0$ градиент целевой функции обязан быть коллинеарен градиенту ограничения:

$$\nabla f(x,y) = \lambda \, \nabla g(x,y)$$

для некоторого числа $\lambda$ (множителя Лагранжа), которое показывает, во сколько раз и в какую сторону градиенты отличаются по длине.

Заметь, что параллельность градиентов — это условие необходимое, но не привязанное к тому, максимум это или минимум: оно просто означает «дальше двигаться вдоль ограничения без изменения значения $f$ в первом порядке нельзя», то есть это критическая точка условной задачи, кандидат и на максимум, и на минимум (а иногда и вовсе не экстремум, а своего рода «условная седловая точка» — но об этом позже).

Почему это важно

Условие $\nabla f = \lambda\nabla g$ — это, по сути, честный перевод интуитивно понятной картинки («тропа касается линии уровня») на строгий язык векторной алгебры. Именно эта идея — заменить геометрическое условие касания на алгебраическое условие параллельности градиентов — и открывает дорогу к практическому методу решения: вместо того чтобы возиться с касательными прямыми и геометрическими построениями, мы просто выпишем уравнение $\nabla f=\lambda\nabla g$ покоординатно и получим систему алгебраических уравнений, которую (в отличие от геометрии) можно решать чисто механически. Этим и займёмся в следующем разделе.

Функция Лагранжа и система уравнений

Интуиция: одна функция вместо ограничения и множителя

Условие $\nabla f=\lambda\nabla g$ вместе с самим ограничением $g(x,y)=0$ образуют систему из трёх уравнений (две координаты градиентного условия плюс само ограничение) относительно трёх неизвестных: $x$, $y$ и $\lambda$. Это уже рабочий рецепт, но Лагранж придумал, как записать эту же систему ещё компактнее и элегантнее — так, чтобы вся она получалась автоматически из одного-единственного условия «взять частные производные и приравнять к нулю», в точности как в обычной безусловной задаче.

Представь, что мы строим новую вспомогательную функцию трёх переменных — назовём её функцией Лагранжа, — которая «замешивает» исходную целевую функцию с ограничением, домноженным на новую переменную $\lambda$:

Идея на первый взгляд выглядит как трюк, но давай проверим, что она действительно работает, взяв частные производные этой новой функции по всем трём переменным — $x$, $y$ и $\lambda$ — и приравняв их к нулю (то есть решая для $L$ обычную безусловную задачу на экстремум, ровно как в прошлом уроке).

Метод: функция Лагранжа для задачи «найти экстремум $f(x,y)$ при условии $g(x,y)=0$» строится так:

$$L(x,y,\lambda) = f(x,y) + \lambda\, g(x,y)$$

Точки условного экстремума ищутся среди решений системы уравнений $\nabla L = 0$, то есть:

$$\frac{\partial L}{\partial x} = \frac{\partial f}{\partial x} + \lambda\frac{\partial g}{\partial x} = 0, \qquad \frac{\partial L}{\partial y} = \frac{\partial f}{\partial y} + \lambda\frac{\partial g}{\partial y} = 0, \qquad \frac{\partial L}{\partial \lambda} = g(x,y) = 0$$

Обрати внимание, что происходит в этой системе. Первые два уравнения — это ровно покоординатная запись условия $\nabla f = -\lambda\nabla g$ (знак множителя здесь чисто условность записи, о ней ниже), то есть геометрического условия параллельности градиентов, которое мы вывели интуитивно в предыдущем разделе. А третье уравнение, полученное простым дифференцированием $L$ по $\lambda$, — это ни что иное, как само исходное ограничение $g(x,y)=0$, вернувшееся к нам «бесплатно», без каких-либо дополнительных усилий, просто как побочный продукт дифференцирования по искусственно введённой переменной $\lambda$. Это и есть главная магия метода Лагранжа: единственная функция $L$ и единственная операция «взять градиент и приравнять к нулю» автоматически порождают и условие параллельности градиентов, и само ограничение — то есть ровно всю систему, которую нужно решить.

Маленькое техническое замечание про знак: некоторые учебники пишут функцию Лагранжа как $L=f-\lambda g$ вместо $L=f+\lambda g$. Разницы по сути никакой: множитель $\lambda$ — это просто вспомогательное число, которое в конце решения задачи, как правило, само по себе не нужно (нужны только $x$ и $y$), и оно просто поменяет знак в зависимости от выбранного соглашения. Мы придерживаемся варианта со знаком «плюс» — так и продолжай для единообразия, но встретив в другом источнике «минус», не пугайся: результат для $x,y$ будет тот же самый.

Разбор примеров

Пример 1 (лёгкий). Найти экстремум функции $f(x,y)=xy$ при ограничении $x+y=10$.

Прежде всего, приводим ограничение к стандартному виду $g(x,y)=0$: $g(x,y)=x+y-10=0$.

Составляем функцию Лагранжа:

Берём частные производные и приравниваем к нулю:

Из первых двух уравнений: $y=-\lambda$ и $x=-\lambda$, значит $x=y$. Подставляем в третье уравнение: $x+x-10=0\Rightarrow x=5$, значит и $y=5$.

Ответ: критическая точка условной задачи — $(5,5)$, значение функции $f(5,5)=25$. Это максимум: если взять любую другую пару чисел с той же суммой (скажем, $x=1,y=9$: $f=9$, или $x=9{,}9,y=0{,}1$: $f\approx0{,}99$), произведение окажется меньше $25$ — интуитивно понятно, что при фиксированной сумме произведение двух чисел максимально, когда числа равны.

Пример 2 (средний). Найти точку окружности $x^2+y^2=8$, ближайшую и самую дальнюю от точки $(4,0)$.

Здесь целевая функция — квадрат расстояния до точки $(4,0)$ (квадрат берём для удобства дифференцирования — минимум квадрата расстояния достигается в той же точке, что и минимум самого расстояния, так как квадратный корень — монотонно возрастающая функция): $f(x,y)=(x-4)^2+y^2$. Ограничение: $g(x,y)=x^2+y^2-8=0$.

Функция Лагранжа:

Частные производные:

Из второго уравнения: $2y(1+\lambda)=0$, значит либо $y=0$, либо $\lambda=-1$.

Случай $y=0$. Из ограничения: $x^2=8\Rightarrow x=\pm2\sqrt2$. Получаем две точки: $(2\sqrt2,0)$ и $(-2\sqrt2,0)$.

Случай $\lambda=-1$. Из первого уравнения: $2(x-4)+2\cdot(-1)\cdot x=0\Rightarrow 2x-8-2x=0\Rightarrow-8=0$ — противоречие, решений нет. Значит, остаются только точки из первого случая.

Вычисляем расстояния (точнее, значения $f$) в найденных точках: $f(2\sqrt2,0)=(2\sqrt2-4)^2\approx(2{,}828-4)^2\approx1{,}373$; $f(-2\sqrt2,0)=(-2\sqrt2-4)^2\approx(-6{,}828)^2\approx46{,}627$.

Ответ: ближайшая к точке $(4,0)$ точка окружности — $(2\sqrt2,0)\approx(2{,}828,\,0)$ (расстояние $\approx1{,}172$), а самая дальняя — $(-2\sqrt2,0)\approx(-2{,}828,\,0)$ (расстояние $\approx6{,}828$). Заметь важную деталь: обе точки лежат на прямой, соединяющей центр окружности и точку $(4,0)$, — что абсолютно логично геометрически: ближайшая и дальняя точки окружности от внешней точки всегда лежат на прямой через центр.

Пример 3 (сложный, задача на условный экстремум с тремя переменными и содержательной проверкой). Прямоугольный параллелепипед (коробка) имеет фиксированную площадь полной поверхности $S=24$. Найти размеры коробки, максимизирующие её объём.

Пусть рёбра коробки — $x,y,z>0$. Объём: $f(x,y,z)=xyz$. Ограничение на площадь поверхности: $2(xy+yz+xz)=24$, то есть $g(x,y,z)=xy+yz+xz-12=0$.

Функция Лагранжа (теперь уже трёх переменных плюс множитель):

Частные производные по всем переменным:

Так как ищем максимум объёма, разумно предположить (и потом строго проверить), что оптимальная коробка — куб, то есть $x=y=z$. Проверим эту гипотезу прямой подстановкой в первые три уравнения: при $x=y=z$ все три уравнения превращаются в одно и то же тождество $x^2+2\lambda x=0\Rightarrow \lambda=-\dfrac{x}{2}$ (при $x\ne0$) — то есть система действительно удовлетворяется при любом $x=y=z$, значит симметричное решение — законный кандидат.

Подставляем $x=y=z$ в ограничение: $x^2+x^2+x^2=12\Rightarrow3x^2=12\Rightarrow x^2=4\Rightarrow x=2$ (берём положительный корень, так как длина ребра не может быть отрицательной).

Ответ: $x=y=z=2$ — оптимальная коробка есть куб с ребром $2$, объём составляет $f(2,2,2)=8$. Строгое доказательство, что это именно максимум (а не просто критическая точка), а также доказательство, что асимметричные решения системы (если бы они существовали) давали бы меньший объём, требует более тонкого анализа границы допустимой области (при $x,y,z\to0$ или $\to\infty$ объём стремится к нулю при фиксированной площади поверхности, значит внутренний максимум существует и, по симметрии задачи относительно перестановки $x,y,z$, должен достигаться в симметричной точке) — здесь мы полагаемся на этот содержательный аргумент вместо развёрнутого анализа вторых производных по трём переменным, что для линии базового курса вполне достаточно.

Почему это важно

Метод функции Лагранжа превращает геометрически понятную, но алгебраически неудобную идею («градиенты коллинеарны») в чисто механическую процедуру: составь $L$, продифференцируй по всем переменным (включая $\lambda$), реши получившуюся систему. Это тот же самый переход от интуиции к алгоритму, который мы уже видели в прошлом уроке при переходе от «вершина холма — там, где всё плоско» к «$\nabla f=0$» — только теперь холм заменён тропой, а условие плоскостности — условием параллельности градиентов. Именно эта механичность и делает метод Лагранжа применимым не только вручную, на бумаге, но и внутри численных алгоритмов оптимизации, которые решают точно такие же системы уравнений автоматически, зачастую с сотнями и тысячами переменных и ограничений одновременно — как раз то, что происходит внутри SVM, к которому мы вернёмся чуть позже.

Метод множителей Лагранжа для нескольких ограничений

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

Метод (несколько ограничений): чтобы найти экстремум функции $f(x_1,\dots,x_n)$ при $m$ ограничениях $g_1(x_1,\dots,x_n)=0,\ \dots,\ g_m(x_1,\dots,x_n)=0$ (где $m $$L(x_1,\dots,x_n,\lambda_1,\dots,\lambda_m) = f(x_1,\dots,x_n) + \sum_{i=1}^{m}\lambda_i\, g_i(x_1,\dots,x_n)$$

Условие экстремума — обращение в ноль всех частных производных, как по исходным переменным, так и по всем множителям:

$$\frac{\partial L}{\partial x_k}=0 \ (k=1,\dots,n), \qquad \frac{\partial L}{\partial \lambda_i}=0 \ (i=1,\dots,m)$$

что даёт систему из $n+m$ уравнений с $n+m$ неизвестными.

Геометрически это обобщение той же самой идеи параллельности градиентов, только теперь градиент целевой функции $\nabla f$ должен быть представим как линейная комбинация градиентов всех ограничений: $\nabla f=-\sum_i\lambda_i\nabla g_i$ (это условие называют условием стационарности функции Лагранжа, и в более общем контексте выпуклой оптимизации оно является частью так называемых условий Каруша-Куна-Таккера, о которых чуть подробнее скажем в разделе про интересные факты). Интуитивно: если раньше одна тропа-ограничение допускала движение вдоль одной кривой, то теперь пересечение нескольких поверхностей-ограничений оставляет ещё меньше свободы — и градиент целевой функции обязан «укладываться» в подпространство, натянутое на градиенты всех ограничений сразу, иначе вдоль допустимого множества всегда найдётся направление, улучшающее $f$.

Пример. Найти экстремум функции $f(x,y,z)=x+y+z$ при двух ограничениях: $x^2+y^2+z^2=1$ (единичная сфера) и $x+y=0$ (плоскость).

Обозначим $g_1=x^2+y^2+z^2-1=0$ и $g_2=x+y=0$. Функция Лагранжа:

Частные производные:

Из первых двух уравнений вычитанием получаем $2\lambda_1(x-y)=0$. Если $\lambda_1\ne0$, то $x=y$ — и вместе с ограничением $x+y=0$ это даёт $x=y=0$. Тогда из ограничения на сферу: $z^2=1\Rightarrow z=\pm1$. Из третьего уравнения: $1+2\lambda_1 z=0\Rightarrow\lambda_1=-\dfrac1{2z}$, что при $z=\pm1$ даёт конкретное непротиворечивое значение $\lambda_1$ — решение согласовано.

Ответ: критические точки — $(0,0,1)$ со значением $f=1$ и $(0,0,-1)$ со значением $f=-1$. Максимум функции на пересечении сферы и плоскости равен $1$ в точке $(0,0,1)$, минимум равен $-1$ в точке $(0,0,-1)$.

Связь с методом опорных векторов (SVM)

Интуиция: максимальный зазор — это тоже условный экстремум

Давай теперь разберём обещанную связь с машинным обучением подробно, потому что именно ради неё этот урок так важен для тебя. Представь задачу бинарной классификации: у тебя есть точки двух классов на плоскости (или в пространстве большей размерности), помеченные метками $y_i=+1$ или $y_i=-1$, и ты хочешь провести между ними разделяющую прямую (в общем случае — гиперплоскость) $w\cdot x+b=0$, которая максимально уверенно разделяет классы. «Максимально уверенно» в SVM означает конкретную вещь: зазор (margin) — расстояние от разделяющей гиперплоскости до ближайших точек каждого класса — должен быть максимален.

Можно показать, что при подходящей нормировке весов $w$ ширина зазора равна $\dfrac{2}{|w|}$, а условие, что все точки классифицированы правильно и находятся хотя бы на расстоянии этого зазора от границы, записывается как $y_i(w\cdot x_i+b)\ge1$ для всех обучающих точек $i$. Максимизировать зазор $\dfrac{2}{|w|}$ — то же самое, что минимизировать $|w|$ (а для удобства дифференцирования — минимизировать $\dfrac12|w|^2$). Получаем задачу оптимизации:

Обрати внимание: здесь ограничения — не равенства, а неравенства (это как раз обобщение метода Лагранжа, о котором мы упомянули выше, — условия Каруша-Куна-Таккера). Но идея построения функции Лагранжа абсолютно та же самая: заводим по множителю $\lambda_i\ge0$ на каждое ограничение-неравенство (в литературе по SVM множители традиционно обозначают буквой $\alpha_i$, но суть та же) и строим функцию:

Метод: дифференцируя функцию Лагранжа SVM по весам $w$ и по смещению $b$ и приравнивая к нулю, получают:

$$\frac{\partial L}{\partial w} = w - \sum_i\lambda_i y_i x_i = 0 \ \Rightarrow \ w=\sum_i\lambda_i y_i x_i, \qquad \frac{\partial L}{\partial b} = -\sum_i \lambda_i y_i = 0$$

Первое из этих равенств — одно из самых красивых и содержательных мест во всём машинном обучении: оптимальный вектор весов $w$ раскладывается как линейная комбинация обучающих точек $x_i$, причём с коэффициентами $\lambda_i$, которые в подавляющем большинстве случаев равны в точности нулю! Точки, у которых $\lambda_i>0$ (их обычно совсем немного по сравнению с полным размером выборки), и называются опорными векторами (support vectors) — это ровно те точки, что лежат непосредственно на границе зазора и «держат» на себе всю конструкцию оптимальной гиперплоскости. Все остальные точки обучающей выборки, лежащие «в глубине» своего класса, дальше от границы, вообще не влияют на итоговое решение — их множители Лагранжа равны нулю, они как будто не участвовали в обучении. Это удивительный и практически очень полезный факт: модель SVM можно полностью восстановить, зная только небольшое подмножество обучающих точек — опорные векторы, — а не всю выборку целиком. И название всего метода, Support Vector Machine, произошло ровно от этого явления.

Дальнейшая подстановка найденных выражений для $w$ обратно в функцию Лагранжа приводит к так называемой двойственной задаче — задаче максимизации некоторой функции уже только от множителей $\lambda_i$ (без $w$ и $b$), которую на практике и решают численно внутри библиотек вроде libsvm. Разбор этого перехода в полной строгости выходит за рамки одного урока математического анализа (это уже область выпуклой оптимизации и теории двойственности), но важно, чтобы ты уже сейчас видел главную нить: без метода множителей Лагранжа, который мы разобрали на школьных примерах про бассейны и коробки, не было бы и алгебраического пути к формуле $w=\sum_i\lambda_i y_i x_i$ — сердцу метода опорных векторов.

Почему это важно

Связь между «найти минимум площади забора при ограничении на периметр» и «найти оптимальную разделяющую гиперплоскость в SVM» — это не натянутая аналогия, а буквально один и тот же математический механизм, применённый к разным задачам. Как только ты один раз честно разобрал, откуда берётся условие $\nabla f=\lambda\nabla g$ и как из него строится $L=f+\lambda g$, ты автоматически понимаешь логику вывода куда более сложных вещей — двойственной задачи SVM, условий Каруша-Куна-Таккера в выпуклой оптимизации, регуляризации через штрафные слагаемые. Это ровно тот случай, когда «скучная» школьная задача о заборе оказывается прямым концептуальным предком одного из самых элегантных алгоритмов современного машинного обучения.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Найти экстремум функции $f(x,y)=x+y$ при ограничении $x^2+y^2=2$.

Задание 2: Максимизировать произведение $xy$ при условии $x+y=20$.

Задание 3: Найти минимум $f(x,y)=x^2+y^2$ при ограничении $x+2y=5$.

Задание 4: Найти экстремумы функции $f(x,y)=xy$ при ограничении $x^2+y^2=8$.

Задание 5: Прямоугольник вписан в ограничение на периметр $2x+2y=40$. Максимизировать площадь $S=xy$.

Задание 6: Найти точку прямой $2x+y=10$, ближайшую к началу координат.

Задание 7 (машинное обучение): Регуляризованная задача: минимизировать $f(w_1,w_2)=w_1^2+w_2^2$ при ограничении $w_1+w_2=1$ (упрощённая модель с двумя весами и линейным ограничением на их сумму).

Задание 8: Найти экстремум $f(x,y)=x^2y$ при ограничении $x+y=3$ (проверить, что найденная точка удовлетворяет ограничению).

Задание 9: Найти минимум суммы квадратов $f(x,y,z)=x^2+y^2+z^2$ при ограничении $x+y+z=6$.

Задание 10: Составить функцию Лагранжа и выписать (не решая до конца) систему уравнений для задачи: максимизировать $f(x,y)=\ln x+\ln y$ при ограничении $x+y=4$ (заодно проверить область определения $x,y>0$).

Средние задания (11–20)

Задание 11: Найти экстремум функции $f(x,y)=x^2-y^2$ на эллипсе $x^2+4y^2=4$.

Задание 12: Коробка без крышки изготавливается из листа картона $60\times40$ см вырезанием квадратов со стороной $t$ по углам. Объём коробки $V(t)=t(60-2t)(40-2t)$. Здесь ограничения на форму нет (это безусловная задача одной переменной), но сформулируй её как условную задачу с двумя переменными $x,y$ — размерами дна — и ограничением на связь $x,y$ с $t$ через периметр вырезаемого материала. Затем найди оптимальное $t$ прямым дифференцированием.

Задание 13 (машинное обучение): В задаче регуляризованной линейной регрессии с одним весом упрощённо рассмотрим минимизацию $f(w)=(w-5)^2$ при жёстком ограничении на норму $w^2=4$ (аналог ограничения весов единичной сферой в SVM, только в одномерном случае). Найти оптимальное $w$.

Задание 14: Найти экстремум $f(x,y)=4x+3y$ при ограничении $x^2+y^2=25$.

Задание 15: Максимизировать полезность $U(x,y)=\sqrt{x}\cdot\sqrt{y}$ при бюджетном ограничении $2x+3y=120$.

Задание 16: Найти минимум $f(x,y)=x^2+2y^2$ при ограничении $x+y=3$.

Задание 17 (машинное обучение): В упрощённой модели SVM с одним признаком рассматриваем минимизацию $\dfrac12w^2$ при единственном ограничении-равенстве $y_1(wx_1+b)=1$, где $y_1=1$, $x_1=2$, $b=0$ (то есть ограничение $2w=1$). Найти оптимальный вес $w$ методом Лагранжа и убедиться, что он совпадает с прямым решением ограничения.

Задание 18: Найти экстремум $f(x,y)=x^2y^2$ при ограничении $x^2+y^2=4$.

Задание 19: Найти минимум $f(x,y,z)=x^2+y^2+z^2$ при двух ограничениях: $x+y+z=6$ и $x-y=0$.

Задание 20: Найти экстремум функции $f(x,y)=2x+y$ на эллипсе $x^2+4y^2=4$.

Продвинутые задания (21–30)

Задание 21: Найти минимальную сумму $x+y+z$ при ограничении $xyz=8$ (для положительных $x,y,z$).

Задание 22 (машинное обучение, SVM): Упрощённая двумерная SVM-задача: минимизировать $\dfrac12(w_1^2+w_2^2)$ при единственном активном ограничении $y_1(w_1x_{11}+w_2x_{12}+b)=1$, где точка $x_1=(3,4)$, $y_1=1$, $b=0$ (то есть ограничение $3w_1+4w_2=1$). Найти оптимальные веса.

Задание 23: Найти точку плоскости $x+y+z=12$, ближайшую к началу координат.

Задание 24: Найти экстремумы функции $f(x,y)=x^2+y^2$ при ограничении $\dfrac{x^2}{4}+\dfrac{y^2}{9}=1$ (эллипс с полуосями $2$ и $3$).

Задание 25: Netflix максимизирует охват аудитории $f(x,y,z)=xy+yz+xz$ (взаимное усиление трёх типов контента) при бюджете $x+2y+3z=60$. Найти оптимальное распределение бюджета между тремя переменными.

Задание 26: Доказать методом Лагранжа, что среди всех прямоугольников с фиксированным периметром $P$ квадрат имеет наибольшую площадь (общий вид задачи 5).

Задание 27 (машинное обучение, регуляризация): Показать, что минимизация $f(w)=(w-a)^2$ при жёстком ограничении на норму $w^2=r^2$ (аналог L2-ограничения радиуса $r$ вокруг нуля) даёт решение $w=r$ при условии $a>0$ (найти общее выражение и проверить на конкретных числах $a=10$, $r=3$).

Задание 28: Найти экстремум $f(x,y,z)=xyz$ при ограничении $x+y+z=12$ (для положительных $x,y,z$; вариация задачи о коробке без ограничения на площадь поверхности).

Задание 29: Найти минимум функции $f(x,y)=e^{x+y}$ при ограничении $x^2+y^2=2$ (обрати внимание, что экспонента монотонна, значит экстремумы $f$ достигаются там же, где экстремумы показателя $x+y$).

Задание 30 (машинное обучение, обобщение SVM на три опорные точки): В упрощённой SVM-задаче с двумя весами $w_1,w_2$ и тремя ограничениями-равенствами от трёх опорных точек рассматривается функция Лагранжа $L=\dfrac12(w_1^2+w_2^2)+\sum_{i=1}^3\lambda_i\big[1-y_i(w_1x_{i1}+w_2x_{i2})\big]$. Выписать (не решая численно) итоговое выражение для оптимальных весов через множители $\lambda_i$ и объяснить, почему оно и есть формула $w=\sum_i\lambda_iy_ix_i$ из теории.

Частые ошибки

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

Первая и самая распространённая ошибка — забыть привести ограничение к стандартному виду $g(x,y)=0$. Если условие дано как $x+y=10$, его нужно явно переписать как $g(x,y)=x+y-10=0$ (перенести всё в одну сторону), а не подставлять «как есть» в функцию Лагранжа. Небрежность здесь не всегда меняет итоговый ответ (потому что константа при дифференцировании по $\lambda$ всё равно вернёт исходное уравнение), но систематически приводит к путанице со знаками при промежуточных вычислениях.

Вторая ошибка — не проверить, что найденное решение действительно удовлетворяет исходному ограничению. Метод Лагранжа даёт систему уравнений, а любая система уравнений теоретически может иметь посторонние или потерянные решения (особенно если по дороге производилось деление на переменную, которая могла оказаться нулём). Всегда подставляй финальные $x,y$ обратно в $g(x,y)=0$ — это дешёвая, но надёжная страховка от арифметических ошибок.

Третья ошибка — путать критическую точку условной задачи с гарантированным экстремумом. Метод Лагранжа находит все точки, где градиенты параллельны, — это необходимое условие экстремума, но не достаточное. Среди найденных критических точек может быть как максимум, так и минимум, а иногда и точка, вообще не являющаяся ни тем, ни другим (аналог седловой точки, только «вдоль ограничения»). Чтобы различить их, нужно либо явно сравнить значения $f$ во всех найденных критических точках (как мы систематически делали в разборе примеров), либо привлечь более тонкий анализ через окаймлённый гессиан — вторую производную функции Лагранжа с учётом ограничения (эта техника выходит за рамки базового курса, но важно хотя бы знать, что она существует).

Четвёртая ошибка — деление на переменную или выражение, которое может обращаться в ноль, без явного разбора случая, когда оно равно нулю. В разборе примеров ты видел не раз: уравнение вида $y(-1+4\lambda)=0$ распадается на два случая — $y=0$ или $\lambda=\dfrac14$, — и оба случая нужно честно рассмотреть по отдельности, а не бездумно сокращать на $y$.

Пятая ошибка — забыть про множитель $\lambda$ при нескольких ограничениях: у каждого ограничения обязан быть свой собственный множитель ($\lambda_1$, $\lambda_2$ и так далее), а не один общий на все ограничения сразу. Смешивание нескольких ограничений в одно слагаемое с общим множителем ломает всю логику метода: каждое ограничение вносит независимое требование, и градиент целевой функции обязан раскладываться по всем ограничениям одновременно, с собственным коэффициентом для каждого.

Шестая, более концептуальная ошибка — путать знак в записи функции Лагранжа ($L=f+\lambda g$ против $L=f-\lambda g$) с ошибкой в вычислениях. Оба варианта корректны, просто в них множитель $\lambda$ получится с противоположным знаком; главное — придерживаться одного выбранного соглашения на протяжении всего решения одной задачи, не перескакивая с одного на другое посередине выкладок.

Главное запомнить

• Условный экстремум — это поиск максимума или минимума функции $f(x,y)$ не во всём пространстве, а только на множестве точек, удовлетворяющих ограничению $g(x,y)=0$.

• Геометрическая суть метода: в точке условного экстремума линия уровня функции $f$ касается кривой ограничения $g=0$, а значит их градиенты в этой точке коллинеарны (параллельны).

• Формально условие параллельности записывается как $\nabla f=\lambda\nabla g$, где $\lambda$ — множитель Лагранжа, число, показывающее пропорцию между градиентами.

• Функция Лагранжа $L(x,y,\lambda)=f(x,y)+\lambda g(x,y)$ «упаковывает» и условие параллельности градиентов, и само ограничение в единую систему уравнений $\nabla L=0$.

• Система уравнений метода Лагранжа состоит из частных производных $L$ по $x$, по $y$ и по $\lambda$, причём последнее уравнение автоматически возвращает исходное ограничение.

• Для нескольких ограничений $g_1=0,\dots,g_m=0$ на каждое заводится собственный множитель $\lambda_i$, и функция Лагранжа складывается из целевой функции и суммы всех произведений $\lambda_i g_i$.

• Метод даёт только необходимое условие экстремума (критические точки условной задачи); чтобы понять, максимум это или минимум, нужно либо сравнить значения $f$ во всех найденных точках, либо привлечь более тонкий анализ вторых производных.

• Метод опорных векторов (SVM) выводится ровно этим же приёмом: минимизация $\dfrac12|w|^2$ при ограничениях правильной классификации даёт после дифференцирования функции Лагранжа формулу $w=\sum_i\lambda_iy_ix_i$.

• Опорные векторы в SVM — это в точности те обучающие точки, у которых множитель Лагранжа $\lambda_i>0$; все остальные точки формально не влияют на итоговую модель.

• Метод множителей Лагранжа — прямой концептуальный предок условий Каруша-Куна-Таккера для ограничений-неравенств, теории двойственности в выпуклой оптимизации и идеи регуляризации через штрафные слагаемые в функции потерь.

Связь с другими темами курса

Метод множителей Лагранжа опирается напрямую на понятие градиента и его геометрический смысл (перпендикулярность линиям уровня) из уроков про производную по направлению и градиент, а также на весь аппарат безусловных экстремумов функций нескольких переменных из предыдущего урока — критические точки, классификацию через вторые производные. Вперёд метод Лагранжа тянет сразу несколько важных линий: в курсах по оптимизации он обобщается на условия Каруша-Куна-Таккера (KKT) для ограничений-неравенств, что и есть теоретический фундамент двойственной задачи SVM; в вариационном исчислении и физике та же самая идея множителей применяется к функционалам (принцип наименьшего действия в механике, из которого выводятся уравнения движения, — прямой потомок задачи Лагранжа о равновесии связанных систем); а в статистике и машинном обучении множители Лагранжа неявно стоят за идеей регуляризации: штрафное слагаемое $\lambda\|w\|^2$ в функции потерь исторически и математически восходит к переходу от жёсткого ограничения на норму весов к его «штрафному» аналогу через множитель.

Интересные факты

Метод множителей Лагранжа был впервые опубликован в 1788 году в трактате «Аналитическая механика» — книге, которую сам Лагранж с гордостью описывал как труд, не содержащий ни единого чертежа: вся механика в ней изложена чисто аналитически, алгебраическими средствами, без единой геометрической иллюстрации — подход, который во многом определил стиль математической физики на следующие два столетия.

Обобщение метода Лагранжа на ограничения-неравенства (не только $g(x)=0$, но и $g(x)\le0$) было независимо предложено Уильямом Каруном в 1939 году в его магистерской диссертации в Чикагском университете — и оставалось практически незамеченным почти десять лет, пока Гарольд Кун и Альберт Таккер не переоткрыли и не опубликовали те же самые условия в 1951 году. С тех пор эти условия называют условиями Каруша-Куна-Таккера (KKT), хотя долгое время в литературе их называли только условиями Куна-Таккера, несправедливо забывая первооткрывателя.

Название Support Vector Machine (метод опорных векторов) впервые появилось в статье Владимира Вапника и Алексея Червоненкиса, а окончательная современная форма алгоритма с мягким зазором (soft margin) и ядерным трюком (kernel trick) была предложена Вапником с соавторами уже в 1990-х годах в лабораториях Bell Labs; при этом ключевая математическая идея — переход к двойственной задаче через множители Лагранжа — оставалась той же самой идеей двухсотлетней давности, просто применённой к принципиально новой прикладной области.

Множители Лагранжа в экономике получили собственную содержательную интерпретацию: значение оптимального множителя $\lambda$ в задаче максимизации прибыли при ограниченном ресурсе (скажем, бюджете или сырье) равно предельной полезности этого ресурса — иными словами, показывает, насколько вырастет максимальная прибыль, если немного увеличить доступный ресурс. Экономисты называют эту величину «теневой ценой» (shadow price) ресурса, и она активно используется при принятии решений о том, стоит ли инвестировать в увеличение производственных мощностей.

Лайфхаки и полезные трюки

Если ограничение линейно (вида $ax+by=c$), а целевая функция — простое произведение или сумма квадратов, часто можно угадать симметричное решение сразу, без выкладок: например, при максимизации произведения $xy$ на фиксированной сумме $x+y=S$ ответ всегда $x=y=\dfrac S2$ — этот факт стоит запомнить как готовый шаблон, чтобы быстро проверять правильность более длинных вычислений.

Если после составления системы уравнений возникает деление на переменную (скажем, из $2\lambda x=2\lambda y$ хочется сразу сократить на $2\lambda$), никогда не сокращай молча — сначала явно распиши оба случая: «$\lambda=0$» и «$x=y$», и проверь оба, даже если один из них кажется заведомо неинтересным. Часто именно отброшенный без проверки случай оказывается источником потерянного решения.

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

При работе с несколькими ограничениями удобно сначала записать систему в общем виде, а потом методично вычитать уравнения друг из друга, выражая одни переменные через другие (как мы делали в задачах на несколько ограничений выше), — это почти всегда быстрее и надёжнее, чем решать все уравнения одновременно в лоб.

Когда в задаче фигурирует логарифм или квадратный корень целевой функции (как в задаче про полезность), не бойся заменить исходную функцию на её монотонное преобразование — логарифм или квадрат: точка экстремума от этого не сдвинется (так как монотонное преобразование сохраняет порядок значений), а выкладки часто становятся заметно проще.

Держи в голове наглядную проверку правильности знака множителя $\lambda$: если задача на максимум и ты нашёл два кандидата с противоположными значениями $\lambda$, тот кандидат, что даёт большее значение целевой функции, — это и есть искомый максимум; сравнение чисел в конце решения — самый надёжный способ отличить максимум от минимума без углубления в теорию вторых производных.

Метод множителей Лагранжа — это, наверное, одна из самых «щедрых» тем университетской математики: один и тот же приём, который ты сегодня отработал на простеньких задачах про заборы, окружности и коробки, работает без единого изменения логики и в вывод одного из самых элегантных алгоритмов машинного обучения. В следующий раз, когда увидишь в документации scikit-learn слова support vectors или dual coefficients, вспомни: за этими терминами стоит ровно та же самая функция Лагранжа $L=f+\lambda g$, которую ты только что научился составлять и дифференцировать своими руками. Впереди — двойные интегралы, но эта тема, поверь, не менее интересна и заслуживает такого же вдумчивого разбора.