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

🎯 Зачем это нужно?

Представь Instagram, который показывает тебе идеальную ленту 📱. Как алгоритм выбирает посты из миллионов вариантов? Или Tesla, которая планирует маршрут с минимальным расходом батареи ⚡. В основе таких задач лежит оптимизация на выпуклых множествах.

💼 В индустрии:

• Google Search: PageRank оптимизируется на симплексе вероятностей
• Netflix: рекомендации через матричную факторизацию на выпуклых множествах
• Uber: маршрутизация водителей - задача линейного программирования
• ChatGPT: обучение нейросетей = оптимизация на выпуклых функциях потерь

📚 История вопроса

В 1947 году Данциг придумал симплекс-метод для планирования авиаперевозок в армии США ✈️. Оказалось, что многие “сложные” задачи становятся простыми, если искать решение в правильно выбранном выпуклом множестве.

Сегодня 90% задач машинного обучения решаются именно благодаря выпуклой геометрии!

💡 Интуиция

Выпуклое множество = множество без “вмятин” и “дырок” 🥣

Простая проверка: возьми любые две точки внутри множества и соедини их отрезком. Если весь отрезок лежит внутри множества - оно выпуклое!

🟢 Выпуклые: круг, квадрат, треугольник, полуплоскость 🔴 Невыпуклые: звезда, буква “С”, пончик, две отдельные точки

[МЕДИА: image_01] Описание: Сравнение выпуклых и невыпуклых фигур с отрезками между точками Промпт: “educational illustration showing convex vs non-convex shapes, line segments between points, green checkmarks for convex shapes (circle, square, triangle), red X marks for non-convex shapes (star, crescent, donut), clean mathematical style, white background”

📐 Формальное определение

Определение: Множество S ⊆ ℝⁿ называется выпуклым, если для любых двух точек x, y ∈ S и любого λ ∈ [0, 1] выполняется:

λx + (1-λ)y ∈ S

Это выпуклая комбинация точек x и y.

Ключевые концепции:

🔸 Выпуклая комбинация: ∑λᵢxᵢ, где ∑λᵢ = 1, λᵢ ≥ 0 🔸 Выпуклая оболочка: conv(S) = наименьшее выпуклое множество, содержащее S 🔸 Крайние точки: точки, не лежащие внутри отрезков между другими точками множества

🔍 Примеры с разбором

Пример 1: Проверяем выпуклость

Множество S = {(x,y) : x² + y² ≤ 1} (единичный круг)

Проверка: Возьмем x = (1,0), y = (0,1) ∈ S Для λ = 0.5: z = 0.5(1,0) + 0.5(0,1) = (0.5, 0.5) ||z||² = 0.5² + 0.5² = 0.5 < 1 ✅

Аналогично для любых точек круга и любого λ ∈ [0,1].

Пример 2: SVM и разделяющая гиперплоскость

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

Множество возможных решений: S = {w : ||w|| ≤ C} - выпуклое! Поэтому SVM всегда находит глобальный оптимум 🎯

[МЕДИА: image_02] Описание: Визуализация SVM с разделяющей гиперплоскостью и выпуклым множеством решений Промпт: “machine learning visualization showing SVM hyperplane separation, data points in two classes, margin boundaries, convex feasible region for weights, modern ML illustration style, blue and orange data points”

Пример 3: Портфельная оптимизация

Инвестор распределяет капитал между n активами. Ограничения: xᵢ ≥ 0 (нельзя “занимать”), ∑xᵢ = 1 (весь капитал)

Это симплекс - классическое выпуклое множество! 📊 Поэтому задача поиска оптимального портфеля решается эффективно.

🎮 Практика

Базовый уровень 🟢

1. Какие из множеств выпуклы? a) {(x,y) : x ≥ 0, y ≥ 0} b) {(x,y) : xy ≥ 1, x > 0, y > 0}
c) {(x,y) : |x| + |y| ≤ 1} d) {(x,y) : max(|x|, |y|) ≤ 1}

2. Найди выпуклую комбинацию точек A(1,2) и B(3,0) с λ = 0.3

3. Докажи, что пересечение выпуклых множеств выпукло

4. Верно ли, что объединение выпуклых множеств выпукло?

Продвинутый уровень 🟡

5. Найди выпуклую оболочку точек: (0,0), (1,0), (0,1), (1,1)

6. Множество S = {x ∈ ℝⁿ : Ax ≤ b} выпукло для любой матрицы A. Почему?

7. В задаче линейного программирования min{cᵀx : Ax ≤ b, x ≥ 0} почему оптимум достигается в крайней точке?

8. Докажи, что функция f(x) = ||x||₂ выпукла, используя неравенство треугольника

Челлендж 🔴

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

10. Как изменится выпуклая оболочка точек {(±1,±1)} при добавлении точки (0,2)?

11. В нейросети функция потерь L(w) выпукла по весам w. Объясни, почему градиентный спуск находит глобальный минимум

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

❌ Ошибка: “Если множество ограничено, то оно выпуклое” ✅ Правильно: Выпуклость не зависит от ограниченности (пример: вся плоскость ℝ²) 💡 Почему: Выпуклость - про “отрезки”, а не про размер

❌ Ошибка: “Объединение выпуклых множеств выпукло”
✅ Правильно: Пересечение выпуклых множеств выпукло, объединение - НЕТ 💡 Почему: Два круга через отрезок дают “гантелю” - невыпуклую фигуру

❌ Ошибка: “В выпуклом множестве все локальные минимумы - глобальные” ✅ Правильно: Это верно для выпуклых функций на выпуклых множествах
💡 Почему: Нужны ОБА условия: и функция, и множество выпуклые

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

✅ Выпуклое множество = “без вмятин”, любой отрезок между точками лежит внутри ✅ Выпуклая комбинация: λx + (1-λ)y, где λ ∈ [0,1] ✅ Применения: ML (SVM, нейросети), оптимизация, экономика, компьютерная графика

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

Назад: Линейные неравенства (урок 276) задают выпуклые множества Вперед: Выпуклые функции, методы оптимизации, двойственность в линейном программировании Связи: Градиентный спуск, симплекс-метод, теория игр, вычислительная геометрия