Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.
Нещодавно створений в Україні новий вирішувач (solver) interalg відтепер також здатен знаходити розв’язок нелінійних рівнянь (або систем з них) з гарантованою точністю, або достатньо швидко переконуватись, що розв’язок не існує.
Більш докладно дивіться forum.openopt.org/viewtopic.php?id=423
А как по мне, так молодцы! даже в дебиане пакет есть. Хорошо бы еще какой-то туториал по этому делу почитать, а то я кроме GLPK и не знаю ничего. А так если бы для каждого типа задачи из /Problems был кусок теории + примеры кода, да свести все в один красивый pdf... :) тем более что вся эта информация, похоже, в очень разрозненном виде есть на вики, но блин, тяжко так читать по кускам.
Времени и финансирования хватило на то, что есть. Примеры кода для каждой задачи из /Problems приведены, а дублировать теоретический материал, которого и так хватает в интернете, я не вижу смысла.
На чем основывается этот философский камень? Что позволяет ему достигать таких результатов?
Вот если бы ты контрпример привел, где задекларированные в документации свойства солвера не выполняются, тогда это что-то значило бы.
Зачем мне кому то доказывать что земля круглая? В какой документации? Если поменяешь название темы на “Гарантований розв’язок деяких нелінійних рівнянь та їх систем” то поверю.
Правильно, зачем? Вот и я тут распинаться не буду, тем более статья с алгоритмом еще не опубликована.
>В какой документации?в приведенном сообщении есть линк
>Если поменяешь название темы на “Гарантований розв’язок деяких нелінійних рівнянь та їх систем” то поверю.
Это и так понятно. Можно выбрать такие сложные уравнения и такие большие (порядка 10^300) или маленькие (10^-300) числа, что просто конечная сеткаАлгоритм interalg-а принадлежит к семейству интервальных методов, которые известны уже давно (в гугле полно инфы), и наряду с липшицевыми давно уже решают задачу, упомянутую тобой как “филосовский камень”. Однако из-за чрезвычайно низкой скорости (а иногда и чрезмерных требований к памяти) пользуются ими крайне редко. Придуманные и запрограммированные мной идеи позволили значительно (на порядки) улучшить ситуацию, openopt.org/interalg_bench
Правильно, зачем? Вот и я тут распинаться не буду, тем более статья с алгоритмом еще не опубликована.
Та я уже понял, что распинаться ты не любишь.
в приведенном сообщении есть линк
Ответ абсолютно точный и абсолютно бесполезный©, то что ты математик я тоже уже понял.
Алгоритм interalg-а принадлежит к семейству интервальных методов, которые известны уже давно (в гугле полно инфы), и нараду с липшицевыми давно уже решают задачу, упомянутую тобой как «филосовский камень».
В общем случае не решают, но спасибо за обьяснения!
Что понимать под «общим случаем»?
Для этих методов математически все доказано, поэтому должны решать, другое дело, что
* влияют ошибки конечной сетки
* требуемые вычислительные ресурсы (время расчета и память) очень быстро растут от числа переменных (+ зависят также от характера функции, например для липшицевых методов -от величины константы Липшица в рассматриваемой области).
Если есть конкретные притензии — озвучь, а то знаешь ли слово «троль» вполне может быть использовано тролем же.
Но reality_hacker абсолютно прав, заявление звучит очень помпезно, при том что правильно было бы указать ограничения.
Ну у меня уже давно появились смутные подозрения что любые дискуссии релевантные проблемам программирования на этом форуме это троллинг и офтопик. А вот такие клевые темы как «какие зарплаты», «с чего начать», «кто возьмет работать за еду если я ничего не знаю и не умею», «как мигрировать с пэхопэ на джаву» — это то что сегодня реально интересует целевую аудиторию.
А можно взглянуть на такие доказательства? А то есть подозрения что в процессе глядения найдуться сильные ограничения на функции вроде дифференцируемости и степени гладкости.
а потом уже стоит переходить к обсуждению, а то с таким же успехом можно заявить и о решении проблемы Кеплера))
я не вижу, в чем состоит вопрос к данному алгоритму в этих фразах.
Речь шла о доказательстве достижимости результата с заданной точностью для интервальных методов, для этого непояввившаяся статья не нужна.
Эти доказательства в 2 строчки, основаны на том, что производится деление исходного параллелепипеда на несколько других, и часть из них выбрасывается (там, где точно нет искомого оптимума). Определить это можно либо интервальным анализом, либо при заданной (или как-то динамически оцениваемой) константе Липшица. В обоих случая степень гладкости и дифференцируемость значения не имеют (имеет значение только константа Липшица, и то только для липшицевых, а не интервальных алгоритмов). Читайте документацию BARON, LGO, GANSO и т.п, там эти доказательства присутствуют.
и часть из них выбрасывается (там, где точно нет искомого оптимума).
и как появляется магическое знание что в подгиперкубе нету искомого оптимума?
Знание константы липшица почти такое же сильное ограничение как и знание степени гладкости функции. Вот предположим у меня есть задача f(x) -> мин, где f это куча перемножений матриц експонент и синусов, как мне посчитать константу липшица? Знание константы липшица это вообще распространенный пример из жизни или нет? Думаю нет.
Элементарно — берется значение в центре, находится с максимально возможным достижимым улучшением из цетра (посчитанным как расстояние до вершины умножить на константу Липшица) и сравнивается с лучшем из известных значений в цетрах, посчитанных ранее (иногда добавляется требуемая точность целевой ф-ции, это ускоряет сходимость). Аналогично проводится отсев и в интервальных методах (только там наилучшее известное значение сравнивается с границами функции, полученными интервальным анализом).и как появляется магическое знание что в подгиперкубе нету искомого оптимума?
В ряде софта, в чатности BARON и LGO, константа Липшица определяется автоматически. По всем вопросам — обращайтесь к их документации, я липшицевыми методами не занимаюсь.
Только в общем случае у тебя лучшее найденное значение может попадать в степень вариации функции определенной интервальным анализом во всех подгиперкубах, и ничего отбросить не получится. Это происходит потому что интервальная арифметика далеко не всегда дает правильную оценку вариации для достаточно сложных функций, и я так понимаю как раз это строго доказано.
В данной проблематике вообще нету универсальных решений, в зависимости от специфики задачи собирают пазл из разных методов.
тогда деление продолжается. Для непрерывных функций, ограниченных на компакте (первоначальной локализации), при достаточно малых длинах ребер параллепипедов разница между верхней и нижней границами интервала, посчитанном в нем, будет меньше любого положительного эпсилона. Поэтому со временем он или уточнит оценку, или отсеется (в соответствии с критерием требуемой точности — фиксированным положительным числом). Другое дело, что для достаточно сложных задач число таких параллелепипедов может не влазить в память компьютера, тогда некоторые приходится отбрасывать по каким-либо критериям.и ничего отбросить не получится.
Если каждая переменная учавствует в функции ровно 1 раз, то интервальная оценка всегда точная.
Мы сейчас обсуждаем твое доказательство в две строчки, так вот из него совсем не очевидно что не может быть подобного случая: берем функцию f(g(x), k(x), x) — суперпозицию двух функций, при чем у этих двух функций в точке x=0 есть точка разрыва второго рода, но за счет суперпозиции ее нету(или есть, но скажем первого рода) у функции f, очевидно что в таком случае интервальная арифметика смело сможет выдать вариацию в -/+ бесконечность и все интервальные подходы накроются медным тазом. То есть твое доказательство имеет смысл(если в нем нет других проблем) только для функций с единичным вхождением каждой переменной и как ты заметил с компактным пространством возможных решений.
Про единичное вхождение — в доказательстве оно не использовалось, это я просто факт привел. Про то, что начальная область локализация решения заключена в боксе 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?
В NumPy присутствие/отсутствие типа float128 в железе, на котором оно запущено, определяется автоматически, а с програмными эмуляциями мне не хочется связываться. Кроме того, задачи с такой точностью достаточно редки, и если уже и будет надо — можно просто посчитать на компьютере, где тип float128 поддерживается на аппаратном уровне.
Кроме того, задачи с такой точностью достаточно редки
Совсем неверно, таких задач множество. И наличие библиотек для работы с такой точностью есть элементарное подтверждение этому.
В NumPy присутствие/отсутствие типа float128 в железе, на котором оно запущено, определяется автоматически, а с програмными эмуляциями мне не хочется связываться.
В этом то и весь ньюанс. Аппаратной поддержки float128 нет нигде в современном железе.
’float128′ in numpy.__dict__
Ну для крайніх випадків можна взагалі-то довгу арифметику заюзати, типу BigDecimal в джаві
Sergiy Matusevych
reality_hacker
reality_hacker
Illia Khabibrakhmanov
Bogdan Shyiak
Edelweiss
reality hacker
Mike Gorchak
Dmytro Dziuma
34 коментарі
Додати коментар Підписатись на коментаріВідписатись від коментарів