Выпуклый анализ и оптимизация

Определения

Геометрический тест

— нарисуйте фигуру. Если можно найти две точки внутри неё, соединённые отрезком, частично выходящим за границу — фигура невыпуклая. Буква «C» — невыпуклая. Круг, квадрат, треугольник — выпуклые.

Гиперплоскость

— {x ∈ ℝⁿ : aᵀx = b}, где a ≠ 0 — фиксированный вектор, b — число. Это n-1-мерная «плоскость» в пространстве. Пример в ℝ²: прямая 2x₁ + 3x₂ = 6. Любые две точки на прямой соединены отрезком, лежащим на прямой — выпуклость очевидна.

Полупространство

— {x : aᵀx ≤ b} — одна «сторона» от гиперплоскости. В ℝ² это полуплоскость по одну сторону прямой.

Шар

— {x : ‖x − xc‖ ≤ r} — все точки на расстоянии не более r от центра xc. Выпуклость: если две точки лежат в шаре (расстояние до xc ≤ r), то любая точка между ними тоже в шаре — это следует из неравенства треугольника.

Эллипсоид

— {x : (x−xc)ᵀP⁻¹(x−xc) ≤ 1}, где P — положительно определённая матрица. Это «вытянутый шар» по разным осям. Активно используется в теории управления для описания допустимых областей состояний.

Конус второго порядка (SOCP)

— {(x, t) : ‖x‖ ≤ t, t ≥ 0} — «мороженое» в пространстве. Поверхность конуса — это точки с ‖x‖ = t, внутренность — с ‖x‖ < t.

Множество положительно полуопределённых матриц

— Sⁿ₊ = {X ∈ ℝⁿˣⁿ : X = Xᵀ, uᵀXu ≥ 0 для всех u}. Это выпуклый конус в пространстве симметричных матриц.

Пересечение

— если C₁ и C₂ выпуклые, то C₁ ∩ C₂ — тоже выпуклое. Доказательство: если x, y ∈ C₁ ∩ C₂, то x, y ∈ C₁ → отрезок xy ⊆ C₁, и x, y ∈ C₂ → отрезок xy ⊆ C₂, значит отрезок xy ⊆ C₁ ∩ C₂. Следствие: многогранник (политоп) — пересечение конечного числа пол...

Образ при линейном преобразовании

— f(C) = {Ax + b : x ∈ C} — выпуклое, если C выпуклое. Аффинные преобразования «сохраняют» выпуклость.

Прообраз

— если f: ℝⁿ → ℝᵐ аффинная (f(x) = Ax+b) и D — выпуклое, то f⁻¹(D) = {x : f(x) ∈ D} — выпуклое.

Сумма Минковского

— C₁ + C₂ = {x + y : x ∈ C₁, y ∈ C₂} — выпуклая, если C₁, C₂ выпуклые.

Теорема

— если C₁ и C₂ — непустые выпуклые множества с пустым пересечением (C₁ ∩ C₂ = ∅), то существует вектор a ≠ 0 и число b такие, что:

Смысл

— гиперплоскость {x : aᵀx = b} «разделяет» два множества. Это геометрически очевидно в ℝ²: два непересекающихся выпуклых множества на плоскости всегда можно разделить прямой.

Опорная гиперплоскость

— в граничной точке x₀ выпуклого C существует вектор g ≠ 0 такой, что gᵀ(x − x₀) ≤ 0 для всех x ∈ C. Это «касательная» гиперплоскость к C в точке x₀, лежащая «снаружи».

Существование и единственность

— такая точка всегда существует и единственна. Единственность — следствие строгой выпуклости функции ‖y − x‖².

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

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

Что это означает словами? Возьмите любые две точки множества. Соедините их отрезком. Если весь этот отрезок целиком лежит внутри множества — оно выпуклое. Параметр θ «пробегает» от 0 до 1, описывая все точки между x и y: при θ=1 получаем x, при θ=0 — y, при θ=0.5 — середину отрезка.

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

Определения

Геометрический смысл

— рассмотрим две точки на графике функции: A = (x, f(x)) и B = (y, f(y)). Правая часть λf(x) + (1−λ)f(y) — это точка на хорде AB, соответствующая параметру λ. Левая часть f(λx + (1−λ)y) — это значение функции в той же точке по горизонтали. Выпуклост...

Вогнутая функция

