Сопряжённые функции Фенхеля

Идея преобразования Лежандра-Фенхеля

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

Определение сопряжённой функции

Сопряжённая функция Фенхеля (или Лежандра-Фенхеля):

f*(y) = sup_{x ∈ dom(f)} {yᵀx − f(x)}

Смысл каждого символа:

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

Геометрически: f*(y) — максимальный «зазор» между линейной функцией yᵀx и f(x).

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

Неравенство Фенхеля-Юнга

Из определения немедленно следует:

f*(y) ≥ yᵀx − f(x) для всех x, y

что эквивалентно неравенству Фенхеля-Юнга:

f(x) + f*(y) ≥ yᵀx

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

Примеры вычисления

Квадратичная функция f(x) = (1/2)‖x‖² (при n=1: f(x) = x²/2):

f*(y) = sup_x {yx − x²/2} = sup_x {−(x − y)²/2 + y²/2} = y²/2

Результат: f*(y) = (1/2)‖y‖² — самосопряжённая! Максимум достигается при x = y.

L1-норма f(x) = ‖x‖₁ = Σᵢ|xᵢ|:

f*(y) = sup_x {yᵀx − ‖x‖₁} = δ_{‖y‖_∞ ≤ 1}(y)

(0 если ‖y‖_∞ = max|yᵢ| ≤ 1, иначе +∞)

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

Экспонента f(x) = eˣ (n=1):

f*(y) = sup_x {yx − eˣ}. Производная: y − eˣ = 0 → x = log y (при y > 0). Значение: y·log y − e^{log y} = y·log y − y. Для y ≤ 0: супремум = +∞.

Результат: f*(y) = y log y − y при y > 0, +∞ при y ≤ 0.

Отрицательная энтропия f(x) = Σᵢ xᵢ log xᵢ (при xᵢ > 0):

f*(y) = log(Σᵢ eʸⁱ) — это log-sum-exp! Мягкая аппроксимация максимума.

Двойственность через сопряжённые функции

Двойственная задача для min_x {f(x) + g(Bx)}:

Через сопряжённые: max_y {−f*(−Bᵀy) − g*(y)}.

Задача LASSO: min_x {(1/2)‖Ax−b‖² + λ‖x‖₁}

Сопряжённые: ((1/2)‖·‖²)* = (1/2)‖·‖², (λ‖·‖₁)* = λ δ_{‖·‖_∞ ≤ 1}.

Двойственная: max_y {bᵀy − (1/2)‖y‖²} при ‖Aᵀy‖_∞ ≤ λ — это QP с L∞-ограничением.

Полный разбор примера: вычисление f* для log-барьера

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

f*(y) = sup_{x > 0} {yx − (−log x)} = sup_{x > 0} {yx + log x}

Шаг 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 одной функции трудно, вычисляем прокс сопряжённой.

Свойства преобразования Фенхеля

Сопряжённое преобразование обладает замечательными свойствами:

Сопряжённая функция всегда выпуклая (даже если f не выпуклая) — преобразование «выпукливает» функцию
Двойное сопряжённое f** = f, если f выпуклая и замкнутая; в общем случае f** — выпуклая оболочка f
Соответствие порядка: f₁ ≤ f₂ → f₂* ≤ f₁*
Сопряжённое к сумме: (f₁ + f₂)* = f₁* □ f₂* (инфимальная конволюция)
Связь с субдифференциалом: y ∈ ∂f(x) ⟺ x ∈ ∂f*(y) ⟺ f(x) + f*(y) = xᵀy

Примеры пар сопряжённых

f(x) = (1/2)xᵀPx (квадратичная) ↔ f*(y) = (1/2)yᵀP⁻¹y
f(x) = exp(x) ↔ f*(y) = y log y − y (для y > 0)
f(x) = log(1 + eˣ) (softplus) ↔ f*(y) = y log y + (1−y) log(1−y) (бинарная энтропия) для y ∈ [0,1]
f(x) = ‖x‖p ↔ f*(y) = δ{‖·‖_q ≤ 1}(y), где 1/p + 1/q = 1 (двойственные нормы)
f(x) = max(x₁,...,xₙ) ↔ f*(y) = δ_Δ(y) (индикатор симплекса)

Применения

Преобразование Фенхеля — основа двойственности Фенхеля-Рокафеллара, обобщающей лагранжеву двойственность. В термодинамике сопряжение Лежандра связывает свободную энергию Гельмгольца и Гиббса, внутреннюю энергию и энтальпию. В выпуклом анализе образа Фенхеля используется для построения «двойственных» алгоритмов: проксимальное расщепление, primal-dual hybrid gradient, Chambolle-Pock — все они оперируют сопряжёнными функциями для эффективного решения задач с неразделимыми членами.