Tired of outsourcing? Get hired at a top product startup from Silicon Valley 🚀
×Закрыть

Гарантований розв’язок нелінійних рівнянь та їх систем

Нещодавно створений в Україні новий вирішувач (solver) interalg відтепер також здатен знаходити розв’язок нелінійних рівнянь (або систем з них) з гарантованою точністю, або достатньо швидко переконуватись, що розв’язок не існує.

Більш докладно дивіться forum.openopt.org/viewtopic.php?id=423

LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

А как по мне, так молодцы! даже в дебиане пакет есть. Хорошо бы еще какой-то туториал по этому делу почитать, а то я кроме GLPK и не знаю ничего. А так если бы для каждого типа задачи из /Problems был кусок теории + примеры кода, да свести все в один красивый pdf... :) тем более что вся эта информация, похоже, в очень разрозненном виде есть на вики, но блин, тяжко так читать по кускам.

Времени и финансирования хватило на то, что есть. Примеры кода для каждой задачи из /Problems приведены, а дублировать теоретический материал, которого и так хватает в интернете, я не вижу смысла.

Звиздежь, не верю!

На чем основывается этот философский камень? Что позволяет ему достигать таких результатов?

Ну не верь себе на здоровье, мне-то что?

Вот если бы ты контрпример привел, где задекларированные в документации свойства солвера не выполняются, тогда это что-то значило бы.

Зачем мне кому то доказывать что земля круглая? В какой документации? Если поменяешь название темы на “Гарантований розв’язок деяких нелінійних рівнянь та їх систем” то поверю.

>Зачем мне кому то доказывать что земля круглая?

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

>В какой документации?

в приведенном сообщении есть линк

>Если поменяешь название темы на “Гарантований розв’язок деяких нелінійних рівнянь та їх систем” то поверю.

Это и так понятно. Можно выбрать такие сложные уравнения и такие большие (порядка 10^300) или маленькие (10^-300) числа, что просто конечная сетка 8-байтного типа float64, используемого в расчетах, не выдержит (хотя, надеюсь, в следующем релизе будет возможность пользоваться и типом float128, что существенно улучшит ситуацию). Кроме того, для типа float64 1+10^-16=1 (из-за округлений), что существенно ограничивает точность.

Алгоритм interalg-а принадлежит к семейству интервальных методов, которые известны уже давно (в гугле полно инфы), и наряду с липшицевыми давно уже решают задачу, упомянутую тобой как “филосовский камень”. Однако из-за чрезвычайно низкой скорости (а иногда и чрезмерных требований к памяти) пользуются ими крайне редко. Придуманные и запрограммированные мной идеи позволили значительно (на порядки) улучшить ситуацию, openopt.org/interalg_bench

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

Та я уже понял, что распинаться ты не любишь.

в приведенном сообщении есть линк

Ответ абсолютно точный и абсолютно бесполезный©, то что ты математик я тоже уже понял.

Алгоритм interalg-а принадлежит к семейству интервальных методов, которые известны уже давно (в гугле полно инфы), и нараду с липшицевыми давно уже решают задачу, упомянутую тобой как «филосовский камень».

В общем случае не решают, но спасибо за обьяснения!

Что понимать под «общим случаем»?

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

* влияют ошибки конечной сетки

* требуемые вычислительные ресурсы (время расчета и память) очень быстро растут от числа переменных (+ зависят также от характера функции, например для липшицевых методов -от величины константы Липшица в рассматриваемой области).

Если есть конкретные притензии — озвучь, а то знаешь ли слово «троль» вполне может быть использовано тролем же.

То что это троллинг сомнений нет.

Но reality_hacker абсолютно прав, заявление звучит очень помпезно, при том что правильно было бы указать ограничения.

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

А можно взглянуть на такие доказательства? А то есть подозрения что в процессе глядения найдуться сильные ограничения на функции вроде дифференцируемости и степени гладкости.

