Квадратичное программирование: как найти лучшее решение с ограничениями

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

Представь, что ты настраиваешь рекламную кампанию в TikTok 📱. У тебя есть бюджет $10,000, и ты хочешь максимизировать охват, но при этом:

• Не потратить больше $3,000 на видеорекламу
• Получить минимум 100,000 показов
• Сохранить баланс между разными возрастными группами

Или Google Photos автоматически улучшает качество твоих селфи - алгоритм минимизирует “шум” в пикселях, но с ограничениями на яркость и контраст 📸.

А еще - это основа машинного обучения! SVM (которые используются в распознавании лиц Instagram) решают именно задачи квадратичного программирования 🤖.

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

В 1950-х годах Гарри Марковиц работал в RAND Corporation и пытался понять, как банки должны распределять деньги между разными акциями 💰. Проблема: нужно максимизировать прибыль, но минимизировать риск.

Он понял, что риск растет квадратично (если вложить в 2 раза больше в рискованную акцию, риск вырастет в 4 раза!), а ограничения линейные (общий бюджет фиксирован). Так родилось квадратичное программирование - за что Марковиц получил Нобелевскую премию в 1990! 🏆

💡 Интуиция

Квадратичное программирование - это как игра в дартс с изогнутой мишенью 🎯:

Обычная оптимизация: Найди минимум функции f(x) = x² - крутишься вокруг одной точки.

Квадратичное программирование: Найди минимум функции f(x) = x² при условии x ≥ 2. Теперь оптимальная точка может “прилипнуть” к границе!

[МЕДИА: image_01] Описание: 3D график квадратичной функции с плоскостями ограничений, показывающий как оптимум “скользит” по границе Промпт: “3D mathematical visualization of quadratic function with linear constraints, bowl-shaped surface intersected by constraint planes, optimal point highlighted on boundary, modern educational style, blue and orange gradients”

Главная интуиция: квадратичная функция всегда имеет форму “миски” (выпуклая), поэтому у задачи ВСЕГДА есть единственное глобальное решение. Линейные ограничения - это “стенки”, которые могут заставить оптимум “прилипнуть” к границе.

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

Стандартная задача квадратичного программирования:

minimize ½xᵀQx + cᵀx subject to Ax ≤ b x ≥ 0

Где:

• Q - симметричная положительно определенная матрица (n×n)
• c - вектор коэффициентов (n×1)
• A - матрица ограничений (m×n)
• b - вектор правых частей (m×1)
• x - вектор переменных (n×1)

Условия оптимальности (KKT):

1. ∇f(x*) + Aᵀλ* = 0 (стационарность)
2. Ax* ≤ b (допустимость прямая)
3. λ* ≥ 0 (допустимость двойственная)
4. λᵢ*(Aᵢx* - bᵢ) = 0 (дополняющая нежесткость)

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

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

Допустим, у тебя есть $1000 для инвестиций в два актива 💼:

• Bitcoin: ожидаемая доходность 20%, волатильность 40%
• S&P 500: ожидаемая доходность 10%, волатильность 15%
• Корреляция между активами: 0.3

Нужно минимизировать риск при доходности минимум 15%.

Математическая модель:

Variables: x₁ (доля в Bitcoin), x₂ (доля в S&P)

minimize   ½[x₁ x₂][0.16  0.018][x₁]  = 0.08x₁² + 0.0125x₂² + 0.018x₁x₂
                     [0.018 0.0225][x₂]

subject to 0.20x₁ + 0.10x₂ ≥ 0.15    (минимальная доходность)
           x₁ + x₂ = 1                 (весь бюджет инвестирован)  
           x₁, x₂ ≥ 0                  (нельзя шортить)

[МЕДИА: image_02] Описание: Эффективная граница Марковица для двух активов с выделенной оптимальной точкой Промпт: “portfolio optimization visualization showing efficient frontier curve, risk-return plot with constraint lines, optimal portfolio point highlighted, financial charts style, professional blue color scheme”

