Motivation

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

для некоторого вектора , то есть касательная к графику функции является глобальной оценкой снизу для функции.

  • Если - дифференцируема, то
  • Не все непрерывные выпуклые функции дифференцируемы :)

Не хочется лишаться такого вкусного свойства.

Subgradient

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

Subdifferential

Множество всех субградиентов функции в точке называется субдифференциалом в и обозначается .

  • Если , то выпуклое компактное множество.
  • Выпуклая функция дифференцируема в точке
  • Если , то - выпукла на .

Moreau - Rockafellar theorem (subdifferential of a linear combination)

Пусть - выпуклые функции на выпуклых множествах .
Тогда, если то функция имеет субдифференциал на множестве и

Dubovitsky - Milutin theorem (subdifferential of a point-wise maximum)

Пусть - выпуклые функции на открытом выпуклом множестве , а поточечный максимум определяется как . Тогда:

где

Chain rule for subdifferentials

Пусть - выпуклые функции на открытом выпуклом множестве , - образованная из них вектор - функция, - монотонно неубывающая выпуклая функция на открытом выпуклом множестве , причем . Тогда субдифференциал функции имеет вид:

где

В частности, если функция дифференцируема в точке , то формула запишется так:

Subdifferential calculus

  • , for
  • , - выпуклые функции
  • , - выпуклая функция

Examples

Концептуально, различают три способа решения задач на поиск субградиента:

  • Теоремы Моро - Рокафеллара, композиции, максимума
  • Геометрически
  • По определению

1

Найти , если

Решение:

Решить задачу можно либо геометрически (в каждой точке числовой прямой указать угловые коэффициенты прямых, глобально подпирающих функцию снизу), либо по теореме Моро - Рокафеллара, рассмотрев как композицию выпуклых функций:

2

Найти , если

Решение:

Совершенно аналогично применяем теорему Моро - Рокафеллара, учитывая следующее:

Таким образом:

3

Найти , если . Здесь - выпуклая функция на открытом выпуклом множестве , .

Решение:
Согласно теореме о композиции (функция - дифференцируема), а имеем:

По теореме о поточечном максимуме:

4

Найти , если

5

Найти , если

Решение: Пусть , а . Так как эти функции выпуклы, субдифференциал их суммы равен сумме субдифференциалов. Найдем каждый из них:

Далее интересными представляются лишь различные взаимные расположения векторов и , рассмотрение которых предлагается читателю.

6

Найти , если

Решение: По определению

Рассмотрим эту сумму как поточечный максимум линейных функций по : , где . Каждая такая функция однозначно определяется набором коэффициентов .

Тогда по теореме Дубовицкого - Милютина, в каждой точке

Заметим, что .

Причем, правило выбора “активной” функции поточечного максимума в каждой точке следующее:

  • Если координата точки отрицательна,
  • Если координата точки положительна,
  • Если координата точки равна нулю, то подходят оба варианта коэффициентов и соответствующих им функций, а значит, необходимо включать субградиенты этих функций в объединение в теореме Дубовицкого - Милютина.

В итоге получаем ответ: