Выпуклые множества 🔷

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

Возьми задачу, с которой ты наверняка уже сталкивался или скоро столкнёшься на практике: обучение SVM или Lasso-регрессии с ограничением на размер весов. В SVM ты ищешь вектор весов $w$, задающий разделяющую гиперплоскость, и часто явно или неявно требуешь $\|w\|_2 \le C$ — не позволяешь весам расти бесконечно, чтобы модель не переобучалась и margin оставался разумным. В Lasso-регрессии constrained-формулировка требует $\|w\|_1 \le t$ — сумма модулей весов ограничена сверху, что на практике обнуляет часть коэффициентов и отбирает признаки. В обоих случаях допустимое множество весов $D$ — это не что попало, а конкретная геометрическая фигура: шар в первом случае, «ромб» (точнее, кросс-политоп) во втором. И то, что обе эти фигуры выпуклые — не случайное совпадение и не второстепенная деталь, а именно то условие, которое гарантирует: задача имеет глобальный минимум, до него можно эффективно добраться градиентными или квадратичными методами, и результат не зависит от того, с какой точки стартовал алгоритм.

Если бы допустимое множество весов было невыпуклым — например, состояло из двух отдельных «островов» разрешённых значений, — та же самая целевая функция могла бы иметь несколько несравнимых локальных решений в разных островах, и никакой алгоритм не мог бы гарантированно сказать, какое из них лучше, не перебрав их все. Именно поэтому теория выпуклых множеств — это не абстрактная геометрия ради геометрии, а необходимый фундамент для понимания того, почему SVM, Lasso, ridge-регрессия и линейное программирование решаются настолько предсказуемо и быстро, тогда как обучение глубокой нейросети — принципиально другая, гораздо менее предсказуемая история.

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

История

Систематическое изучение выпуклых фигур как самостоятельного математического объекта началось на рубеже XIX–XX веков с работ немецкого математика Германа Минковского. В 1896 году в трактате «Geometrie der Zahlen» («Геометрия чисел») он ввёл понятие выпуклого тела как инструмент для задач теории чисел — как ни странно, изначально выпуклость понадобилась не для оптимизации, а для доказательств о целочисленных решениях диофантовых уравнений. Минковский показал, что у выпуклых тел есть богатая и при этом на удивление простая структура: их можно складывать («сумма Минковского»), масштабировать, пересекать — и каждая такая операция снова даёт выпуклое тело. Эта алгебраическая устойчивость выпуклости и стала тем свойством, вокруг которого спустя полвека выросла вся теория выпуклой оптимизации.

Второй импульс пришёл из совершенно практической области — военной логистики. В 1947 году американский математик Джордж Данциг, работая над задачами планирования снабжения для ВВС США, сформулировал линейное программирование и придумал симплекс-метод для его решения. Область допустимых решений линейной программы — пересечение конечного числа полупространств — оказалась в точности многогранником, классическим выпуклым множеством, и Данциг заметил, что оптимум линейной задачи всегда достигается в одной из «угловых» точек этого многогранника. Это наблюдение сработало настолько хорошо на практике, что уже к 1950-м линейное программирование стало основным инструментом планирования в экономике, промышленности и логистике — и остаётся им сегодня, просто спрятанным внутри современных ERP-систем и логистических платформ.

Строгая теоретическая база под всё это была подведена чуть позже: в 1951 году Гарольд Кун и Алберт Такер опубликовали условия оптимальности для задач с ограничениями (позже выяснилось, что аналогичный результат ещё в 1939 году в своей магистерской диссертации получил малоизвестный тогда Уильям Каруш — отсюда современное название «условия Каруша–Куна–Таккера», KKT, урок 279 будет целиком об этом), а в 1970 году американский математик Р. Тиррелл Рокафеллар выпустил монографию «Convex Analysis» — книгу, которая систематизировала всю теорию выпуклых множеств и функций в единый аппарат и больше пятидесяти лет спустя всё ещё остаётся настольной книгой для каждого, кто всерьёз занимается оптимизацией. Именно на этом фундаменте в середине 1990-х Владимир Вапник и Коринна Кортес построили метод опорных векторов (SVM), а Роберт Тибширани в 1996 году предложил Lasso-регрессию — оба метода в самой своей постановке используют выпуклые допустимые множества, и оба обязаны своей вычислительной эффективностью ровно тем идеям, которые заложил ещё Минковский за сто лет до появления машинного обучения в его нынешнем виде.

Определение выпуклого множества: весь отрезок целиком

Интуиция

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

Определение

Определение. Множество $C \subseteq \mathbb{R}^n$ называется выпуклым, если для любых двух точек $x, y \in C$ и любого числа $\theta \in [0, 1]$ выполняется

$$\theta x + (1-\theta) y \in C$$

Точка $\theta x + (1-\theta) y$ называется выпуклой комбинацией точек $x$ и $y$ с весом $\theta$; при $\theta$, пробегающем весь отрезок $[0,1]$, эта формула как раз и «заметает» отрезок между $x$ и $y$: при $\theta=1$ получаем точку $x$, при $\theta=0$ — точку $y$, при $\theta=0{,}5$ — середину отрезка.

Определение естественным образом обобщается на произвольное конечное число точек: точка $\sum_{i=1}^k \theta_i x_i$, где $\theta_i \ge 0$ и $\sum_{i=1}^k \theta_i = 1$, называется выпуклой комбинацией точек $x_1, \dots, x_k$, и множество выпукло тогда и только тогда, когда оно содержит любую такую комбинацию своих точек — не только для пар, но и для любого числа точек сразу (это эквивалентное определение, которое несложно вывести из парного по индукции, и оно ещё понадобится в разделе про выпуклую оболочку).

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