Думаю пока не приняли в печать статью(кстати в каком журнале статья?), никто нам доказательства не покажет.
Но в таких случаях предоставляют другую инфу:
— на каких семинарах/конференциях делались доклады
— есть ли уже положительные рецензии
— сама формулировка ключевых теорем(без доказательства)
— на какие классы функций распространяется данный алгоритм, в каком пространстве, как задается метрика...
и т.д.

а потом уже стоит переходить к обсуждению, а то с таким же успехом можно заявить и о решении проблемы Кеплера))

Пока что я обсуждал только со своим научным руководителем
openopt.org/...ikolayZhurbenko , + в общих чертах объяснил еще 2 сотрудникам отдела оптимизации. Но в нашем отделе задачами такого рода никто раньше не занимался, у нас в основном негладкая оптимизация и задачи на графах, так что никакой рецензии они дать не могут. Статью я еще не дописал, т.к. хочу публиковать вариант с другими ограничениями кроме box-bounds, а это еще не сделано. Классы функций упомянуты в описании солвера — это комбинации из +, -, *, /, pow (**), sin, cos, arcsin, arccos, arctan, sinh, cosh, exp, sqrt, abs, log, log2, log10, floor, ceil (у коммерческого BARON этот список намного меньше), планы на будущее — min, max, 1-D splines, radial-basis functions.
>в каком пространстве, как задается метрика

я не вижу, в чем состоит вопрос к данному алгоритму в этих фразах.

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

Эти доказательства в 2 строчки, основаны на том, что производится деление исходного параллелепипеда на несколько других, и часть из них выбрасывается (там, где точно нет искомого оптимума). Определить это можно либо интервальным анализом, либо при заданной (или как-то динамически оцениваемой) константе Липшица. В обоих случая степень гладкости и дифференцируемость значения не имеют (имеет значение только константа Липшица, и то только для липшицевых, а не интервальных алгоритмов). Читайте документацию BARON, LGO, GANSO и т.п, там эти доказательства присутствуют.

и часть из них выбрасывается (там, где точно нет искомого оптимума).

и как появляется магическое знание что в подгиперкубе нету искомого оптимума?

Знание константы липшица почти такое же сильное ограничение как и знание степени гладкости функции. Вот предположим у меня есть задача f(x) -> мин, где f это куча перемножений матриц експонент и синусов, как мне посчитать константу липшица? Знание константы липшица это вообще распространенный пример из жизни или нет? Думаю нет.

и как появляется магическое знание что в подгиперкубе нету искомого оптимума?

Элементарно — берется значение в центре, находится с максимально возможным достижимым улучшением из цетра (посчитанным как расстояние до вершины умножить на константу Липшица) и сравнивается с лучшем из известных значений в цетрах, посчитанных ранее (иногда добавляется требуемая точность целевой ф-ции, это ускоряет сходимость). Аналогично проводится отсев и в интервальных методах (только там наилучшее известное значение сравнивается с границами функции, полученными интервальным анализом).

В ряде софта, в чатности BARON и LGO, константа Липшица определяется автоматически. По всем вопросам — обращайтесь к их документации, я липшицевыми методами не занимаюсь.

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

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

и ничего отбросить не получится.

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

Если каждая переменная учавствует в функции ровно 1 раз, то интервальная оценка всегда точная.

Мы сейчас обсуждаем твое доказательство в две строчки, так вот из него совсем не очевидно что не может быть подобного случая: берем функцию f(g(x), k(x), x) — суперпозицию двух функций, при чем у этих двух функций в точке x=0 есть точка разрыва второго рода, но за счет суперпозиции ее нету(или есть, но скажем первого рода) у функции f, очевидно что в таком случае интервальная арифметика смело сможет выдать вариацию в -/+ бесконечность и все интервальные подходы накроются медным тазом. То есть твое доказательство имеет смысл(если в нем нет других проблем) только для функций с единичным вхождением каждой переменной и как ты заметил с компактным пространством возможных решений.