— f вогнутая, если −f выпуклая. Неравенство «переворачивается».

Смысл

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

Важное следствие

— если ∇f(x*) = 0, то x* — глобальный минимум! Действительно, f(y) ≥ f(x*) + 0 = f(x*) для всех y.

Теорема

— если f выпуклая, то все подуровневые множества C_α выпуклые.

Ключевая теорема

— f выпуклая ⟺ epi(f) — выпуклое множество в ℝⁿ⁺¹.

Задача

— проверить выпуклость f(x₁, x₂) = x₁² + 2x₁x₂ + 3x₂² с помощью критерия второго порядка.

Шаг 1

— Вычислим частные производные второго порядка.

Шаг 2

— Матрица Гессе (не зависит от x в этом примере):

Шаг 3

— Проверяем положительную полуопределённость. Критерий Сильвестра:

Шаг 4

— Находим минимум. ∇f(x) = 0: 2x₁ + 2x₂ = 0, 2x₁ + 6x₂ = 0. Из первого уравнения: x₁ = −x₂. Подставляем во второе: −2x₂ + 6x₂ = 0 → x₂ = 0, x₁ = 0. Минимум в точке (0, 0), f(0, 0) = 0.

Регрессия

— среднеквадратичная ошибка f(w) = ‖Xw − y‖² — выпуклая (критерий: ∇²f = 2XᵀX ≽ 0). Поэтому градиентный спуск всегда находит глобальный минимум.

Логистическая регрессия

— функция потерь − Σ [yᵢ log σ(wᵀxᵢ) + (1−yᵢ) log(1 − σ(wᵀxᵢ))] — выпуклая по w. Гарантия сходимости любого метода первого порядка.

Финансы

— функция среднеквадратичного риска портфеля wᵀΣw (Σ — ковариационная матрица, ≽ 0) — выпуклая. Минимизация риска — выпуклая задача с уникальным решением.

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

Функция f: ℝⁿ → ℝ (или f: dom(f) → ℝ, где dom(f) — выпуклое множество) называется выпуклой, если для любых x, y ∈ dom(f) и любого λ ∈ [0,1]:

Геометрический смысл: рассмотрим две точки на графике функции: A = (x, f(x)) и B = (y, f(y)). Правая часть λf(x) + (1−λ)f(y) — это точка на хорде AB, соответствующая параметру λ. Левая часть f(λx + (1−λ)y) — это значение функции в той же точке по горизонтали. Выпуклость означает: график функции л...

Если выполняется строгое неравенство (< вместо ≤) при x ≠ y и λ ∈ (0,1) — функция строго выпуклая. У строго выпуклой функции минимум единственен.

Определения

Интерпретация

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

Теорема

— точка x* является глобальным минимумом выпуклой функции f тогда и только тогда, когда:

Смысл

— нуль должен быть субградиентом. Если f дифференцируема, это стандартное условие ∇f(x*) = 0. Для недифференцируемых функций: 0 должен лежать в «веере» субградиентов.

Пример

— для f(x) = |x|: 0 ∈ ∂|x*| ⟺ x* = 0 (потому что только при x = 0 субдифференциал содержит 0).

Сумма

— ∂(f + g)(x) ⊇ ∂f(x) + ∂g(x). При условиях регулярности (например, одна из функций непрерывна): выполняется равенство.

Аффинная замена аргумента

— если h(x) = f(Ax + b), то ∂h(x) = Aᵀ ∂f(Ax + b).

Задача

— min_{x ∈ ℝⁿ} F(x) = (1/2)‖Ax − b‖² + λ‖x‖₁

Условие оптимальности

— 0 ∈ ∂F(x*) = ∂[(1/2)‖Ax−b‖²](x*) + λ ∂‖x*‖₁

Отбор признаков

— LASSO-регрессия с L1-штрафом автоматически обнуляет ненужные коэффициенты. Это «автоматический отбор переменных». В медицинских данных с тысячами генов LASSO выбирает несколько десятков наиболее значимых.

Компрессированное восстановление сигналов

— МРТ-сканер делает в 10 раз меньше измерений, используя L1-минимизацию для восстановления разреженного изображения. Субдифференциал L1-нормы — ключ к пониманию, почему это работает.