Пример 1 (отрезок на прямой). Проверим, что интервал $[a, b] \subset \mathbb{R}$ выпуклый — это самый базовый случай, буквально давший имя всему понятию. Возьмём произвольные $x, y \in [a,b]$ и $\theta \in [0,1]$. Поскольку $a \le x \le b$ и $a \le y \le b$, то

значит $\theta x + (1-\theta) y \in [a,b]$. Отрезок на прямой выпуклый — что, конечно, ожидаемо, ведь само слово «выпуклая комбинация» описывает именно точки отрезка между $x$ и $y$, а определение просто требует, чтобы множество содержало отрезки между всеми своими парами точек.

Пример 2 (шар). Проверим выпуклость шара $B(0, r) = \{x \in \mathbb{R}^n : \|x\| \le r\}$ радиуса $r$ с центром в начале координат — общее доказательство, которое работает для любой нормы, не только евклидовой. Возьмём $x, y \in B(0,r)$, то есть $\|x\| \le r$ и $\|y\| \le r$, и произвольный $\theta \in [0,1]$. По неравенству треугольника и однородности нормы:

Значит, $\theta x + (1-\theta) y \in B(0,r)$ — шар выпуклый, и это доказательство не использует ничего, кроме определения нормы, а значит работает одинаково и для $\ell_2$-шара, и для $\ell_1$-шара, и для любого $\ell_p$-шара при $p \ge 1$ — деталь, которая станет центральной в разделе про допустимые множества в SVM и Lasso. Численно: точки $x=(1,0)$ и $y=(0,1)$ лежат на границе единичного круга ($\|x\|=\|y\|=1$), при $\theta=0{,}5$ их выпуклая комбинация $z = (0{,}5,\ 0{,}5)$ имеет норму $\|z\| = \sqrt{0{,}25+0{,}25} = \sqrt{0{,}5} \approx 0{,}707 < 1$ — заметно внутри круга, что согласуется с общим доказательством.