я говорил, что провожу доказательство для непрерывных функций, так что с точками разрыва хоть 1-го, хоть 2-го рода разбирайся сам.

Про единичное вхождение — в доказательстве оно не использовалось, это я просто факт привел. Про то, что начальная область локализация решения заключена в боксе lb <= x <= ub — так это и в документации сказано, но это не проблема — можно взять достаточно широкий диапазон, для данного солвера он значим намного меньше, чем, например, для отжига или генетических алгоритмов.

Ты говорил про доказательство правильности интервальных методов в целом безотносительно твоего проекта и документации. Функция f в моем примере может быть непрерывной, дела это не меняет и проблемы с интервальной арифметикой не решает.

А единичное вхождение переменной в твоем доказательстве не позволяло бы мне рассматривать функции типа f(g(x), k(x)).

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

А единичное вхождение переменной в твоем доказательстве не позволяло бы мне рассматривать функции типа f(g(x), k(x)).

Я же ясно сказал — Я НЕ ИСПОЛЬЗУЮ В ДОКАЗАТЕЛЬСТВЕ ЕДИНИЧНОЕ ВХОЖДЕНИЕ! Это просто очень важный факт из теории интервалов, который иногда очень полезен.

Про диапазон — очередная чушь (и кроме того, требование конечных границ присутствует в документации моего и всех других всех солверов, в которых оно требуется). На практике я могу взять (-10^30, 10^30) (или, при желании, еще больше), и в реальных инженерных задачах решение, если оно существует, будет лежать в нем (в моем солвере в пространстве, далеком от решения, при более-менее достаточном качестве интервального прогноза, отсев проходит очень хорошо и практически по экспоненте). А если оно лежит на границе типа float64 (~10^300), то из-за конечной сетки ничего нельзя гарантировать.

В документации моего (и остальных) солверов ясно указано, из каких функций можно составлять целевую. Кроме того, у меня приводится список ситуаций, которые теоретически могут доставить проблемы, в частности наличие нуля одновременно в интервалах числителя и знаменателя дроби. В то же время, на подавляющем числе протестированных примеров даже с наличием подобных ситуаций (например, 1/a с диапазоном а, включающем ноль, или корень из a с диапазоном, включающем отрицательные значения) мой солвер справляется (я пока не знаю теста, где это не работает). В том же приведенном в ссылке примере решения системы из 6 уравнений присутствует log(a+5) с начальной локализацией a in (-10,10), так что тут присутствуют и nan, и inf, однако, как видно по результатам, солвер с этим справляется.

Я же ясно сказал — Я НЕ ИСПОЛЬЗУЮ В ДОКАЗАТЕЛЬСТВЕ ЕДИНИЧНОЕ ВХОЖДЕНИЕ!

А я нигде не говорил что ты это используешь в доказательстве.

Про диапазон — очередная чушь (и кроме того, требование конечных границ присутствует в документации моего и всех других всех солверов, в которых оно требуется). На практике я могу взять (-10^30, 10^30) (или, при желании, еще больше), и в реальных инженерных задачах решение, если оно существует, будет лежать в нем (в моем солвере в пространстве, далеком от решения, при более-менее достаточном качестве интервального прогноза, отсев проходит очень хорошо и практически по экспоненте).

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

В то же время, на подавляющем числе протестированных примеров даже с наличием подобных ситуаций (например, 1/a с диапазоном а, включающем ноль, или корень из a с диапазоном, включающем отрицательные значения) мой солвер справляется (я пока не знаю теста, где это не работает).

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

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

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

Для разных интервальных методов соответственно и доказательства разные. Я же сказал — иди читай документацию интервальных и липшицевых солверов, там все теоремы и соответствующие доказательства приведены, я тут их дублировать не собираюсь.

