2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

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

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Критерий для сабмодулярности квадрата сабмодулярной
Сообщение28.08.2015, 12:52 


28/08/15
3
Сабмодулярной функцией $ 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 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Критерий для сабмодулярности квадрата сабмодулярной
Сообщение28.08.2015, 14:48 


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

 Профиль  
                  
 
 Re: Критерий для сабмодулярности квадрата сабмодулярной
Сообщение28.08.2015, 14:57 
Заслуженный участник
Аватара пользователя


09/09/14
6316
ivanovserg990 в сообщении #1048741 писал(а):
Хочется понять необходимое и достаточное условие для этого.

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

 Профиль  
                  
 
 Re: Критерий для сабмодулярности квадрата сабмодулярной
Сообщение28.08.2015, 15:23 


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

 Профиль  
                  
 
 Re: Критерий для сабмодулярности квадрата сабмодулярной
Сообщение28.08.2015, 15:43 
Заслуженный участник
Аватара пользователя


09/09/14
6316
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 
Заслуженный участник
Аватара пользователя


23/07/05
17679
Москва

(Оффтоп)

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

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


09/09/14
6316

(Оффтоп)

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group