Многие важные выпуклые функции не имеют градиента в каждой точке. Абсолютное значение |x| не дифференцируемо в нуле. L1-норма ‖x‖₁ не дифференцируема, когда хотя бы одна компонента обращается в нуль. Максимум из нескольких функций не дифференцируем на множестве переключения. Если мы хотим решать ...

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

Почему? При x = 0 нужно найти все g такие, что |y| ≥ |0| + g(y−0) = gy для всех y. Это выполняется при |y| ≥ gy для всех y, что означает g ∈ [−1, 1].

где I(x) = {i : fᵢ(x) = max_j fⱼ(x)} — множество «активных» функций, conv — выпуклая оболочка.

Определения

Лагранжиан

— «смягчаем» ограничения, перемещая их в целевую функцию со штрафами λᵢ и νⱼ:

Физический смысл λᵢ

— цена нарушения i-го ограничения. Если gᵢ(x) > 0 (нарушение), за это платим λᵢ gᵢ(x) > 0. При λᵢ = 0 — штрафа нет. При больших λᵢ — нарушение «дорогое».

Двойственная функция

— g(λ, ν) = inf_{x} L(x, λ, ν) — минимум лагранжиана по x при фиксированных множителях.

Теорема (слабая двойственность)

— для любых допустимых λ ≥ 0 и ν выполняется:

Доказательство

— пусть x* — оптимальное допустимое решение примальной задачи. Тогда:

Следствие

— максимизируя g(λ, ν) по λ ≥ 0, ν, получаем наилучшую нижнюю оценку p*.

Двойственная задача

— max_{λ ≥ 0, ν} g(λ, ν).

Теорема Слэйтера

— если задача выпуклая (f, gᵢ — выпуклые, hⱼ — аффинные) и существует строго допустимая точка x̃ такая, что gᵢ(x̃) < 0 строго для всех i (и hⱼ(x̃) = 0), то:

1. Примальная допустимость

— gᵢ(x*) ≤ 0, hⱼ(x*) = 0 (x* — допустимо)

2. Двойственная допустимость

— λᵢ* ≥ 0

3. Дополняющая нежёсткость

— λᵢ* gᵢ(x*) = 0 для всех i

4. Стационарность

— ∇f(x*) + Σᵢ λᵢ* ∇gᵢ(x*) + Σⱼ νⱼ* ∇hⱼ(x*) = 0

Интерпретация условия 3

— либо ограничение «активно» (gᵢ(x*) = 0), либо его цена нулевая (λᵢ* = 0). Нельзя одновременно «неактивное» ограничение иметь ненулевую цену.

Задача

— min (x₁ − 1)² + (x₂ − 1)² при x₁ + x₂ ≤ 1, x₁ ≥ 0, x₂ ≥ 0.

Условие Слэйтера

— x̃ = (0.1, 0.1) строго допустима: 0.1 + 0.1 = 0.2 < 1, 0.1 > 0. Сильная двойственность выполнена.

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

Лагранжиан: «смягчаем» ограничения, перемещая их в целевую функцию со штрафами λᵢ и νⱼ:

где λᵢ ≥ 0 — «двойственные переменные» (множители Лагранжа) для неравенств, νⱼ — для уравнений (могут быть любого знака).

Физический смысл λᵢ: цена нарушения i-го ограничения. Если gᵢ(x) > 0 (нарушение), за это платим λᵢ gᵢ(x) > 0. При λᵢ = 0 — штрафа нет. При больших λᵢ — нарушение «дорогое».

Определения

Ключевое свойство

— f* — всегда выпуклая функция, даже если исходная f — невыпуклая! (Как супремум аффинных функций по y.)

Биполярная теорема

— если f — замкнутая выпуклая функция, то f = f (двойная сопряжённая совпадает с исходной). Для невыпуклых f: f = cl(conv(f)) — замыкание выпуклой оболочки.

Вычисление

— если |yᵢ| > 1 для некоторого i, берём xᵢ → ±∞ → супремум = +∞. Если |yᵢ| ≤ 1 для всех i, то yᵀx ≤ ‖y‖_∞ ‖x‖₁ ≤ ‖x‖₁ → yᵀx − ‖x‖₁ ≤ 0, максимум = 0 (при x = 0).

Задача LASSO

— min_x {(1/2)‖Ax−b‖² + λ‖x‖₁}

Задача

— найти сопряжённую для f(x) = −log x (x > 0).

Шаг 1

