Выпуклость функции на Rn

[copyleft]

Подскажите, как можно доказать выпуклость функции на Rn:
$f(x)=\frac{1}{2} (Ax,x)-(b,x)$, где А – неотрицательно определенная симметричная матрица?

[Gortaur]

Может, лапласиан взять?

[ewert]

Выпуклость вообще равносильна выпуклости на любой прямой вида $\vec x+t\vec y$. На каждой такой прямой получается квадратичная (или линейная) функция числового аргумента $t$, и её выпуклость тривиальна: если бы рога параболы смотрели вниз, то матрица никак не могла бы быть неотрицательной (т.к. на этой линии её квадратичная форма уходила бы в минус бесконечность).

[copyleft]

А можно ли этот факт доказать "в лоб" и получить выполнение неравенства: $f(ax'+(1-a)x'') \leq a f(x')+(1-a) f(x'')$?

[ewert]

copyleft в сообщении #382883 писал(а):

А можно ли этот факт доказать "в лоб" и получить выполнение неравенства

Можно всё. Но далеко не всё нужно.

[copyleft]

Что мне сделать? Как провести доказательство...

[ewert]

copyleft в сообщении #382935 писал(а):

Что мне сделать? Как провести доказательство...

Как я сказал.

Обратите внимание, что слова

ewert в сообщении #382859 писал(а):

Выпуклость вообще равносильна выпуклости на любой прямой

-- вполне принципиальны.

[copyleft]

Я не понимаю, что значит выпуклость на любой прямой. Это отклонение от нее что ли?

[ewert]

copyleft в сообщении #382944 писал(а):

Я не понимаю, что значит выпуклость на любой прямой.

Нет, это я не понимаю. Вы же знаете, что такое выпуклость вообще. И при этом не знаете, что значит выпуклость обычной функции одной переменной, полученной сужением той исходной функции на некоторое одномерное многообразие?... Совершенно не понимаю, как это может сочетаться.

[copyleft]

к сожалению..

-- Пт дек 03, 2010 00:08:51 --

Ладно, спасибо.

[Gortaur]

ewert имеет ввиду, что при любых фиксированных $x,y\in\mathbb{R}^n$ Вы должны лишь проверить выпуклость
$f(x+ty)$ как функции только от $t\in\mathbb{R}$. Это и называется сужением функции на прямую - т.е. Вы рассматриваете ее не на всей области определения, а лишь на части этой области.
Думаю, доказать что для любых $x,y$ выпуклость $f(x+ty)$ как функции от $t$ несложно, другое дело что я не знаю так ли легко показать равносильность выпуклости вообще и выпуклости на каждой прямой (возможно это только для такой квадратичной функции).
Что дали Ваши попытки в лоб?

[Padawan]

А что такое выпуклость функции нескольких переменных? $f(p_1x_1+\ldots+p_nx_n)\leqslant p_1f(x_1)+\ldots +p_nf(x_n)$ при $\sum_i p_i =1$, $p_i\geqslant 0$ ? Плюс множество задания должно быть выпуклым?

-- Пт дек 03, 2010 13:59:37 --

Gortaur в сообщении #383046 писал(а):

другое дело что я не знаю так ли легко показать равносильность выпуклости вообще и выпуклости на каждой прямой

Для $n=3$ пощупайте. Потом по индукции для любого $n$.

[TOTAL]

copyleft в сообщении #382883 писал(а):

А можно ли этот факт доказать "в лоб" и получить выполнение неравенства: $f(ax'+(1-a)x'') \leq a f(x')+(1-a) f(x'')$?

Да, легко.

[ewert]

Gortaur в сообщении #383046 писал(а):

другое дело что я не знаю так ли легко показать равносильность выпуклости вообще и выпуклости на каждой прямой

Ну, выпуклость на любой прямой есть частный случай выпуклости вообще. С другой стороны, для любой конкретной пары точек для выполнения условия выпуклости на этой паре достаточно выполнения этого условия на соединяющей их прямой. Ибо:

Padawan в сообщении #383063 писал(а):

А что такое выпуклость функции нескольких переменных? $f(p_1x_1+\ldots+p_nx_n)\leqslant p_1f(x_1)+\ldots +p_nf(x_n)$ при $\sum_i p_i =1$, $p_i\geqslant 0$ ?

-- это уж как-то чересчур. Стандартно под выпуклостью функции ("выпуклостью вниз", естественно) понимается просто выполнение неравенства $f(\theta\vec x+(1-\theta)\vec y)\leqslant\theta f(\vec x)+(1-\theta)f(\vec y)$ для любой пары векторов $\vec x$, $\vec y$ и для любого $\theta\in[0;1]$. Потом ещё можно в качестве уточнения добавить различение строгой и нестрогой выпуклостей. И всё это, кстати -- независимо от размерности (и даже от конечности или бесконечности той размерности).

[Padawan]

ewert в сообщении #383117 писал(а):

Стандартно под выпуклостью функции ("выпуклостью вниз", естественно) понимается просто выполнение неравенства $f(\theta\vec x+(1-\theta)\vec y)\leqslant\theta f(\vec x)+(1-\theta)f(\vec y)$ для любой пары векторов $\vec x$, $\vec y$ и для любого $\theta\in[0;1]$.

Так это же и есть условие выпуклости вдоль любой прямой. В общем, понятно. То, что я написал -- это неравенство Йенсена. Следует из стандартного (Вашего) определения -- график лежит ниже хорды.