Мат. программирование. Дизъюнктивная система неравенств.

[_hum_]

Подскажите, пожалуйста, каким образом в задачах нелинейного программирования обрабатываются ограничения, включающие систему неравенств с логическим "или", то есть, наподобие $g_1(x) < 0 \text{ или } g_2(x) < 0$.

(Систему равенств вроде понятно как свести: $g_1(x) = 0 \text{ или } g_2(x) = 0$ <=> $g_1(x) g_2(x) = 0$, а вот с неравенствами вопрос. Надеюсь, не разбиением на несколько задач оптимизации, каждая из которых соответствует своей области, ибо это чревато экспоненциальным взрывом даже в простейших случаях)

[iifat]

У вас что, так много подобных условий? Как по мне, вполне себе метод. Более того (это уже касательно вашего преобразования для равенств), решать две задачи попроще вполне может оказаться быстрее и точнее, чем одну задачу посложнее.

[upgrade]

Думал так (с нулем не работает):
$g_1(x) g_2(x)-|g_1(x) g_2(x)|<0$.

[VPro]

_hum_ в сообщении #1125394 писал(а):

Подскажите, пожалуйста, каким образом в задачах нелинейного программирования обрабатываются ограничения, включающие систему неравенств с логическим "или", то есть, наподобие $g_1(x) < 0 \text{ или } g_2(x) < 0$.

(Систему равенств вроде понятно как свести: $g_1(x) = 0 \text{ или } g_2(x) = 0$ <=> $g_1(x) g_2(x) = 0$, а вот с неравенствами вопрос. Надеюсь, не разбиением на несколько задач оптимизации, каждая из которых соответствует своей области, ибо это чревато экспоненциальным взрывом даже в простейших случаях)

$g_i(x)\le0$, $i=1,\dots,n$ эквивалентно $g_0(x)\le0$, где $g_0(x)=\max_{i}g_i(x)$.

[_hum_]

iifat в сообщении #1125400 писал(а):

У вас что, так много подобных условий? Как по мне, вполне себе метод. Более того (это уже касательно вашего преобразования для равенств), решать две задачи попроще вполне может оказаться быстрее и точнее, чем одну задачу посложнее.

да, немало (там из геометрической задачи вытекает, например, условия на касание двух прямоугольников - могут касаться или сверху, или снизу, или слева, или справа, см. dxdy.ru/topic108768). к тому же они начинают "перемешиваться" с конъюнкцией, и выдирать отдельно эти все варианты - очень сильно уменьшает читабельность и как следствие увеличивает ошибки.

VPro в сообщении #1125403 писал(а):

$g_i(x)\le0$, $i=1,\dots,n$ эквивалентно $g_0(x)\le0$, где $g_0(x)=\max_{i}g_i(x)$.

намекаете на то, что дизъюнкцию можно записать как $\min_{i}g_i(x) \leq 0$? хм.. может быть, и подойдет (ведь, я ничего не путаю, $\min$ может быть представлен через арифметические операции и взятие модуля?)

upgrade в сообщении #1125402 писал(а):

Думал так (с нулем не работает):
$g_1(x) g_2(x)-|g_1(x) g_2(x)|<0$.

нет, для случая $g_1(x) < 0$ и $g_2(x) < 0$ тоже не сработает.

[upgrade]

Можно конечно сделать финт ушами и просто ошибки вылавливать $\sqrt{g_1(x)}\cdot\sqrt{g_2(x)}$

[VPro]

_hum_ в сообщении #1125405 писал(а):

VPro в сообщении #1125403 писал(а):

$g_i(x)\le0$, $i=1,\dots,n$ эквивалентно $g_0(x)\le0$, где $g_0(x)=\max_{i}g_i(x)$.

намекаете на то, что дизъюнкцию можно записать как $\min_{i}g_i(x) \leq 0$? хм.. может быть, и подойдет (ведь, я ничего не путаю, $\min$ может быть представлен через арифметические операции и взятие модуля?)

Да, "намекаю". Я по привычке написал условия одновременного выполнения всех неравенств, те условие конъюнкции. Вы правы, если требуется выполнение хотя бы одного из условий (дизъюнкция), то максимум меняем на минимум:
$\bigvee_{i}{\left(g_i(x)\le0\right)} \Leftrightarrow \min_{i}g_i(x)\le0$

-- Пн май 23, 2016 17:32:56 --

_hum_ в сообщении #1125405 писал(а):

ведь, я ничего не путаю, $\min$ может быть представлен через арифметические операции и взятие модуля?

$\min\{g_1;g_2\}=-\frac12\left(|g_2-g_1|-g_2-g_1 \right)$

[upgrade]

С мнимыми работает.
$-\Biggl(i\Bigl(\sqrt{g_1(x)}\Bigr)+i\Bigl(\sqrt{g_1(x)}\Bigr)\right \Biggr)<0$
Находим коэффициенты при мнимой единице корней из $g_1(x)$, $g_2(x)$, и их суму умножаем на $-1$

[mserg]

Классика жанра - это псевдобулевы переменные $b_i$ и "большое число" $M$:
$g_1(x)<b_1M$
$g_2(x)<b_2M$
$b_1+b_2<=1$

[_hum_]

upgrade, эта проблема относится к теме нелинейного программирования, а не просто "как можно задать множество одним неравенством" :)

VPro, да, спасибо.

mserg, о, вот этот подход с "релаксацией" уже, действительно, интересен. спасибо.
п.с. может, еще подскажете литературу, где бы можно было бы быстро познакомиться со всеми такими приемами, используемыми в нелинейном программировании?

[upgrade]

_hum_ в сообщении #1125433 писал(а):

а не просто "как можно задать множество одним неравенством"

Тогда к чему написано это:

_hum_ в сообщении #1125394 писал(а):

Систему равенств вроде понятно как свести: $g_1(x) = 0 \text{ или } g_2(x) = 0$ <=> $g_1(x) g_2(x) = 0$,

[_hum_]

upgrade, имелось в виду, нужно, чтобы новая функция была хорошей для применения методов решения задач нелинейной оптимизации

[mserg]

Если речь идет об создания логических ограничений, то линейность / нелинейность $g(x)$ не имеет значения.
Насчет литературы не подскажу, но припоминаю, довольно много приемов описано в документации пакета lpsolve.