2014 dxdy logo

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

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


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


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Численная проверка множества на пустоту
Сообщение18.05.2020, 01:27 


17/07/14
13
Есть система неравенств. Нужно проверить, что множество её решений пусто.
Хотелось бы иметь какой-то полиномиальный численный метод.

О системе неравенств: функции в неравенствах бесконечно гладкие, множество решений, вообще говоря, не выпуклое.

 Профиль  
                  
 
 Re: Численная проверка множества на пустоту
Сообщение18.05.2020, 03:37 
Заслуженный участник


18/01/15
3312
AlexeyE в сообщении #1463523 писал(а):
Есть система неравенств. Нужно проверить, что множество её решений пусто.

Без уточнения вида системы неравенств непонятно, что имеется в виду. В слова "система неравенств" можно вкладывать, вообще говоря, 1001 смысл.

 Профиль  
                  
 
 Re: Численная проверка множества на пустоту
Сообщение18.05.2020, 11:36 


17/07/14
13
vpb в сообщении #1463532 писал(а):
Без уточнения вида системы неравенств непонятно, что имеется в виду. В слова "система неравенств" можно вкладывать, вообще говоря, 1001 смысл.


Система неравенств относительно переменной x\in R^n имеет вид:
c_i(x)\leqslant 0,\quad i=1,...,m,
где
c_i\in C^{(\infty)}(R^n,R^1),\quad i=1,...,m.

 Профиль  
                  
 
 Re: Численная проверка множества на пустоту
Сообщение18.05.2020, 11:59 
Заслуженный участник
Аватара пользователя


01/09/13
4770
А почему Вы думаете, что эта задача может быть решена численно?

 Профиль  
                  
 
 Re: Численная проверка множества на пустоту
Сообщение18.05.2020, 21:12 


17/07/14
13
Geen в сообщении #1463582 писал(а):
А почему Вы думаете, что эта задача может быть решена численно?


Рассмотрим частный случай. Допустим, все неравенства выпуклые. Это бы означало, что множество решений выпукло. Можно превратить задачу в задачу выпуклой оптимизации, добавив условие минимизации какой-нибудь простой функции. Например, константы. Для решения этой задачи можно применить, например, метод внутренней точки, который имеет полиномиальную сложность.

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

 Профиль  
                  
 
 Re: Численная проверка множества на пустоту
Сообщение18.05.2020, 22:26 
Заслуженный участник
Аватара пользователя


01/09/13
4770
AlexeyE в сообщении #1463700 писал(а):
Допустим, все неравенства выпуклые. Это бы означало, что множество решений выпукло.

Это почему?
AlexeyE в сообщении #1463700 писал(а):
Можно превратить задачу в задачу выпуклой оптимизации, добавив условие минимизации какой-нибудь простой функции. Например, константы.

Возможно я совсем не в теме, но Вы собираетесь минимизировать константу?
AlexeyE в сообщении #1463700 писал(а):
Для решения этой задачи можно применить, например, метод внутренней точки, который имеет полиномиальную сложность.

Для решения какой задачи?

 Профиль  
                  
 
 Re: Численная проверка множества на пустоту
Сообщение18.05.2020, 23:46 


17/07/14
13
На счёт выпуклости неравенств я не очень точно выразился. Я имею в виду следующее: если $x_1,x_2$ - два решения неравенства, то для любого $\lambda\in[0,1]$ точка $\lambda x_1+(1-\lambda)x_2$ - тоже решение. Если каждое из неравенств в системе обладает этим свойством, то множество решений системы неравенств выпукло.

Если ввести какую-то формальную функцию, то задача (формально) превращается в задачу выпуклой оптимизации. Методы, решающие задачу выпуклой оптимизации, умеют, в частности, определять, является ли множество допустимых точек пустым или нет. Одним из таких методов является метод внутренней точки. В случае выпуклой задачи он имеет полиномиальную сложность.

 Профиль  
                  
 
 Re: Численная проверка множества на пустоту
Сообщение19.05.2020, 01:46 
Заслуженный участник


18/01/15
3312
А, примерно понял. Нет, не может быть такого метода. Точно как доказать не знаю, но есть такой "метод сопротивляющегося оракула". Это см. в книге Нестеров, Введение в выпуклую оптимизацию.

 Профиль  
                  
 
 Re: Численная проверка множества на пустоту
Сообщение19.05.2020, 16:13 


17/07/14
13
vpb в сообщении #1463769 писал(а):
А, примерно понял. Нет, не может быть такого метода. Точно как доказать не знаю, но есть такой "метод сопротивляющегося оракула". Это см. в книге Нестеров, Введение в выпуклую оптимизацию.


Хорошая книжка. Спасибо!

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

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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