Вогнутость функции

[Rich]

На вещественной прямой задана метрика $d$, инвариантная относительно сдвигов. Определим функцию $f=d(0,x)$. Является ли функция $f$ вогнутой? Не получается доказать, это утверждение использовалось без доказательства в одной статье.

[Dmitriy40]

Простите, но если $d$ определить просто как ориентированное расстояние между точками $d(a,b)=a-b$, то $f=d(0,x)$ будет прямой - разве ж прямая вогнута? Уж не контрпример ли это? Или я туплю? Может быть в статье использовалась не произвольная метрика, а некий подкласс (ну к примеру метрика $d(a,b)=(a-b)^2$), для которого утверждение верно?

[Dan B-Yallay]

Dmitriy40 в сообщении #1312704 писал(а):

Простите, но если $d$ определить просто как ориентированное расстояние между точками $d(a,b)=a-b$

Метрика не бывает отрицательной. Если я правильно понял определение.

[Xaositect]

Это неверно, дискретная метрика, например, не подходит. А в статье точно никаких дополнительных предположений нет?

[Dmitriy40]

Сначала написал классически с модулем разности, но тогда функция может и правда стать вогнутой в точке $(0,0)$, тут уже я не уверен в определениях.
Хорошо, а константная метрика $d(a,b)=0$ не подойдёт как контрпример? Метрикой оно является, аксиомам удовлетворяет, к сдвигам инвариантна, а других условий и не наложено ...
Ещё в разрывных функциях можно метрику задать (типа $d(a,b)=\left\lfloor |a-b| \right\rfloor$) и там вопрос вогнутости становится нетривиальным. А, про дискретные уже сказали.

[arseniiv]

Dmitriy40 в сообщении #1312710 писал(а):

Метрикой оно является

Увы, нет. Первая аксиома не удовлетворена, расстояние между разными точками не должно быть нулём. Есть обобщения, конечно.

[iifat]

Dmitriy40 в сообщении #1312710 писал(а):

аксиомам удовлетворяет

Насколько я помню, одной из аксиом является равенство нулю только для совпадающих точек, не?

-- 17.05.2018, 00:31 --

Не стал стирать — наколачивал, старался

arseniiv в сообщении #1312716 писал(а):

Есть обобщения, конечно

Обобщения такие затейники... Есть и отрицательные обобщения, да и вообще, наверное, всякие разные.

[Dmitriy40]

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

[arseniiv]

Ну вы чего, в первой аксиоме же следование в обе стороны: $d(x, y) = 0 \Leftrightarrow x = y$.

(Оффтоп)

iifat
Немного эрудиции там и сям нелишне, одно предложение не занимает особого места. А вот его обсуждение уже заняло много больше.

[Dmitriy40]

(Туплю)

arseniiv
А-а-а, точно, ну совсем туплю значит.
А с модулем она таки вогнута, тоже не подходит как контрпример.

[vpb]

Вероятно, ТС неправильно (или не до конца) понял, что в статье написано.

Можно построить такой пример. Определим функцию $f$ на $[0; 2]$ как $f(x)=x$ при $0\leq x\leq1$ и $f(x)=1$ при $1\leq x\leq2$. Затем определим $g$ на $[0; \infty)$ как $g(x)=\inf f(x_1-x_0)+f(x_2-x_1)+\ldots+f(x_t-x_{t-1})$, инфимум по всем $(x_0=0\leq x_1\leq\ldots\leq x_t=x)$ таким, что $x_i-x_{i-1}\leq 2$ $\forall i$. Наконец, положим $d(x,y)=g(|x-y|)$.
Тогда легко видеть, что $d$ --- трансляционно-инвариантная метрика на ${\mathbb R}$. Однако же $d(0,x)$ не является вогнутой функцией на $[0,\infty)$ (и даже в любой окрестности точки $x=2$).

Для порядку напомним, что функция $f$ на выпуклом множестве $C$ (в каком-либо линейном пространстве) называется вогнутой, если

$$ f(\lambda x+(1-\lambda)y)\geq \lambda f(x)+(1-\lambda)f(y) \ \ \forall x,y\in C, \ \ 0\leq\lambda\leq1. $$

