Численная проверка множества на пустоту

[AlexeyE]

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

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

[vpb]

AlexeyE в сообщении #1463523 писал(а):

Есть система неравенств. Нужно проверить, что множество её решений пусто.

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

[AlexeyE]

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.

[Geen]

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

[AlexeyE]

Geen в сообщении #1463582 писал(а):

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

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

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

[Geen]

AlexeyE в сообщении #1463700 писал(а):

Допустим, все неравенства выпуклые. Это бы означало, что множество решений выпукло.

Это почему?

AlexeyE в сообщении #1463700 писал(а):

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

Возможно я совсем не в теме, но Вы собираетесь минимизировать константу?

AlexeyE в сообщении #1463700 писал(а):

Для решения этой задачи можно применить, например, метод внутренней точки, который имеет полиномиальную сложность.

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

[AlexeyE]

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

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

[vpb]

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

[AlexeyE]

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

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

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