— Производная по x: y + 1/x = 0 → x* = −1/y (только при y < 0).

Шаг 2

— При y ≥ 0: yx + log x → +∞ при x → +∞ (для y > 0) или x → +∞ при y = 0 → супремум = +∞.

Шаг 3

— При y < 0: f*(y) = y·(−1/y) + log(−1/y) = −1 + log(−1/y) = −1 − log(−y).

Результат

— f*(y) = −1 − log(−y) при y < 0, +∞ при y ≥ 0.

Двойственность в оптимизации

— сопряжённая функция автоматически порождает двойственную задачу. Это используется в расчёте оптимальных портфелей (двойственность задачи Марковица), SVM (ядровой трюк через двойственность), и в методе ADMM.

Прокс-оператор через сопряжённую

— по теореме Моро, prox_{τf}(x) + τ prox_{f*/τ}(x/τ) = x. Если вычислить prox одной функции трудно, вычисляем прокс сопряжённой.

Представьте, что вы хотите охарактеризовать выпуклую функцию не через её значения в точках, а через поддерживающие её гиперплоскости. Каждая касательная линия к выпуклой функции задаётся своим наклоном y и «точкой перехвата». Сопряжённая функция f*(y) фиксирует это «пересечение» для гиперплоскост...

Ключевое свойство: f* — всегда выпуклая функция, даже если исходная f — невыпуклая! (Как супремум аффинных функций по y.)

Биполярная теорема: если f — замкнутая выпуклая функция, то f = f (двойная сопряжённая совпадает с исходной). Для невыпуклых f: f = cl(conv(f)) — замыкание выпуклой оболочки.

Вычисление: если |yᵢ| > 1 для некоторого i, берём xᵢ → ±∞ → супремум = +∞. Если |yᵢ| ≤ 1 для всех i, то yᵀx ≤ ‖y‖_∞ ‖x‖₁ ≤ ‖x‖₁ → yᵀx − ‖x‖₁ ≤ 0, максимум = 0 (при x = 0).

Определения

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

— min cᵀx при Ax ≤ b, x ≥ 0.

Геометрия

— область допустимых решений — выпуклый многогранник (политоп). Линейная целевая функция достигает минимума в вершине многогранника. Симплекс-метод (Данциг, 1947) «ходит» по вершинам, пока не найдёт оптимальную. Метод внутренней точки — движется чер...

Двойственность ЛП

— примальная задача min cᵀx при Ax ≥ b, x ≥ 0 имеет двойственную max bᵀy при Aᵀy ≤ c, y ≥ 0. Сильная двойственность выполнена всегда (при допустимости обеих задач).

Пример — задача о диете

— минимизировать стоимость набора продуктов при условии получения достаточного количества питательных веществ. Это классическая ЛП-задача, решённая ещё в 1940-х годах.

Ограничение SOCP

— ‖Aᵢx + bᵢ‖ ≤ cᵢᵀx + dᵢ — норма вектора ограничена линейной функцией x.

Включает ЛП и КП

— ЛП — частный случай (Aᵢ = 0, вырождается в линейное). КП с P ≽ 0 допускает SOCP-формулировку.

Задача SDP

— min_{X} tr(CX) при tr(AᵢX) = bᵢ, i=1,...,m, X ≽ 0

Переменная

— матрица X! Это обобщение ЛП (переменная — вектор x) на матричный случай.

Задача

— граф G = (V, E). Разбить вершины на два множества S и V∖S, максимизируя число рёбер между ними.

ЦЛП-формулировка

— xᵢ ∈ {−1, +1}. Разрез: (1/4)Σ_{(i,j)∈E} (1 − xᵢxⱼ). NP-трудная.

SDP-релаксация (Гёманс-Вильямсон, 1995)

— заменяем xᵢ ∈ {±1} на векторы vᵢ ∈ ℝⁿ с ‖vᵢ‖ = 1. Произведение xᵢxⱼ → скалярное произведение vᵢᵀvⱼ. Матрица Yᵢⱼ = vᵢᵀvⱼ ≽ 0!

Решение

— это SDP! Рандомизированное округление (случайная гиперплоскость) даёт 0.878-аппроксимацию MAX-CUT.

Что это означает

— алгоритм гарантированно находит разрез, составляющий не менее 87.8% от оптимального. Это лучший известный полиномиальный алгоритм.