какие грязные приемы? Кнопка «забанить» на этом форуме как раз и присутствует для того, чтобы убирать флудеров типа тебя, которые предпочитают поболтать вместо того, чтобы самим читать документацию.

Я же сказал — иди читай документацию интервальных и липшицевых солверов, там все теоремы и соответствующие доказательства приведены, я тут их дублировать не собираюсь.

ты такого не сказал, а бросился сочинять свое доказательство «в две строчки» на несостоятельность которого я тебе и указал.

какие грязные приемы? Кнопка «забанить» на этом форуме как раз и присутствует для того, чтобы убирать флудеров типа тебя, которые предпочитают поболтать вместо того, чтобы самим читать документацию.

А помоему у тебя случился батхерт когда я тебе указал на проблемы в твоих рассуждениях.

>ты такого не сказал

Я как минимум дважды сказал:

Читайте документацию BARON, LGO, GANSO и т.п, там эти доказательства присутствуют.

...

> По всем вопросам — обращайтесь к их документации

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

>А помоему у тебя случился батхерт когда я тебе указал на проблемы в твоих рассуждениях.

Это по-твоему, а по настоящему мне твой флуд надоел. Я не вижу смысла продолжать дискуссию с квазиматематиком, который пишет «експонент» (и другие орфографические ошибки), да и по твоим фразам похоже, что «слышал звон, да не знает где он».


Это и так понятно. Можно выбрать такие сложные уравнения и такие большие (порядка 10^300) или маленькие (10^-300) числа, что просто конечная сетка <nobr>8-байтного</nobr> типа float64, используемого в расчетах, не выдержит (хотя, надеюсь, в следующем релизе будет возможность пользоваться и типом float128, что существенно улучшит ситуацию). Кроме того, для типа float64 1+10^-16=1 (из-за округлений), что существенно ограничивает точность.

Если использовать программную эмуляцию float128, которая доступна не везде и не всегда, то почему бы не реализовать свою работу с числами с плавающей запятой через GMP?

В Python есть несколько средств для работы с произвольной точностью, см forum.supercomputer.com.ua/...st122.html#p122
Однако их использование с массивами NumPy, использующимися в interalg, непрооптимизировано (а может, и вообще не будет работать). Кроме того, для существенного ускорения солвера используется Bottleneck (pypi.python.org/...pi/Bottleneck/ (если он установлен), и он скорее всего не поддержит эти типы данных.

В NumPy присутствие/отсутствие типа float128 в железе, на котором оно запущено, определяется автоматически, а с програмными эмуляциями мне не хочется связываться. Кроме того, задачи с такой точностью достаточно редки, и если уже и будет надо — можно просто посчитать на компьютере, где тип float128 поддерживается на аппаратном уровне.

Кроме того, задачи с такой точностью достаточно редки

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

В NumPy присутствие/отсутствие типа float128 в железе, на котором оно запущено, определяется автоматически, а с програмными эмуляциями мне не хочется связываться.

В этом то и весь ньюанс. Аппаратной поддержки float128 нет нигде в современном железе.

>>Кроме того, задачи с такой точностью достаточно редки
>Совсем неверно, таких задач множество.
Я имею в виду процентное соотношение. Для подавляющего большинства инженерно-технических задач точность 10^-15 вполне приемлема.
На любом железе упомянутые пакеты используют свои очень высокоуровневые (и соответственно, очень медленные) функции для обработки этих типов данных (произвольной точности), тогда как NumPy просто смотрит, есть ли поддержка float128 на уровне команд процессора, и если нет — то тип float128 просто отсутстует в этом Python-модуле (нельзя импортировать из него). Соответственно, проверять можно так:
import numpy
’float128′ in dir(numpy) или
hasattr(numpy,’float128′) или

’float128′ in numpy.__dict__

Ну для крайніх випадків можна взагалі-то довгу арифметику заюзати, типу BigDecimal в джаві

Подписаться на комментарии