Задача выпуклой оптимизации

SVM - это не «алгоритм классификации». SVM - это задача квадратичного программирования с линейными ограничениями: min 0.5||w||^2 при y_i(w*x_i+b) >= 1. Как только это поняли - kernel trick, dual problem и support vectors стали следствием одной теоремы Куна-Таккера. Весь scikit-learn SVC под капотом решает именно эту выпуклую задачу через LIBSVM (sequential minimal optimization). Это не алгоритм - это задача. Разница принципиальная.

• **SVM как QP**: scikit-learn SVC вызывает LIBSVM, который решает квадратичную программу через SMO. Kernel trick работает потому что dual problem зависит только от скалярных произведений x_i*x_j
• **LASSO и L1**: min ||Xw-y||^2 + lambda*||w||_1 - выпуклая задача с негладким ограничением. Sparsity - не магия, а следствие угловых точек L1-шара: оптимум попадает туда, где координаты нулевые
• **Markowitz portfolio**: min w^T*Sigma*w при E[r^T*w] >= R, sum(wi)=1 - классическая QP задача. Любое портфельное приложение (Betterment, Wealthfront) под капотом решает именно это

Предварительные знания

• Выпуклые функции

Стандартная форма

SVM - это не «алгоритм классификации». SVM - это задача квадратичного программирования с линейными ограничениями: min 0.5||w||^2 при y_i(w·x_i+b) >= 1. Как только это поняли - весь kernel trick, dual problem и support vectors стали следствием одной теоремы. До этого казалось магией.

**Выпуклая задача оптимизации** в стандартной форме: минимизировать выпуклую функцию f0(x) при выпуклых неравенствах gi(x) <= 0 и аффинных равенствах hj(x) = 0. Три типа объектов, три требования - и ни одного лишнего.

**Равенства должны быть аффинными (линейными).** Нелинейное равенство h(x) = 0 задаёт поверхность, которая не выпуклая. Аффинная hj(x) = aj^T*x - bj - это гиперплоскость, и только гиперплоскость. Всё остальное ломает гарантии.

**Иерархия вложенности:** LP < QP < QCQP < SOCP < SDP < Общая выпуклая. Каждый класс включает все предыдущие. LASSO - это QP плюс L1, которую через вспомогательные переменные можно свести к LP. Именно поэтому координатный спуск на LASSO сходится гарантированно.

Допустимое множество и условие Слэтера

Портфельная оптимизация Марковица - классика: min variance(w) при E[return] >= R, sum(wi) = 1, wi >= 0. Прежде чем искать оптимальный портфель, надо спросить: а существует ли хоть один портфель, удовлетворяющий всем ограничениям одновременно? Это вопрос о **допустимом множестве**.

**Допустимое множество (feasible set)** - это пересечение всех ограничений: D = {x | gi(x) <= 0, hj(x) = 0}. В выпуклой задаче D всегда выпуклое: подуровни выпуклых gi выпуклы, гиперплоскости hj = 0 выпуклы, пересечение выпуклых множеств - выпуклое. Это не теорема, которую надо доказывать каждый раз - это прямое следствие определений.

**Условие Слэтера** - ключ к двойственности: если существует строго допустимая точка (все неравенства строгие: gi(x) < 0), то сильная двойственность выполняется (d* = p*). Для Марковица это означает: если хоть один портфель строго удовлетворяет всем ограничениям - двойственные переменные (теневые цены) точно характеризуют оптимум.

Локальный = глобальный минимум

Вот почему выпуклая оптимизация - это «лёгкий» класс задач: **любой локальный минимум является глобальным**. Нет ловушек. Нет обманчивых впадин. Gradient descent на Ridge regression или LASSO не может застрять - запущенный из любой точки, он придёт к одному и тому же ответу.

Доказательство короткое. Пусть x* - локальный минимум, но не глобальный. Тогда существует y с f(y) < f(x*). По выпуклости f: f(t*x* + (1-t)*y) <= t*f(x*) + (1-t)*f(y) < f(x*). При t -> 1 точка t*x* + (1-t)*y произвольно близка к x* и имеет меньшее значение f - противоречие с локальной оптимальностью. Конец доказательства.

