Критерий для сабмодулярности квадрата сабмодулярной

[ivanovserg990]

Сабмодулярной функцией $ f:2^E \rightarrow R $ называется функция, которая удовлетворяет следующим эквивалентным условиям:

- Для любого $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $
- Для любого $ S,T\subseteq E $ и $ S\subseteq T $ и для любого $ x\in E\setminus T : f(S\cup \{x\})-f(S)\geq f(T\cup\{x\}) - f(T) $

Также есть свойство:

$f:2^\Omega\rightarrow \mathbb{R}_+$ is a submodular function then $g:2^\Omega\rightarrow \mathbb{R}_+$ defined as $g(S)=\varphi(f(S))$ where $\varphi$ is a concave function, is also a submodular function.

Можно найти пример сабмодулярной функции, для которой квадрат не является сабмодулярной.

Есть ли какой-то критерий, чтобы квадрат сабмодулярной функции был тоже сабмодулярной функцией?

[grizzly]

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

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

Нужен ли Вам какой-то универсальный критерий необходимости и достаточности? или лучше не очень сильный, но простой для проверки в приложениях критерий достаточности? Что насчёт такого интуитивно-напрашивающегося критерия достаточности:
Квадрат неотрицательной субмодулярной функции будет "субмодулярным", если эта функция может быть представлена в виде суперпозиции субмодулярной и такой вогнутой, вогнутость которой "не слабее", чем у $\sqrt{\cdot}$.

[ivanovserg990]

Да, Вы правы. Да множество $E$ ограничено. У меня имеется функция $h:2^\Omega\rightarrow [0,1]$. Легко можно придумать пример функции, для которой квадрат функции сабмодулярный. Хочется понять необходимое и достаточное условие для этого.

[grizzly]

ivanovserg990 в сообщении #1048741 писал(а):

Хочется понять необходимое и достаточное условие для этого.

О, замечательно! Я абстракции люблю больше, чем "прикладные" задачи.
Вы согласны с достаточностью предложенного мной критерия? Насколько, по-Вашему, он не дотягивает до необходимого? Можете привести какой-нибудь контрпример или аргументы? А то я теперь думаю, почему бы ему не быть и необходимым по совместительству. Разве что-то этому мешает?

[ivanovserg990]

Хмм, наверное подходит, только сложно как-то. Пример функции можно такой? В общем, чем проще критерий, тем лучше.

[grizzly]

ivanovserg990 в сообщении #1048749 писал(а):

Пример функции можно такой?

Конечно. На базе примера из Вашей ссылки:
$E=\{a,b\};\quad g(\varnothing)=0, \ g(\{a\})=1, \ g(\{b\})=\sqrt{2}, \ g({a,b})=\sqrt{3}.$
Здесь субмодулярная функция $g$ является суперпозицией функции $f$ из примера и квадратного корня. Тогда $g^2=f$ является субмодулярной функцией.

ivanovserg990 в сообщении #1048749 писал(а):

В общем, чем проще критерий, тем лучше.

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

[Someone]

(Оффтоп)

"Саб…" — это от "sub…"? Тогда по-русски будет "суб…".

[grizzly]

(Оффтоп)

Someone в сообщении #1048779 писал(а):

"Саб…" — это от "sub…"? Тогда по-русски будет "суб…".

Вы меня немало удивили -- я умудрился ни разу не заметить эту ошибку у ТС. Глаза видели одно, а мозг читал другое. И вот сейчас нарочно пошёл убеждаться, что ТС и правда всюду так пишет, а не случайно где-то.