Негладкий аналіз та обчислювальні правила субдиференціала Кларка: класика та сучасність

• f(x)=|x|
• f(x)=max_i f_i(x)
• функції відстані
• функції значення (value functions) в оптимізації/керуванні
• кусково-лінійні функції втрат типу ReLU

2. Узагальнена похідна Кларка за напрямом

Для локально ліпшицевої f узагальнена похідна Кларка за напрямом у точці x у напрямі v визначається як:^E

f°(x; v) = limsup_{y -> x, t ↓ 0} [f(y + t v) - f(y)] / t.

Ключові моменти:

• Визначена для локально ліпшицевих негладких функцій.^EE
• Є додатно однорідною та субадитивною за v у стандартній теорії Кларка.^LE
• Зазвичай більша або дорівнює звичайній похідній за напрямом, коли обидві існують.^E
• Відображає «найгірший» локальний ріст функції в околі точки x.^EE

3. Субдиференціал Кларка

Субдиференціал Кларка визначається як:^E

∂C f(x) = { ξ ∈ R^n: f°(x; v) ≥ <ξ, v> для всіх v ∈ R^n }.

Еквівалентний опис для локально ліпшицевих f: це опукла оболонка границь градієнтів у точках, де функція диференційовна:^EE

∂C f(x) = co { границі ∇f(x_k): x_k → x, f диференційовна в x_k }.

Тут co позначає опуклу оболонку.

Ключові властивості:

• ∂C f(x) — це множинне узагальнення похідної для локально ліпшицевих функцій.^EE
• Для локально ліпшицевої f субдиференціал Кларка є непорожньою, компактною та опуклою множиною.^EE
• Якщо f неперервно диференційовна поблизу x, то субдиференціал Кларка зводиться до звичайного градієнта: ∂C f(x) = {∇f(x)}.^EE
• Для опуклих функцій субдиференціал Кларка збігається зі звичайним субдиференціалом опуклого аналізу.^LE

Приклад:

f(x) = |x|.

Тоді

∂C f(x) =
  {-1},        x < 0
  [-1, 1],     x = 0
  {1},         x > 0.

Це класичний приклад, що показує, як «кут» функції представляється цілим інтервалом можливих нахилів.^EE

4. Обчислювальні правила для субдиференціала Кларка

Нехай f, g: R^n → R — локально ліпшицеві поблизу x. Правила Кларка є центральною частиною теорії негладкої оптимізації.^LEE

Правило суми

∂C(f + g)(x) ⊂ ∂C f(x) + ∂C g(x).

За додаткових умов регулярності може виконуватися рівність.^LE

Множення на скаляр

Для скаляра a:

∂C(a f)(x) = a ∂C f(x).

Якщо a < 0, множина віддзеркалюється.^E

Правило добутку

∂C(fg)(x) ⊂ f(x) ∂C g(x) + g(x) ∂C f(x).

Це один зі стандартних результатів типу включень у численні Кларка.^LE

Правило частки

Якщо g(x) ≠ 0 і g відокремлена від нуля поблизу x:

∂C(f/g)(x) ⊂ [g(x) ∂C f(x) - f(x) ∂C g(x)] / g(x)^2.

Правило ланцюга

Якщо F: R^n → R^m є строго диференційовною в x, а φ: R^m → R — локально ліпшицевою поблизу F(x), то правило ланцюга Кларка має вигляд включення:^LE

∂C(φ ∘ F)(x) ⊂ DF(x)^T ∂C φ(F(x)).

Якщо φ є регулярною за Кларком, доступні сильніші форми.^LE

Правило максимуму

Якщо

f(x) = max { f1(x), ..., fm(x) },

де кожна fi локально ліпшицева, то для множини активних індексів I(x) = { i: fi(x) = f(x) } виконується:^LE

∂C f(x) ⊂ co ⋃_{i ∈ I(x)} ∂C fi(x).

Якщо всі fi гладкі, то:

∂C f(x) ⊂ co { ∇fi(x): i ∈ I(x) }.

За певних умов регулярності може виконуватися рівність.^LE

Правило Ферма для негладкої оптимізації

Якщо x — точка локального мінімуму локально ліпшицевої функції f, то виконується необхідна умова:^LE

0 ∈ ∂C f(x).

Це негладкий аналог класичної умови ∇f(x)=0.^LE

5. Класичні роботи та книги

• Роботи Ф. Г. Кларка про узагальнені градієнти є фундаментальними для цієї галузі.^E
• Узагальнені похідні Кларка та узагальнені градієнти детально розглядаються в літературі з негладкої оптимізації, зокрема в роботах Ж.-Б. Іріар-Уррюті.^L
• Роботи Р. Т. Рокафеллара про узагальнені субградієнти в математичному програмуванні є ще одним фундаментальним напрямком.^S
• Праця Іріар-Уррюті обговорює похідні Кларка за напрямом, узагальнені градієнти, обчислювальні правила та застосування до негладкої оптимізації в скінченновимірному випадку.^L

6. Сучасні напрямки досліджень (остання література)

• Сучасні дослідження з негладкої оптимізації продовжують використовувати об'єкти типу Кларка та пов'язані релаксації. Наприклад, робота 2025 року досліджує швидкість збіжності з використанням субдиференціала Ґольдштайна, який описується як релаксована версія субдиференціала Кларка, що використовується в кількох алгоритмах.^L
• Узагальнені похідні Кларка за напрямом продовжують з'являтися в умовах оптимальності для задач множинної оптимізації; робота 2025 року досліджує наближені слабкі мінімальні розв'язки з використанням нового типу узагальненої похідної Кларка.^A
• Нещодавні публікації Рокафеллара вказують на продовження роботи в галузі множинного та негладкого аналізу, включаючи роботу 2025 року, пов'язану з варіаційним численням.^S

7. Рекомендована послідовність вивчення

1. Почніть з узагальненої похідної Кларка за напрямом та субдиференціала.^LEE
2. Вивчіть основні обчислювальні правила: суми, добутку, ланцюга, максимуму та правило Ферма.^LE
3. Ознайомтеся з субдиференціалами опуклих функцій та порівняйте їх із субдиференціалами Кларка.^LS
4. Перейдіть до варіаційного аналізу: нормальні конуси, копохідні та ширші рамки узагальненого диференціювання.^SS
5. Прочитайте сучасні роботи з оптимізації, які використовують субдиференціали Кларка або Ґольдштайна в алгоритмах.^L

Практичний список першочергового читання:

• Роботи Кларка про узагальнені градієнти.^E
• Робота Іріар-Уррюті про узагальнені похідні та негладку оптимізацію.^L
• Рокафеллара «Узагальнені субградієнти в математичному програмуванні».^S
• Сучасні статті з використанням субдиференціалів типу Ґольдштайна або Кларка в алгоритмах та умовах оптимальності.^LA