**Для невыпуклых задач это не работает.** Нейросети с двумя и более слоями - невыпуклые. SGD в PyTorch начинает из случайного места и движется вниз, но «дно» которое он найдёт - зависит от инициализации. Поэтому He initialization, learning rate schedules и weight decay критически важны: они помогают SGD найти хорошую (пусть не глобальную) точку.

**Условие оптимальности без ограничений**: nabla f(x*) = 0 - необходимо и достаточно. Именно поэтому Ridge regression решается аналитически: w* = (X^T*X + lambda*I)^{-1} * X^T*y - берём градиент MSE+L2, приравниваем нулю, и это сразу глобальный минимум. С ограничениями - условия KKT.

Первый взгляд на двойственность

Почему kernel trick в SVM вообще работает? Почему замена x_i на phi(x_i) и вычисление только скалярных произведений K(xi, xj) = phi(xi)^T * phi(xj) меняет всю картину? Ответ - в двойственной задаче. Dual SVM зависит не от самих векторов phi(x), а только от их скалярных произведений. Это прямое следствие структуры Лагранжиана.

У каждой задачи оптимизации есть «зеркало» - **двойственная задача**. Прямая задача минимизирует f0(x). Двойственная максимизирует нижнюю оценку через **Лагранжиан**: L(x, lambda, nu) = f0(x) + sum(lambda_i * gi(x)) + sum(nu_j * hj(x)). Множители lambda >= 0 штрафуют за нарушение неравенств.

**Слабая двойственность** (всегда, для любых задач): d* <= p*. Двойственный оптимум - гарантированная нижняя оценка прямого. **Сильная двойственность** (выпуклая задача + Слэтер): d* = p*. Зазор нулевой - и тогда KKT-условия являются одновременно необходимыми и достаточными для оптимальности.

**KKT-условия** для выпуклой задачи с сильной двойственностью - четыре пункта: 1) стационарность: nabla f0(x*) + sum(lambda_i * nabla gi(x*)) + sum(nu_j * nabla hj(x*)) = 0; 2) прямая допустимость: gi(x*) <= 0, hj(x*) = 0; 3) двойственная допустимость: lambda_i >= 0; 4) дополняющая нежёсткость: lambda_i * gi(x*) = 0 для всех i. Четвёртый пункт - вот откуда «support vectors» в SVM: только точки на границе margin имеют lambda_i > 0.

Ключевые идеи

• **Стандартная форма**: min f0(x) при gi(x) <= 0, hj(x) = 0 - f0 и gi выпуклые, hj аффинные. SVM - это QP в этой форме
• **Допустимое множество** выпуклой задачи всегда выпуклое. Слэтер-условие (строго допустимая точка) гарантирует сильную двойственность
• **Главная теорема**: локальный минимум = глобальный. Gradient descent на Ridge/LASSO/логрегрессии не застрянет - результат не зависит от старта
• **Двойственность**: d* <= p* всегда (слабая). При выпуклости + Слэтере: d* = p* (сильная). Dual SVM + kernel trick - прямое следствие

Связанные темы

Задача выпуклой оптимизации объединяет функции, множества и алгоритмы:

• Выпуклые функции — Целевая функция и ограничения должны быть выпуклыми - это тема предыдущего урока
• Выпуклые множества — Допустимое множество - выпуклое, построенное из подуровней и гиперплоскостей
• KKT и двойственность — Полное изложение условий оптимальности и их применение к SVM

Вопросы для размышления

• Дополняющая нежёсткость: lambda_i * gi(x*) = 0. Что это означает для SVM: почему только «опорные векторы» (точки на границе margin) имеют ненулевые lambda_i?
• Задача обучения нейросети - невыпуклая. Почему gradient descent с SGD/Adam всё равно работает на практике? Что заменяет гарантии выпуклости?
• Как выпуклая SDP-релаксация MAX-CUT (Goemans-Williamson 1995) даёт 0.878-аппроксимацию для NP-hard задачи? Что именно «расслабляется»?

Связанные уроки

• cvx-02 — Выпуклые функции - целевая и ограничения задачи
• cvx-04 — KKT-условия строятся прямо из стандартной формы
• ml-13-svm — SVM - квадратичная программа с линейными ограничениями
• calc-19-gradient — Условие стационарности Лагранжиана использует градиент
• ml-28-optimizers — Adam и SGD - алгоритмы решения выпуклых и невыпуклых задач
• la-09-systems