Пример 2: SVM для классификации

Задача: разделить фотографии котов и собак 🐱🐶

У нас есть обучающие данные: (xᵢ, yᵢ), где yᵢ ∈ {-1, +1}.

SVM решает задачу:

minimize   ½||w||²
subject to yᵢ(wᵀxᵢ + b) ≥ 1,  i = 1,...,n

Это квадратичная функция (минимизируем ||w||²) с линейными ограничениями!

Решение через двойственную задачу:

maximize   ∑αᵢ - ½∑∑αᵢαⱼyᵢyⱼ(xᵢᵀxⱼ)
subject to ∑αᵢyᵢ = 0
           αᵢ ≥ 0

🎮 Практика

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

Задача 1: Netflix оптимизирует рекомендации minimize f(x₁,x₂) = x₁² + x₂² - 4x₁ - 6x₂ subject to x₁ + 2x₂ ≤ 4, x₁,x₂ ≥ 0

Задача 2: Оптимизация рекламного бюджета У тебя $100 на рекламу в Instagram и YouTube. Instagram дает доходность x₁², YouTube - x₂², но суммарные затраты не должны превышать бюджет.

Задача 3: Простая портфельная задача
Два актива с доходностями 8% и 12%, найди оптимальное распределение при минимальном риске.

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

Задача 4: SVM с мягким зазором Реши двойственную задачу SVM для точек: (1,1,+1), (2,2,+1), (2,1,-1), (3,2,-1)

Задача 5: Многомерная портфельная оптимизация 3 актива, заданы матрица ковариации и вектор доходностей, найди портфель минимального риска при доходности 10%.

Задача 6: Задача о диете с квадратичными штрафами Минимизируй “недовольство” от отклонения калорий от нормы: (calories - 2000)²

Челлендж 🔴

Задача 7: Оптимизация нейросети Минимизируй функцию потерь ½∑(wᵀxᵢ - yᵢ)² + λ||w||² (Ridge регрессия)

Задача 8: Задача управления Минимизируй ∫₀ᵀ (u²(t) + x²(t))dt при динамике ẋ = Ax + Bu

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

❌ Ошибка: “Q должна быть положительно определенной” ✅ Правильно: Достаточно положительной полуопределенности для выпуклости 💡 Почему: При полуопределенности решение может быть не единственным, но задача остается выпуклой

❌ Ошибка: Использование KKT условий для невыпуклых задач ✅ Правильно: KKT - только необходимые условия для общего случая, достаточные для выпуклых 💡 Почему: В невыпуклых задачах KKT точка может быть седловой

❌ Ошибка: Игнорирование условий дополняющей нежесткости ✅ Правильно: λᵢ(gᵢ(x)) = 0 означает: активное ограничение ИЛИ λᵢ = 0 💡 Почему: Это условие определяет, какие ограничения “работают” в оптимуме

❌ Ошибка: Путать квадратичное программирование с квадратичными уравнениями ✅ Правильно: QP - это оптимизация квадратичной функции при линейных ограничениях 💡 Почему: Принципиально разные математические объекты

❌ Ошибка: Использовать градиентный спуск напрямую ✅ Правильно: Специализированные методы (активных множеств, внутренней точки) работают лучше 💡 Почему: Они учитывают структуру задачи и ограничения

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

✅ QP = минимизация квадратичной функции при линейных ограничениях ✅ Всегда имеет глобальный минимум (если задача допустима) ✅ Основа для SVM, портфельной оптимизации, управления ✅ KKT условия дают полное описание оптимального решения

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

Откуда пришли: Линейное программирование (282) + выпуклая оптимизация Куда идем: Семидефинитное программирование, методы внутренней точки
Применения: SVM, портфельная теория, MPC в робототехнике, компьютерная графика (деформации), обработка сигналов