Формулы

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

Здесь c ∈ ℝⁿ — вектор коэффициентов цели, A ∈ ℝ^{m×n} — матрица ограничений, b ∈ ℝᵐ — правые части.

Геометрия: область допустимых решений — выпуклый многогранник (политоп). Линейная целевая функция достигает минимума в вершине многогранника. Симплекс-метод (Данциг, 1947) «ходит» по вершинам, пока не найдёт оптимальную. Метод внутренней точки — движется через внутренность.

Двойственность ЛП: примальная задача min cᵀx при Ax ≥ b, x ≥ 0 имеет двойственную max bᵀy при Aᵀy ≤ c, y ≥ 0. Сильная двойственность выполнена всегда (при допустимости обеих задач).

Определения

Класс L-гладких функций

— f называется L-гладкой, если ‖∇f(x) − ∇f(y)‖ ≤ L‖x − y‖ для всех x, y. Константа L — «степень гладкости» (наибольшее собственное значение матрицы Гессе).

Теорема о сходимости

— для выпуклой L-гладкой f с шагом α = 1/L:

Скорость сходимости

— O(1/k²) — вдвое быстрее градиентного спуска! Это теоретически оптимально для методов первого порядка (нижняя оценка Нестерова).

Физический смысл

— «инерция» не даёт застрять в «ущельях» — местах с большим κ. Шарик, катящийся с инерцией, «перелетает» узкое дно ущелья и останавливается ближе к минимуму.

Задача

— минимизировать f(x) = (1/2)(x₁² + 100x₂²) — вытянутая парабола с κ = 100.

Нестеров

— сходится за ~20√κ ≈ 200 итераций вместо 1000. Это 5-кратное ускорение при κ = 100.

Скорость

— O(1/√k) для выпуклых, O(1/k) для сильно выпуклых (при правильном затухании шага).

Адаптивные методы

— Adam, RMSProp, AdaGrad — масштабируют шаг покоординатно. В глубоком обучении Adam почти всегда лучше SGD с фиксированным шагом.

Методы второго порядка (метод Ньютона) очень быстрые, но требуют вычисления и обращения матрицы Гессе — O(n³) операций за шаг. При n = 10⁶ параметров (нейросеть среднего размера) это просто невозможно. Методы первого порядка используют только градиент — O(n) операций. Они медленнее на итерацию, н...

Здесь α > 0 — размер шага (learning rate). При слишком большом α — алгоритм расходится. При слишком малом — очень медленная сходимость.

Класс L-гладких функций: f называется L-гладкой, если ‖∇f(x) − ∇f(y)‖ ≤ L‖x − y‖ для всех x, y. Константа L — «степень гладкости» (наибольшее собственное значение матрицы Гессе).

Это скорость O(1/k): чтобы уменьшить ошибку вдвое, нужно удвоить число итераций.

Определения

Определение

— prox_{τf}(x) = argmin_{y} {f(y) + (1/2τ)‖y − x‖²}

Задача

— min F(x) = (1/2)‖Ax − b‖² + λ‖x‖₁

Численный пример

— A — матрица 50×100, x* разреженный (5 ненулевых компонент). FISTA с λ = 0.1 достигает точности 10⁻⁶ за ~200 итераций. Без ускорения (ISTA) — за ~2000 итераций.

Почему ADMM мощнее

— расщепляет задачу на два подзадачи — по x и по z — решаемые по отдельности. Если обе подзадачи имеют удобные прокс-операторы, весь алгоритм очень эффективен.

Распределённая оптимизация

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

Обработка изображений

— Total Variation (TV) деноизинг: min (1/2)‖u − f‖² + λTV(u). TV норма — негладкая, но имеет удобный прокс. FISTA и ADMM — стандартные методы.

Формулы

Задача LASSO: min (1/2)‖Ax−b‖² + λ‖x‖₁. Первый член — гладкий (можно дифференцировать), второй — нет (|x|₁ недифференцируема в нуле). Применить градиентный спуск нельзя напрямую. Субградиентный метод — слишком медленный (O(1/√k)). Прокс-алгоритмы решают эту проблему элегантно: «расщепляют» функци...

Это «мягкий шаг в сторону минимума f». При τ → 0: prox ≈ x (не двигаемся). При τ → ∞: prox → argmin f (идём в минимум).

