2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Критерий для сабмодулярности квадрата сабмодулярной
Сообщение28.08.2015, 12:52 
Сабмодулярной функцией $ 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.

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

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

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

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

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

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

 
 
 
 Re: Критерий для сабмодулярности квадрата сабмодулярной
Сообщение28.08.2015, 14:57 
Аватара пользователя
ivanovserg990 в сообщении #1048741 писал(а):
Хочется понять необходимое и достаточное условие для этого.

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

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

 
 
 
 Re: Критерий для сабмодулярности квадрата сабмодулярной
Сообщение28.08.2015, 15:43 
Аватара пользователя
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 писал(а):
В общем, чем проще критерий, тем лучше.

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

 
 
 
 Re: Критерий для сабмодулярности квадрата сабмодулярной
Сообщение28.08.2015, 16:48 
Аватара пользователя

(Оффтоп)

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

 
 
 
 Re: Критерий для сабмодулярности квадрата сабмодулярной
Сообщение28.08.2015, 17:03 
Аватара пользователя

(Оффтоп)

Someone в сообщении #1048779 писал(а):
"Саб…" — это от "sub…"? Тогда по-русски будет "суб…".

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

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group