Пример 3 (L-образная область — невыпуклый случай). Возьмём квадрат $[0,2]\times[0,2]$, из которого вырезан верхний правый угол — область $S = \{(x,y): 0\le x\le2,\ 0\le y\le2\} \setminus \{(x,y): 1

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

Определение через отрезок — это не просто формальность, а рабочий инструмент, который ты применяешь одинаково для любого множества: и для абстрактных допустимых областей в оптимизации, и для конкретных множеств точек данных. Чтобы доказать выпуклость, обычно нужен общий аргумент для произвольной пары точек (как в примерах 1 и 2); чтобы опровергнуть выпуклость, достаточно один раз предъявить конкретную пару точек и конкретное $\theta$, для которых отрезок выходит за границы множества (как в примере 3) — и такую пару-«свидетеля» почти всегда можно найти интуитивно, посмотрев на «подозрительное» место фигуры: выемку, дырку, острый угол внутрь. Этот же приём — «выпуклая комбинация как проверка на равенство» — станет фундаментом определения выпуклой функции через её надграфик (epigraph) в следующем уроке.

Примеры выпуклых и невыпуклых множеств

Интуиция

У выпуклых множеств есть небольшой набор «строительных блоков», из которых почти всё остальное собирается через пересечения: полупространства, шары (нормовые шары), эллипсоиды и многогранники. У невыпуклых фигур такого универсального каталога нет — невыпуклость возникает по-разному: из-за дыры внутри (кольцо), из-за острых вогнутых выемок на границе (звезда), из-за разрыва на несколько частей (объединение фигур). Знание этого каталога экономит массу времени: вместо того чтобы каждый раз доказывать выпуклость с нуля через определение, чаще всего достаточно узнать в допустимом множестве один из знакомых типов фигур.

Формализация

Полупространство $H = \{x \in \mathbb{R}^n : a^Tx \le b\}$, где $a \in \mathbb{R}^n$, $a \ne 0$, $b \in \mathbb{R}$ — множество точек по одну сторону от гиперплоскости $a^Tx=b$. Выпукло для любых $a$, $b$.

Эллипсоид $E = \{x \in \mathbb{R}^n : (x-c)^TA^{-1}(x-c) \le 1\}$, где $c$ — центр, $A$ — симметричная положительно определённая матрица. Частный случай при $A = r^2I$ — обычный шар радиуса $r$. Выпуклый, поскольку является множеством уровня выпуклой квадратичной формы (полное доказательство — в уроке 278 про выпуклые функции).

Многогранник (полиэдр) $P = \{x \in \mathbb{R}^n : Ax \le b\}$ — пересечение конечного числа полупространств, где неравенство понимается покомпонентно. Выпуклый как пересечение конечного числа выпуклых множеств (доказательство — в следующем разделе).

Невыпуклые фигуры формального единого описания не имеют, но у них есть узнаваемый общий признак: где-то на границе или внутри фигуры существует «вогнутость» — направление, в котором прямая линия между двумя точками фигуры выходит за её пределы. Классические примеры — кольцо (аннулус) $\{x \in \mathbb{R}^2 : r_1 \le \|x\| \le r_2\}$ с дырой посередине и звезда — многоугольник с чередующимися «острыми» и «вогнутыми» вершинами.

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

Пример 1 (полупространство). Возьмём $H = \{(x,y): x + 2y \le 4\}$. Точки $A=(0,0)$ и $B=(2,1)$ лежат в $H$ ($0 \le 4$ и $2+2=4\le4$). Середина $M = (1,\ 0{,}5)$: $1 + 2\cdot0{,}5 = 2 \le 4$ ✓. Общее доказательство работает без привязки к конкретным числам: для линейной функции $g(x)=a^Tx$ выполняется $g(\theta x + (1-\theta)y) = \theta g(x) + (1-\theta)g(y) \le \theta b + (1-\theta) b = b$ для любых $x,y \in H$ — линейность гарантирует выпуклость автоматически, без исключений.

Пример 2 (многогранник — треугольник как пересечение трёх полупространств). Три ограничения $x \ge 0$, $y \ge 0$, $x+y \le 4$ задают в пересечении прямоугольный треугольник с вершинами $(0,0)$, $(4,0)$, $(0,4)$. Каждое из трёх полупространств выпукло по примеру 1, а их пересечение — треугольник — тоже выпукло (это прямое применение теоремы о пересечении из следующего раздела, но уже здесь видно, как из простых «плоских разрезов» собирается сложная многоугольная фигура, не теряя выпуклости).

Пример 3 (эллипс). Множество $\{(x,y): 4x^2+9y^2 \le 36\}$ — эллипс с полуосями $3$ по $x$ и $2$ по $y$ (перепишем как $\frac{x^2}{9}+\frac{y^2}{4}\le1$). Точки $(3,0)$ и $(0,2)$ лежат на его границе (обе обращают неравенство в равенство). Середина отрезка между ними — $(1{,}5,\ 1)$: подставляем, $4\cdot1{,}5^2 + 9\cdot1^2 = 9+9=18 \le 36$ — заметно внутри эллипса, с большим запасом. Это согласуется с общим фактом: множество уровня $\{x: q(x)\le c\}$ квадратичной формы $q(x)=x^TAx$ с положительно определённой $A$ всегда выпукло, потому что сама функция $q$ выпуклая (её график — «чаша», и всё, что лежит под определённым уровнем этой чаши, образует выпуклую область; формальное доказательство этого факта — тема следующего урока).

Пример 4 (кольцо — невыпуклое). Возьмём кольцо $\{x \in \mathbb{R}^2: 1 \le \|x\| \le 3\}$. Точки $A=(1,0)$ и $B=(-1,0)$ обе лежат на внутренней границе кольца ($\|A\|=\|B\|=1$). Середина отрезка — $M=(0,0)$, центр координат, и $\|M\|=0 < 1$ — точка $M$ попадает в «дыру» кольца, которая из него исключена. Одной этой пары точек достаточно: кольцо невыпуклое, потому что отрезок между двумя точками на противоположных сторонах дыры неизбежно проходит через саму дыру.

Пример 5 (звезда — невыпуклое). Возьмём правильную пятиконечную звезду (пентаграмму) с внешним радиусом вершин-«лучей» $R=1$ и внутренним радиусом «впадин» между лучами $r \approx 0{,}382$ (стандартное соотношение для правильной пентаграммы). Возьмём вершины двух соседних лучей: одну на угле $90°$ — точку $A=(0,\ 1)$, другую на угле $162°$ — точку $B\approx(-0{,}951,\ 0{,}309)$. Обе — вершины звезды, обе лежат в фигуре. Середина отрезка $M = \left(\frac{0-0{,}951}{2},\ \frac{1+0{,}309}{2}\right) \approx (-0{,}476,\ 0{,}655)$, и расстояние от начала координат до $M$ составляет $\approx\sqrt{0{,}476^2+0{,}655^2} \approx 0{,}809$. Направление на $M$ — это ровно биссектриса между $90°$ и $162°$, то есть угол $126°$, а граница звезды в этом направлении — как раз внутренняя «впадина» на расстоянии всего $\approx 0{,}382$ от центра. Поскольку $0{,}809 \gg 0{,}382$, середина отрезка оказывается далеко за пределами звезды, в невидимой «выемке» между двумя лучами — фигура невыпуклая, и этот же аргумент работает для любой пары несоседних (а тем более соседних) лучей звезды.

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

Этот каталог — не коллекция случайных примеров, а список типов множеств, которые реально встречаются как допустимые области в задачах машинного обучения и оптимизации. Норм-шары — это ограничения регуляризации ($\|w\|\le C$); полупространства — это отдельные линейные ограничения или неравенства margin в SVM; эллипсоиды возникают как доверительные области в статистике и как ограничения в квадратичном программировании; многогранники — это допустимые множества линейного программирования целиком. А кольца и звёзды на практике почти не встречаются как желаемые допустимые множества — зато очень похожие на них по структуре «дырчатые» или «многоостровные» области регулярно возникают как допустимые множества дискретных и комбинаторных задач (например, «выбери ровно один из трёх заводов» или «маршрут должен обходить препятствие»), и именно из-за такой невыпуклой геометрии эти задачи качественно труднее, чем задачи с выпуклым $D$.

Пересечение выпуклых множеств: почему выпуклость сохраняется

Интуиция

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

Теорема и доказательство

Теорема (пересечение выпуклых множеств). Пусть $\{C_i\}_{i \in I}$ — произвольное (в том числе бесконечное) семейство выпуклых множеств в $\mathbb{R}^n$. Тогда их пересечение $C = \bigcap_{i \in I} C_i$ тоже выпукло.

Доказательство. Возьмём произвольные $x, y \in C$ и произвольный $\theta \in [0,1]$. По определению пересечения, $x \in C_i$ и $y \in C_i$ для каждого $i \in I$. Поскольку каждое $C_i$ выпукло, для каждого $i$ выполняется $\theta x + (1-\theta) y \in C_i$. А раз точка $\theta x + (1-\theta) y$ принадлежит каждому множеству семейства, она принадлежит и их пересечению: $\theta x + (1-\theta) y \in \bigcap_{i \in I} C_i = C$. Поскольку $x, y$ и $\theta$ были произвольными, $C$ выпукло. $\blacksquare$

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

Важно также зафиксировать обратное: аналогичное утверждение для объединения неверно. Возьмём два непересекающихся круга — $\{x: \|x-(-3,0)\|\le1\}$ и $\{x:\|x-(3,0)\|\le1\}$. Оба выпуклые по отдельности (это шары). Возьмём по точке из центра каждого круга: $A=(-3,0)$, $B=(3,0)$ — обе лежат в объединении. Середина отрезка $M=(0,0)$ находится строго между кругами, на расстоянии 3 от центра каждого, то есть далеко за пределами обоих радиусов, равных 1. Объединение невыпуклое. Это не исключение, а правило: объединение выпуклых множеств выпукло лишь в вырожденных случаях (например, когда одно множество целиком содержится в другом), а в общем случае логическое «ИЛИ» разрушает выпуклость, тогда как логическое «И» (пересечение) её всегда сохраняет — асимметрия, которая напрямую объясняет, почему задачи с ограничениями вида «выполнено условие 1 И условие 2 И условие 3» обычно выпуклые и решаются легко, а задачи вида «выполнено условие 1 ИЛИ условие 2» почти всегда комбинаторные и решаются на порядки труднее.

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

Пример 1 (клин из двух полупространств). Пересечение $\{x+y\le3\} \cap \{x-y\ge-1\}$ образует клиновидную область на плоскости. Проверять её выпуклость через определение (перебором произвольных точек и отрезков внутри клина) неудобно — форма нетривиальная. Но по теореме этого не требуется вовсе: оба полупространства выпуклы по отдельности, значит их пересечение выпукло автоматически, без единого дополнительного вычисления.

Пример 2 (SVM: допустимая область весов из margin-ограничений). В задаче SVM для обучающей выборки из $n$ точек ограничения имеют вид $y_i(w^Tx_i + b) \ge 1$ для каждого $i=1,\dots,n$ — это $n$ отдельных линейных неравенств относительно переменных $(w,b)$, то есть $n$ полупространств в пространстве параметров. Допустимая область для $(w,b)$ — их пересечение. Для датасета с тысячами примеров явно выписать форму этой области и проверить её выпуклость «руками» немыслимо. Теорема о пересечении даёт этот результат бесплатно: раз каждое из $n$ ограничений выпукло (полупространство), пересечение всех $n$ выпукло — сколько бы примеров ни было в обучающей выборке.

Пример 3 (обрезанный шар — ограничение нормы плюс margin). Более реалистичная постановка SVM с ограничением на норму: допустимая область $D = \{w : \|w\|_2 \le C\} \cap \{w : y_i(w^Tx_i+b)\ge1,\ i=1,\dots,n\}$ — пересечение шара (выпуклый по примеру 2 предыдущего раздела) и $n$ полупространств (каждое выпукло). По теореме о пересечении применённой ко всем $n+1$ множествам сразу, итоговая допустимая область $D$ выпукла — «срезанный» шар, форма которого может быть довольно сложной геометрически, но её выпуклость доказана одной короткой ссылкой на теорему.

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

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

Выпуклая оболочка произвольного множества

Интуиция

В блоке вычислительной геометрии ты уже встречался с идеей «натянуть многоугольник на облако точек» — это алгоритмическая задача построения выпуклой оболочки: найти самый компактный выпуклый контур, охватывающий заданное множество точек, и решить её эффективно (например, за $O(n \log n)$). Здесь та же самая конструкция, но с другой стороны — не «как быстро её построить», а «что она означает» и зачем этот геометрический объект нужен теории оптимизации.

Определение

Определение. Выпуклой оболочкой множества $S \subseteq \mathbb{R}^n$ (не обязательно выпуклого и не обязательно конечного) называется наименьшее по включению выпуклое множество, содержащее $S$. Обозначается $\text{conv}(S)$.

У этого определения есть два эквивалентных описания, каждое из которых полезно по-своему.

Генеративное описание: $\text{conv}(S)$ — это множество всех выпуклых комбинаций конечного числа точек из $S$:

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

Экстремальное описание: $\text{conv}(S)$ — это пересечение всех выпуклых множеств, содержащих $S$:

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

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

Пример 1 (оболочка трёх точек — треугольник). Возьмём $S = \{A(0,0),\ B(4,0),\ C(0,3)\}$. Выпуклая оболочка трёх точек, не лежащих на одной прямой, — это заполненный треугольник с вершинами в этих точках: множество всех точек $\theta_1 A + \theta_2 B + \theta_3 C$ с $\theta_1,\theta_2,\theta_3\ge0$, $\theta_1+\theta_2+\theta_3=1$ (это барицентрические координаты точки внутри треугольника). Например, при $\theta = (1/3, 1/3, 1/3)$ получаем центроид треугольника $(4/3,\ 1)$, а при $\theta=(0,\ 0{,}5,\ 0{,}5)$ — середину стороны $BC$, точку $(2,\ 1{,}5)$.

Пример 2 (оболочка пяти точек — какие из них «выживают»). Возьмём точки $A(0,0)$, $B(4,0)$, $C(4,4)$, $D(0,4)$ (углы квадрата) и $E(2,2)$ — точку строго внутри квадрата. Выпуклая оболочка этих пяти точек — тот же самый квадрат $ABCD$, что и оболочка одних только четырёх угловых точек: точка $E$ уже выражается как выпуклая комбинация $A,B,C,D$ (например, $E = 0{,}25A+0{,}25B+0{,}25C+0{,}25D$), а значит попадает в оболочку автоматически и не добавляет к ней ничего нового. Точки вроде $A,B,C,D$, которые нельзя представить как выпуклую комбинацию других точек множества, называются крайними точками (extreme points) — именно они, а не все точки исходного множества, определяют форму оболочки, и именно их ищут алгоритмы построения выпуклой оболочки вроде обхода Грэхема из блока вычислительной геометрии.

Пример 3 (оболочка двух непересекающихся кругов — «стадион»). Возьмём объединение двух кругов $\{\|x-(-3,0)\|\le1\}$ и $\{\|x-(3,0)\|\le1\}$ из предыдущего раздела — само объединение невыпукло. Его выпуклая оболочка — фигура, похожая на беговую дорожку стадиона (stadium shape): два внешних полукруга, соединённые двумя прямыми отрезками-касательными сверху и снизу. Оболочка не просто «залатывает» пустоту между кругами точечно — она добавляет ровно ту минимальную область, которая нужна, чтобы отрезок между любыми двумя точками (в том числе между произвольными точками из разных кругов) целиком помещался внутрь.

Пример 4 (ML: линейная разделимость через непересекающиеся оболочки). В теории SVM есть точная геометрическая характеризация линейной разделимости: два класса точек линейно разделимы (то есть между ними можно провести разделяющую гиперплоскость без ошибок) тогда и только тогда, когда их выпуклые оболочки не пересекаются. Если хотя бы одна точка класса A случайно попадает внутрь выпуклой оболочки класса B (например, шумовой выброс), жёсткий (hard-margin) SVM гарантированно не найдёт разделяющую гиперплоскость — не потому что алгоритм «плохой», а потому что геометрически такой гиперплоскости попросту не существует. Это ровно та ситуация, из-за которой на практике почти всегда используют soft-margin SVM, допускающий часть ошибок ценой штрафа — но сама причина необходимости такого послабления объясняется именно через выпуклые оболочки классов.

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

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

Допустимое множество в условной оптимизации: где выпуклость встречает ML

Интуиция

Вернёмся к языку прошлого урока: задача условной оптимизации — это $\min_{x} f(x)$ при условии $x \in D$, где $D$ — допустимое множество. До сих пор $D$ обсуждалось как абстрактная область. Теперь можно сказать конкретно: в подавляющем большинстве задач машинного обучения с регуляризацией и линейными ограничениями $D$ строится из тех же самых «строительных блоков» — норм-шаров, полупространств, аффинных подпространств — а значит, по теореме о пересечении, автоматически оказывается выпуклым множеством. И именно эта выпуклость — не сила самого алгоритма обучения, а свойство геометрии задачи — превращает обучение SVM или Lasso в задачу с предсказуемым, эффективно достижимым решением.

Определение и формализация

Допустимое множество, построенное из выпуклых ограничений неравенства $g_i(x) \le 0$ (где каждая $g_i$ — выпуклая функция) и аффинных ограничений равенства $h_j(x)=0$, само выпукло:

$$D = \{x : g_i(x) \le 0,\ i=1,\dots,m;\ \ h_j(x)=0,\ j=1,\dots,p\}$$

Каждое множество уровня $\{x: g_i(x)\le0\}$ выпуклой функции $g_i$ выпукло (доказательство — урок 278), каждая гиперплоскость $\{x: h_j(x)=0\}$ выпукла (она одновременно и выпуклая, и вогнутая, как пересечение двух полупространств $h_j(x)\le0$ и $h_j(x)\ge0$), а $D$ — их пересечение, выпуклое по теореме предыдущего раздела.

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

Пример 1 (ridge / SVM: ограничение по $\ell_2$-норме). Допустимое множество весов $D = \{w \in \mathbb{R}^d : \|w\|_2 \le C\}$ — шар радиуса $C$ в пространстве весов. Он выпукл по общему доказательству из первого раздела для любой нормы, конкретизированному здесь для евклидовой. В SVM это ограничение напрямую связано с шириной отступа (margin): чем меньше допустимая норма $\|w\|$, тем шире потенциальный margin, а ограничение $\|w\|\le C$ не даёт весам расти неограниченно в погоне за идеальным разделением обучающих точек, снижая переобучение.

Пример 2 (Lasso: ограничение по $\ell_1$-норме). Допустимое множество $D = \{w \in \mathbb{R}^d: \|w\|_1 \le t\} = \{w : \sum_{k=1}^d |w_k| \le t\}$ — тоже выпуклое множество, по тому же общему доказательству (любая норма удовлетворяет неравенству треугольника и однородности, а значит любой норм-шар выпуклый). Геометрически при $d=2$ это множество — ромб (квадрат, повёрнутый на $45°$) с вершинами на осях координат в точках $(\pm t, 0)$ и $(0, \pm t)$; при большей размерности — кросс-политоп с острыми «шипами» вдоль каждой координатной оси. Именно эти острые углы на осях — геометрическая причина того, почему решение Lasso-регрессии часто оказывается разреженным (часть весов точно равна нулю): оптимум выпуклой целевой функции при ограничении $\ell_1$-шаром «предпочитает» упираться в один из острых углов оболочки, а не в гладкую точку на грани, как это происходит с гладким $\ell_2$-шаром ridge-регрессии.

Пример 3 (совмещённая допустимая область SVM). Полная допустимая область soft-margin SVM с ограничением на норму объединяет несколько типов условий сразу: норм-шар $\|w\|_2\le C$, набор из $n$ полупространств $y_i(w^Tx_i+b)\ge1-\xi_i$ и условия неотрицательности слэков $\xi_i \ge 0$ (тоже полупространства). По теореме о пересечении всё это вместе — выпуклое множество, сколько бы обучающих примеров $n$ ни было. Комбинация выпуклого допустимого множества и выпуклой целевой функции ($\frac12\|w\|^2$ плюс линейный штраф за слэки) означает: задача SVM в целом — задача выпуклой оптимизации, у неё нет «ложных» локальных минимумов, и решается она эффективно методами квадратичного программирования (урок 283) без риска застрять не там.

Пример 4 (линейное программирование как частный случай). Классическая задача ЛП $\min c^Tx$ при $Ax\le b,\ x\ge0$ — допустимое множество $D=\{x: Ax\le b, x\ge0\}$ является многогранником (пересечением полупространств из строк матрицы $A$ и условий неотрицательности), выпуклым по той же теореме. Симплекс-метод (урок 280) использует именно эту выпуклую структуру: раз $D$ — выпуклый многогранник, а линейная целевая функция достигает минимума на границе (в одной из вершин многогранника), алгоритму достаточно перебирать только вершины, а не всё бесконечное множество точек $D$ — прямое практическое следствие выпуклости.

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

import numpy as np

def is_feasible(w, A, b, tol=1e-9):
    """Проверяет w на допустимость для многогранника {x : Ax <= b}."""
    return np.all(A @ w <= b + tol)

# Пример: допустимая область {x + y <= 4, x >= 0, y >= 0}
A = np.array([[1, 1], [-1, 0], [0, -1]])
b = np.array([4, 0, 0])

print(is_feasible(np.array([1.5, 1.0]), A, b))   # True
print(is_feasible(np.array([3.0, 3.0]), A, b))   # False

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

Это и есть та самая связь, ради которой стоило разбирать все предыдущие разделы: выпуклость допустимого множества — не украшение теории, а прямая практическая гарантия. Когда ты добавляешь ограничение $\|w\|\le C$ в SVM или $\|w\|_1\le t$ в Lasso, ты не просто «штрафуешь большие веса» — ты строишь конкретное выпуклое допустимое множество, которое вместе с выпуклой функцией потерь превращает всю задачу обучения в задачу выпуклой оптимизации целиком. А для таких задач справедлив фундаментальный результат, который будет доказан в следующих уроках: любой локальный минимум является глобальным, существуют эффективные (полиномиальные по времени) алгоритмы решения, и при строго выпуклой целевой функции решение единственно. Ни одно из этих свойств не гарантировано автоматически — все они опираются на геометрию допустимого множества, разобранную в этом уроке.

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

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

Задание 1: Проверить, выпукл ли единичный квадрат $\{(x,y): 0\le x\le1,\ 0\le y\le1\}$, взяв точки $A(0,0)$ и $B(1,1)$ и проверив их середину.

Задание 2: Является ли выпуклым множество $S=\{(x,y): xy\ge1,\ x>0,\ y>0\}$ (область над гиперболой в первом квадранте)?

Задание 3: Проверить выпуклость интервала $\{x\in\mathbb{R}: |x|\le2\}$.

Задание 4: Выпукло ли объединение отрезков $[0,1]\cup[2,3]$ на прямой?

Задание 5: Является ли выпуклым множество решений системы $x+y\le5,\ x-y\le2,\ x\ge0,\ y\ge0$?

Задание 6: Является ли выпуклым множество целых чисел $\{0,1,2,\dots,10\}$, рассматриваемое как подмножество $\mathbb{R}$?

Задание 7: Найти выпуклую комбинацию точек $A(2,3)$ и $B(6,1)$ с весом $\theta=0{,}25$ при точке $A$.

Задание 8: Являются ли выпуклыми пустое множество $\varnothing$ и множество из одной точки $\{x_0\}$?

Задание 9: Проверить выпуклость шара радиуса 5 с центром в начале координат в $\mathbb{R}^3$.

Задание 10: Допустимая область для одного веса в упрощённой SVM-задаче: $\{w\in\mathbb{R}: |w|\le3\}$. Выпукла ли она?

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

Задание 11: Доказать в общем виде, что полупространство $\{x\in\mathbb{R}^n: a^Tx\le b\}$ выпукло для произвольных $a\in\mathbb{R}^n$, $b\in\mathbb{R}$.

Задание 12: Проверить выпуклость кольца $\{x\in\mathbb{R}^2: 2\le\|x\|\le5\}$, предъявив пару точек-«свидетелей».

Задание 13: Проверить выпуклость эллипса $4x^2+9y^2\le36$, используя факт о множествах уровня выпуклой квадратичной формы.

Задание 14: Описать форму пересечения шара $\|x\|\le3$ и полупространства $x_1\ge1$, доказать выпуклость.

Задание 15: Доказать невыпуклость объединения двух непересекающихся единичных шаров с центрами в $(0,0)$ и $(3,0)$.

Задание 16: Найти выпуклую оболочку точек $(0,0)$, $(4,0)$, $(0,3)$ и описать её через выпуклые комбинации.

Задание 17: Дано 5 точек: 4 образуют квадрат, пятая лежит строго внутри него. Какие точки являются вершинами выпуклой оболочки?

Задание 18: Объяснить, почему допустимая область $(w,b)$ для SVM с 4 margin-ограничениями $y_i(w\cdot x_i+b)\ge1$ выпукла, не выписывая явно форму пересечения.

Задание 19: Допустимое множество Lasso $\{w\in\mathbb{R}^2: |w_1|+|w_2|\le2\}$ — описать его форму и проверить выпуклость.

Задание 20: Сравнить форму $\ell_1$-шара и $\ell_2$-шара одного «радиуса» и объяснить связь с разреженностью решений Lasso.

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

Задание 21: Доказать теорему о выпуклости пересечения произвольного (в том числе бесконечного) семейства выпуклых множеств $\{C_i\}_{i\in I}$.

Задание 22: Привести контрпример к «объединение выпуклых множеств выпукло» и указать условие, при котором объединение всё же будет выпуклым.

Задание 23: Доказать выпуклость допустимого множества задачи линейного программирования $\{x: Ax\le b,\ x\ge0\}$, используя теорему о пересечении.

Задание 24: Доказать, что любой норм-шар $\{x:\|x\|\le r\}$ выпуклый для произвольной нормы $\|\cdot\|$ (не обязательно евклидовой), используя только аксиомы нормы.

Задание 25: Объяснить, почему в ridge-регрессии с ограничением $\|w\|_2\le C$ и в Lasso с ограничением $\|w\|_1\le t$ задача условной оптимизации гарантированно имеет глобальный минимум, достижимый без риска застревания в локальных минимумах.

Задание 26: Описать форму допустимого множества, заданного тремя условиями: $x_1^2+x_2^2\le4$, $x_1+x_2\ge1$, $x_1\le1{,}5$, и доказать его выпуклость.

Задание 27: На примере пятиконечной звезды показать, что выпуклая оболочка невыпуклой фигуры «затягивает» вогнутые участки, и как при этом меняется площадь.

Задание 28: Объяснить через теорему о непересекающихся выпуклых оболочках, почему hard-margin SVM не находит решение, если один выброс класса A попадает внутрь оболочки класса B.

Задание 29: Реализовать функцию, проверяющую, лежит ли точка в допустимом множестве, заданном как пересечение $m$ полупространств $Ax\le b$, и оценить сложность такой проверки.

import numpy as np

def is_feasible(x, A, b, tol=1e-9):
    return np.all(A @ x <= b + tol)

Задание 30: Дана задача $\min f(w)$ при $w\in D$, где $D=\{w:\|w\|_1\le t\}\cap\{w:Aw=c\}$. Доказать выпуклость $D$ и предложить практическую задачу, которую такая постановка может описывать.

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

Ошибка 1. Считают, что ограниченность (или «компактность») множества — то же самое, что выпуклость.

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

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

Как правильно: ограниченность — про размер множества, выпуклость — про отрезки между точками; кольцо и звезда ограничены, но невыпуклы, а вся плоскость $\mathbb{R}^2$ неограничена, но выпукла — эти два свойства независимы друг от друга.

Ошибка 2. Считают, что объединение выпуклых множеств всегда выпукло.

Как выглядит: распространение теоремы о пересечении на объединение по аналогии, без проверки.

Почему возникает: пересечение и объединение часто воспринимаются как «симметричные» операции, и если одна из них сохраняет свойство, кажется естественным, что и вторая тоже.

Как правильно: пересечение выпуклых множеств выпукло всегда, объединение — только в вырожденном случае вложенности одного множества в другое; в общем случае объединение двух непересекающихся выпуклых множеств («гантель») невыпукло.

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

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

Почему возникает: оба понятия называются «выпуклостью» и легко смешиваются, особенно при беглом знакомстве с темой.

Как правильно: гарантия «любой локальный минимум — глобальный» требует одновременно выпуклой целевой функции и выпуклого допустимого множества; выпуклое множество с невыпуклой функцией на нём (или наоборот) такой гарантии не даёт.

Ошибка 4. Судят о выпуклости по визуальной «кривизне» границы, считая любую изогнутую границу признаком невыпуклости.

Как выглядит: вывод «граница — гипербола, значит область невыпуклая» без проверки по определению.

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

Как правильно: область над графиком выпуклой функции (её надграфик) всегда выпукла, даже если граница сильно искривлена — пример $\{(x,y): y\ge1/x, x>0\}$ из задания 2 демонстрирует это напрямую; проверка через определение или через факт о надграфике выпуклой функции надёжнее любой визуальной оценки.

Ошибка 5. Считают дискретные (целочисленные) множества допустимых решений выпуклыми, потому что они «ограничены» и «упорядочены».

Как выглядит: рассуждение о множестве вроде $\{0,1,2,\dots,n\}$ или $\{0,1\}^n$ как о выпуклом, потому что оно выглядит «компактно и аккуратно».

Почему возникает: дискретные множества часто визуализируются как отрезки или решётки, что создаёт ложное впечатление непрерывности.

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

Ошибка 6. Путают выпуклую оболочку с самим набором исходных точек или с его контуром.

Как выглядит: представление о $\text{conv}(S)$ как о ломаной линии, соединяющей крайние точки, а не о залитой (сплошной) области.

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

Как правильно: $\text{conv}(S)$ — это множество всех выпуклых комбинаций точек $S$, то есть вся заполненная фигура, включая внутренние точки; вершины, которые выдаёт алгоритм построения оболочки, — лишь минимальный набор точек, достаточный, чтобы эту область описать.

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

• Множество $C$ выпукло, если для любых $x,y\in C$ и любого $\theta\in[0,1]$ выпуклая комбинация $\theta x+(1-\theta)y$ тоже принадлежит $C$ — то есть весь отрезок между любыми двумя точками множества лежит внутри него.

• Чтобы доказать выпуклость, нужен общий аргумент для произвольной пары точек; чтобы опровергнуть — достаточно одной конкретной пары-«свидетеля», для которой середина (или другая точка отрезка) выходит за пределы множества.

• Базовые выпуклые множества: полупространство $\{a^Tx\le b\}$, норм-шар $\{\|x-c\|\le r\}$ для любой нормы, эллипсоид, многогранник как пересечение конечного числа полупространств.

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

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

• Объединение выпуклых множеств, в отличие от пересечения, в общем случае невыпукло — логическое «И» сохраняет выпуклость, логическое «ИЛИ» её разрушает.

• Выпуклая оболочка $\text{conv}(S)$ — наименьшее выпуклое множество, содержащее $S$; эквивалентно, множество всех выпуклых комбинаций точек $S$, или пересечение всех выпуклых надмножеств $S$.

• Любой норм-шар (в том числе $\ell_1$-шар Lasso и $\ell_2$-шар ridge/SVM) выпуклый — прямое следствие неравенства треугольника и однородности нормы, работающее для любой корректной нормы.

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

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

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

Что нужно было знать до этого урока

Этот урок напрямую опирается на язык оптимизации из урока 276: понятия целевой функции $f(x)$ и допустимого множества $D$ здесь получают точное геометрическое содержание. Также используются базовые понятия линейной алгебры — векторы, нормы, скалярное произведение — и общее знакомство с точками и расстояниями на плоскости и в пространстве из блока вычислительной геометрии (урок 275), где выпуклая оболочка уже встречалась как алгоритмическая задача построения контура вокруг облака точек.

Что изучить дальше

Следующий урок 278 введёт выпуклые функции — и ты увидишь, что многие факты этого урока (например, выпуклость эллипсоида и надграфика $1/x$) на самом деле частные случаи одной общей теоремы: множество уровня выпуклой функции всегда выпукло. Урок 279 разберёт условия оптимальности Каруша–Куна–Таккера (KKT) — именно для задач с выпуклым допустимым множеством эти условия становятся не просто необходимыми, а достаточными для глобального оптимума. Уроки 280–283 (линейное программирование, симплекс-метод, двойственность, квадратичное программирование) целиком строятся на том, что их допустимые множества — многогранники и их обобщения, — а урок 284 про целочисленное программирование объяснит, почему добавление дискретности разрушает всю эту выпуклую структуру и превращает задачу из «легкой» в NP-трудную.

Где это нужно в жизни

🤖 Машинное обучение. SVM, Lasso, ridge-регрессия, elastic net — все строят допустимые множества весов как норм-шары или их пересечения с линейными ограничениями, и именно выпуклость этих множеств вместе с выпуклостью функции потерь гарантирует эффективную обучаемость без застревания в локальных минимумах.

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

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

🎮 Компьютерная графика и робототехника. Проверка столкновений (collision detection) и планирование пути робота среди препятствий заметно упрощаются, когда препятствия и свободное пространство можно приблизить выпуклыми фигурами — для выпуклых объектов существуют быстрые алгоритмы проверки пересечения, тогда как для произвольных невыпуклых форм задача становится вычислительно куда тяжелее.

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

• Термин «выпуклый» восходит к латинскому convexus — «сводчатый, куполообразный»; в русский язык, как и во многие другие, слово пришло как прямой геометрический образ свода без вмятин.

• Герман Минковский ввёл понятие выпуклого тела в 1896 году не для оптимизации, а для доказательств в теории чисел — знаменитая теорема Минковского о решётках использует объём выпуклых тел, чтобы доказывать существование целочисленных решений уравнений, и лишь спустя полвека этот аппарат стал основой оптимизации.

• Монография Р. Тиррелла Рокафеллара «Convex Analysis» 1970 года остаётся стандартным справочником по выпуклому анализу больше пятидесяти лет спустя — редкий случай, когда учебник полувековой давности всё ещё цитируется в актуальных статьях по машинному обучению.

• Условия Каруша–Куна–Таккера на самом деле были открыты дважды: в 1939 году их вывел в своей магистерской диссертации малоизвестный тогда Уильям Каруш, а независимо — в 1951 году Гарольд Кун и Алберт Такер; имя Каруша добавили к названию условий лишь спустя десятилетия, когда историки науки заново обнаружили его работу.

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

Лайфхаки

• Чтобы быстро прикинуть, выпукло ли допустимое множество реальной задачи, посмотри на структуру ограничений: если все они соединены логическим «И» (каждое неравенство или равенство должно выполняться одновременно с другими), и каждое по отдельности задаёт выпуклую область, — итоговое множество выпукло автоматически по теореме о пересечении, без дополнительных вычислений.

• Помни, что любой $\ell_p$-норм-шар при $p\ge1$ выпуклый — не нужно каждый раз передоказывать это заново для ridge ($\ell_2$), Lasso ($\ell_1$) или $\ell_\infty$-ограничений; но при $p<1$ (например, «$\ell_{0{,}5}$-регуляризация») формула перестаёт быть настоящей нормой и такое множество уже не выпукло — редкая, но реальная ловушка при экспериментах с нестандартной регуляризацией.

• Для опровержения выпуклости не пытайся анализировать всё множество целиком — ищи «подозрительное» место (дырку, острую вогнутую выемку, разрыв на части) и бери пару точек по разные стороны от него; одного удачно выбранного контрпримера достаточно для строгого доказательства невыпуклости.

• Когда объединяешь несколько типов регуляризации (например, elastic net с одновременными $\ell_1$- и $\ell_2$-штрафами), не переживай за выпуклость итоговой конструкции: сумма выпуклых штрафов и пересечение выпуклых ограничений остаются выпуклыми — комбинировать выпуклые «кирпичи» безопасно.

• Если реальное бизнес-ограничение звучит как «ИЛИ» («выбери мощность завода A ИЛИ завода B», «используй не более одного из этих двух каналов продвижения»), сразу закладывай, что задача, скорее всего, невыпуклая и комбинаторная — это сигнал присмотреться к методам смешанного целочисленного программирования (урок 284), а не пытаться решить её обычным выпуклым солвером.

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

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