субдифференциал

[Anya90]

Здравствуйте.

Рассмотрим упорядоченные координаты вектора $x$:
$x_{[1]}, x_{[2]}, ..., x_{[n]}$.
Нужно найти субдифференциал функции:
$f_k(x)=\sum_{j=1}^k x_{[j]}$ для любого $k=1,...,n$.

Легко показать, что данная функция выпуклая. По определению ее субдифференциал в точке $x$:
$\{g\in R^n: f_k(y) \geq f_k(x) + <g,y-x>, \forall y \in R^n\}$.
Но как его найти? Я думала, что м.б. стоит рассмотреть эту функцию, как сумму $k$ функций, тогда субдифференциал нужной функции будет равен сумме субдифференциалов. Но я не знаю, как искать субдифференциалы этих отдельных функций. Поделитесь, пожалуйста, идеями.

[paha]

Заметьте, что $f_k(x)=<F_k,x>$, где $F_k\in\mathbb{R}^n$ -- некоторый вектор.

[paha]

пардон, я невнимательно прочел про "упорядоченные", так что, разумеется, $f_k(x)$ не имеет указанный мною вид:(

[dsmmbrd]

Найти можно просто по определению. Субдифференциал в точке $x=(x_{1}, ... , x_{n})}$ - это множество всех таких линейных функционалов $\alpha$, которые для любого $y=(y_{1}, ... , y_{n}) \in R^{n}$ удовлетворяют условию:
$f(y) \geq f(x)+ \alpha(y-x)$.
По теореме Рисса об общем виде линейного ограниченного функционала в гильбертовом пространстве, функционал $\alpha$ действует на вектора, как скалярное умножение на некоторый вектор $(\alpha_{1}, ... , \alpha_{n})$, то есть:
$\alpha(x)=\alpha_{1}x_{1}+ ... + \alpha_{n}x_{n}$. Перепишем наше неравенство:
$y_{1}+...+y_{n} \geq x_{1}+...x_{n} + \alpha_{1}(y_{1}-x_{1})+...+\alpha_{n}(y_{n}-x_{n})$
Осталось понять, какими должны быть $\alpha_{i}$, чтобы неравенство выполнялось при любых $y$

[MaximVD]

Пусть $x = (x_1,\ldots, x_n)$. Функцию $f_k(x)$ можно представить в виде

$$ f_k(x) = \max_{i_1, \ldots , i_k} (x_{i_1} + \ldots + x_{i_k}), $$

где максимум берётся по всем возможным наборам индексов $i_1, \ldots, i_k$ таким, что $i_l \ne i_s$ при $l \ne s$. Дальше остаётся воспользоваться формулой для вычисления субдифференциала функции максимума (супремума) выпуклых функций. Однако, чем больше $k$, тем больше будет различных "выражений" для субдифференциала в зависимости от соотношений между коодинатами вектора $x$.

[dsmmbrd]

я, похоже, тоже неправильно понял условие)