1. f(x) = ‖x‖₁: prox_{τf}(x) = sign(x) · max(|x| − τ, 0) — мягкое пороговое (soft thresholding)

2. f(x) = δ_C(x) — индикатор выпуклого C: prox_{δ_C}(x) = P_C(x) — проекция на C

Определения

Смысл

— когда gᵢ(x) → 0 (приближаемся к границе ограничения), −gᵢ(x) → 0⁺ → log → −∞ → φ(x) → +∞. Барьер «отталкивает» от границы.

Барьерная задача

— min f(x) + (1/t) φ(x)

Зазор двойственности на центральном пути

— f(x*(t)) − d* = m/t, где m — число ограничений. Точность ε достигается при t = m/ε.

Сложность

— O(√m) итераций «внешнего» цикла, каждая — один шаг Ньютона O(n³) (инвертирование матрицы). Итого: O(√m · n³).

Задача

— min cᵀx при Ax = b, x ≥ 0 (стандартная форма ЛП).

Условия ККТ

— c − (1/t)X⁻¹e + Aᵀλ = 0, Ax = b. Здесь X = diag(x).

Шаг Ньютона

— Решаем линейную систему:

Пример

— транспортная задача 100×100 (10000 переменных): МВТ решает за ~50 итераций (~50 систем линейных уравнений), симплекс-метод — за ~10000 итераций по вершинам.

Задача с ограничениями: min f(x) при gᵢ(x) ≤ 0. Один из подходов — «забыть» про ограничения, но добавить большой штраф за их нарушение. Логарифмический барьер делает это изящно: он уходит в +∞ при приближении x к границе допустимого множества. Метод внутренней точки (МВТ) систематически используе...

Смысл: когда gᵢ(x) → 0 (приближаемся к границе ограничения), −gᵢ(x) → 0⁺ → log → −∞ → φ(x) → +∞. Барьер «отталкивает» от границы.

При gᵢ(x) = −t (x строго внутри, зазор = t): φ(x) = − log t. При удвоении зазора барьер уменьшается на log 2.

Параметр t > 0 — «точность». При t → ∞ барьерный член (1/t)φ(x) → 0, и решение сходится к оригинальному.

Определения

Задача

— min_{x ∈ ℝⁿ} ‖Ax − b‖² + λ‖x‖²

Замкнутое решение

— берём производную по x, приравниваем к нулю:

Эффект

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

Байесовская интерпретация

— Ridge = MAP-оценка при Гауссовском prior p(x) ∝ exp(−λ‖x‖²/2). Предположение: все коэффициенты «примерно равны нулю» с одинаковой дисперсией.

Геометрическое объяснение

— уровни функции потерь ‖Ax−b‖² — эллипсоиды. Уровни L1-штрафа λ‖x‖₁ — «ромбы» (в 2D) с угловыми точками на осях. При уменьшении λ эллипсоид «раздувается» и первым касается ромба в угловой точке → xᵢ = 0 для некоторых i.

Практический пример

— в геномных данных 20000 генов-кандидатов, но реально значимых — 50. Lasso автоматически выбирает эти 50, обнуляя остальные. Ridge выдаст 20000 маленьких ненулевых коэффициентов — интерпретировать невозможно.

Когда использовать

— когда есть группы скоррелированных признаков и нужна как разреженность, так и устойчивость.

L0-минимизация

— min ‖x‖₀ при Ax = b (‖x‖₀ = число ненулевых компонент). Это NP-трудная комбинаторная задача.

L1-релаксация (Кандес, Ромберг, Тао, 2004)

— min ‖x‖₁ при Ax = b — выпуклая задача!

Теорема RIP

— если матрица A удовлетворяет RIP (Restricted Isometry Property) с константой δ_{2s} < √2 − 1, то L1-минимизация точно восстанавливает любой s-разреженный x.

RIP смысл

— A почти сохраняет норму разреженных векторов. Случайные матрицы (Гауссовские, Бернулли) удовлетворяют RIP с вероятностью →1 при m ≥ O(s log(n/s)).

Данные

— A = [[1, 2], [3, 4], [5, 6]], b = [1, 2, 3], λ = 0.5.

Шаг 1

— L = λ_max(AᵀA). AᵀA = [[35, 44], [44, 56]], λ_max ≈ 90.5. Шаг ISTA: τ = 1/L ≈ 0.011.