(т.е. дуга графика всегда лежит не ниже, чем хорда).
При этом, вообще говоря, не предполагается, что $f$ непрерывна. Например, если $f(0)=0$ и $f(x)=1$ при $x>0$, то $f$ вогнута на $[0,\infty)$.

С другой стороны, допустим, что $f$ --- вогнута на $[0,\infty)$, неотрицательна и $f(0)=0$. Тогда, как легко видеть, $d(x,y)=f(|x-y|)$ --- трансляционно-инвариантная метрика. (Возможно, именно про это на самом деле в той статье речь и шла. Если же нет, значит там были какие-то дополнительные условия, или более слабое заключение.) В частности, и обычная метрика, и дискретная порождаются подходящей вогнутой функцией.

Также отметим, что про вогнутость $d(0,x)$ на всей прямой речи идти не может (абсурдность такой ситуации усматривается легко).

[Rich]

Спасибо большое за ответы! Либо я неправильно понял утверждение в статье, либо там ошибка. Попробую разобраться.

[Rich]

Остальные утверждения удалось проверить. Но не получается убедиться, что функция $d(x,y)=g|x-y|$, действительно удовлетворяет неравенству треугольника.

[vpb]

Rich
Ну а если скажем так ... Пусть $f$ --- вообще любая неотрицательная функция на отрезке $[0,2]$, равная нулю в нуле. Определим $g$ той же самой формулой, и $d$ так же, как раньше. Тогда $d$ удовлетворяет неравенству треугольника. Можете доказать? Это я к тому, что, может быть, Вас конкретный вид функции $f$ запутывает --- так он тут ни при чем.

[Rich]

vpb в сообщении #1312799 писал(а):

Вероятно, ТС неправильно (или не до конца) понял, что в статье написано.

Можно построить такой пример. Определим функцию $f$ на $[0; 2]$ как $f(x)=x$ при $0\leq x\leq1$ и $f(x)=1$ при $1\leq x\leq2$. Затем определим $g$ на $[0; \infty)$ как $g(x)=\inf f(x_1-x_0)+f(x_2-x_1)+\ldots+f(x_t-x_{t-1})$, инфимум по всем $(x_0=0\leq x_1\leq\ldots\leq x_t=x)$ таким, что $x_i-x_{i-1}\leq 2$ $\forall i$. Наконец, положим $d(x,y)=g(|x-y|)$.
Тогда легко видеть, что $d$ --- трансляционно-инвариантная метрика на ${\mathbb R}$. Однако же $d(0,x)$ не является вогнутой функцией на $[0,\infty)$ (и даже в любой окрестности точки $x=2$).

Для порядку напомним, что функция $f$ на выпуклом множестве $C$ (в каком-либо линейном пространстве) называется вогнутой, если

$$ f(\lambda x+(1-\lambda)y)\geq \lambda f(x)+(1-\lambda)f(y) \ \ \forall x,y\in C, \ \ 0\leq\lambda\leq1. $$

(т.е. дуга графика всегда лежит не ниже, чем хорда).
При этом, вообще говоря, не предполагается, что $f$ непрерывна. Например, если $f(0)=0$ и $f(x)=1$ при $x>0$, то $f$ вогнута на $[0,\infty)$.

С другой стороны, допустим, что $f$ --- вогнута на $[0,\infty)$, неотрицательна и $f(0)=0$. Тогда, как легко видеть, $d(x,y)=f(|x-y|)$ --- трансляционно-инвариантная метрика. (Возможно, именно про это на самом деле в той статье речь и шла. Если же нет, значит там были какие-то дополнительные условия, или более слабое заключение.) В частности, и обычная метрика, и дискретная порождаются подходящей вогнутой функцией.

Также отметим, что про вогнутость $d(0,x)$ на всей прямой речи идти не может (абсурдность такой ситуации усматривается легко).

До этого вроде бы все сошлось, а сейчас не получается. Можете указать конкретные $x,y, \lambda$ при которых нарушается вогнутость $g$.