Решение систем нелин-х уравнений на заданном мн-ве корней.

[intheruder]

Здравствуйте.
Суть задачи - имеется система из n трансцендентных уравнений с n неизвестных. Известно, что существуют решения (необязательно именно все решения - но какая-то часть из них обязательно) системы, которые принадлежат какому-то ограниченному множеству целых чисел, количество элементов которого меньше количества переменных. Например, одним из решений системы с 10 неизвестными будет какой-то набор из чисел 1,2,3

Вопрос, как именно оптимизировать поиск этих конкретных решений? Возможно, есть какие-то готовые библиотеки для решения такой задачи?

Я пробовал библиотеку scipy.optimize для Python и ее метод для поиска минимума вектор-функции least_squares, но, к сожалению, он позволяет задать только интервал значений переменных, а не конкретное множество значений, которые они могут принимать. А в методах из этой библиотеки для поиска решений подобных систем уравнений (root, fsolve и пр.) даже интервал задать нельзя.
Спасибо.

[mihiv]

Как ни оптимизируй, все равно нужно будет проверить $3^{10}$ предполагаемых решений (в вашем примере).

[Sender]

mihiv в сообщении #1498256 писал(а):

Как ни оптимизируй, все равно нужно будет проверить $3^{10}$ предполагаемых решений (в вашем примере).

Вовсе не обязательно, скажем, если алгоритм поиска решений сумеет показать, к примеру, что при $x_1=3$ какое-то из уравнений заведомо не имеет решений, это позволит несколько сузить пространство поиска. Можно посмотреть в сторону каких-нибудь SMT-солверов.

[Евгений Машеров]

Ну, $3^{10}$ и перебрать можно... А при большем числе какие-то отсечения надо.

[mserg]

Такая задача относится к классу целочисленного нелинейного программирования.
Из готовых пакетов есть вот это:
https://www.coin-or.org/Couenne/
Сие есть

Цитата:

Couenne (Convex Over and Under ENvelopes for Nonlinear Estimation), an Open Source branch&bound algorithm for solving Mixed-Integer Nonlinear Programming (MINLP) problems

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

На задачах с небольшим количеством переменных работает нормально. Если пространство поиска невелико, то, как уже отмечалось выше - проще всего использовать перебор.

Какое-то время назад проблема с использованием была в том, что на вход эта штука принимала AMPL-формат. Но, как показал беглый поиск, появились какие-то пакеты для python. Если заинтересуетесь и получится использовать библиотеку с python - отпишитесь плз.

[intheruder]

Спасибо, попробую