Шаг 2

— Начальная точка x⁰ = [0, 0].

После сходимости

— x* ≈ [0, 0.5] (одна компонента обнулилась при достаточно большом λ).

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

Здесь A ∈ ℝ^{m×n} — матрица признаков, b ∈ ℝᵐ — отклики, λ > 0 — параметр регуляризации.

Важно: матрица AᵀA + λI всегда обратима при λ > 0, даже если AᵀA вырождена! Это решает проблему мультиколлинеарности.

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

Определения

Задача SVM (hard margin)

— максимизировать зазор при правильной классификации:

Лагранжиан

— L(w, b, α) = (1/2)‖w‖² − Σᵢ αᵢ [yᵢ(wᵀxᵢ + b) − 1], αᵢ ≥ 0.

Ключевое наблюдение

— входные данные xᵢ входят только через скалярные произведения xᵢᵀxⱼ!

Kernel trick

— заменяем xᵢᵀxⱼ на K(xᵢ, xⱼ) — ядровую функцию. Тогда SVM неявно работает в высокоразмерном (возможно, бесконечномерном) пространстве признаков, не вычисляя его явно.

Линейное

— K(x, y) = xᵀy. SVM становится линейным классификатором.

Полиномиальное

— K(x, y) = (xᵀy + 1)^d. Неявно работает в пространстве полиномиальных признаков степени d.

RBF (радиальное)

— K(x, y) = exp(−‖x−y‖²/(2σ²)). Соответствует бесконечномерному пространству (!) Гауссовых функций. σ — параметр «ширины». При σ → 0: запоминание; при σ → ∞: линейный классификатор.

Симметрия

— w = α₁ y₁ x₁ + α₂ y₂ x₂ + α₃ y₃ x₃ + α₄ y₄ x₄.

Двойственная задача

— max 4α − (1/2) · (4α)² · (5+5+5+5)/(некоторая норма). После вычисления: w = (0.2, 0.2), b = 0. Зазор = 2/‖w‖ = 2/0.283 ≈ 7.07.

Теорема

— с вероятностью ≥ 1−δ (по случайной обучающей выборке), ошибка SVM ограничена:

Задача классификации: дано N точек (xᵢ, yᵢ), где xᵢ ∈ ℝⁿ и yᵢ ∈ {−1, +1} — метки классов. Нужно найти гиперплоскость, разделяющую два класса. Таких гиперплоскостей бесконечно много — любая разделяющая подойдёт. SVM (Support Vector Machine) выбирает «наилучшую» — ту, которая максимально удалена от...

Зазор (margin) = 2/‖w‖ (расстояние между двумя параллельными гиперплоскостями wᵀx + b = ±1).

Задача SVM (hard margin): максимизировать зазор при правильной классификации:

Это выпуклое квадратичное программирование! Уникальное решение (строго выпуклая цель).

Определения

Основная теорема VC

— конечная vc(H) ↔ PAC-обучаемость (Probably Approximately Correct). Число примеров для (ε, δ)-обучения: N = O((vc(H) + log(1/δ)) / ε²).

Теорема

— с вероятностью ≥ 1−δ:

Феномен implicit bias

— SGD не просто ищет любой глобальный минимум — он находит минимум с минимальной нормой.

Феномен двойного убывания (Belkin et al., 2019)

— при перепараметризации (число параметров > число данных) ошибка снова начинает убывать!

Задача

— классификация MNIST (60000 обучающих, 784 признака, 10 классов).

Формулы

Машинное обучение кажется эмпирической дисциплиной: попробовал — получилось. Но за кулисами существует математическая теория, объясняющая, почему и когда обучение даёт обобщение на новые данные. VC-теория и PAC-обучаемость — это строгие рамки. Выпуклые задачи имеют особые гарантии: независящие от...

Разбиение (shattering): набор точек S «разбит» гипотезным классом H, если для любой разметки точек ∈ {−1, +1} существует гипотеза h ∈ H, правильно классифицирующая все точки.

Основная теорема VC: конечная vc(H) ↔ PAC-обучаемость (Probably Approximately Correct). Число примеров для (ε, δ)-обучения: N = O((vc(H) + log(1/δ)) / ε²).

Следствие: обобщение ≤ O(Bρ/√N) — не зависит от размерности пространства! Только маржа (1/B) и норма данных (ρ) имеют значение.