Comments 28
А не было ли идеи применять другие способы решения многопараметрических уравнений, кроме метода Ньютона? Например, методы Монте-Карло, в частности, метод отжига? Они же прямо просятся сюда.
Алгоритм имитации отжига не гарантирует нахождения минимума функции, однако при правильной политике генерации случайной точки в пространстве X, как правило, происходит улучшение начального приближения.
Шило на мыло?
Одно из преимуществ методов Монте-Карло — простота реализации. В статье вы пишите, что декомпозиция задачи, которую приходится делать для оптимизации — это отдельная аналитическая работа. А результат работы малопригоден если, например, требуется расширить область применения задачи. В случае с ММК, задача легко расширяется на другие области. И можно представить решение не только геометрических уравнений для Эскиза, но и включить в систему уравнений, например, параметр массы. Так чтобы при поиске решения, одновременно решалась задача ее минимизации. Не говоря уже про переход от двухмерных случаев к трехмерным.
Основная работа, которая проводится при применении ММК, это как раз поиск «правильной политики генерации случайной точки в пространстве Х» и снижение вычислительной сложности решаемой системы уравнений. Но, по моему опыту, даже без серьезной проработки, чаще всего можно получить приемлемый результат за адекватное машинное время.
Еще одним из преимуществ ММК является легкость массштабирования и распараллеливания вычислений. Учитывая нынешний вектор развития средств вычисления, это актуально.
Конечно, за все надо платить, и из преимуществ вытекают и недостатки. Основной — потребляемые вычислительные ресурсы. По сути, все ММК, это оптимизированные варианты полного перебора. Тем не менее, инженерные задачи, которые вы описываете, вполне решаемы за приемлемое время.
Одно из преимуществ методов Монте-Карло — простота реализации.
Пожалуй, соглашусь. Я прочитал вот эту статью https://habrahabr.ru/post/209610/, там все доходчиво описано. Но суть в том, как я понял, что ММК применяют для решения NP сложных задач, например. Поэтому там принципиально не имеет значения, сколько вычислительной мощности ты вкидываешь — это все равно будет меньше, чем полный перебор. Метод же Ньютона при имении начального приближения (грубый чертеж), сходится очень быстро, за малое число итераций. А вот если он не сошелся, или, например, стоит задача без начальных приближений параметров построить чертеж, имея только набор точек и констрейны между ними — вот тогда уже можно начать "кидать кости". Тут я, пожалуй соглашусь, что ММК сделает решение этой задачи возможной. Но тут нужно делать просто так: мы кидаем параметры в случайное положение, решаем сошлось все? готово! иначе — перекидываем кости тех парамеров, замешанных в уравнения, которые не сошлись… короче, делаем что-то. Либо нужно внутри метода Ньютона иногда, с некоторой вероятностью, шагать не в направлении решения, а в произвольном прыжке…
В статье вы пишите, что декомпозиция задачи, которую приходится делать для оптимизации — это отдельная аналитическая работа. А результат работы малопригоден если, например, требуется расширить область применения задачи.
Да, но можно не решать задачу декомпозиции, просто забив на нее :) Сейчас есть алгоритмы, которые имеют меньшую вычислительную сложность, работающие на разреженных матрицах.
Но, по моему опыту, даже без серьезной проработки, чаще всего можно получить приемлемый результат за адекватное машинное время.
Тут зависит от того, что рассматривать в качестве "адекватного машинного времени" секунды? минуты? часы? Метод Ньютона работает "realtime" даже на большом количестве ограничений. Мне слабо верится, что от ММК можно добиться такой скорости работы
Я верю, что одним из вариантов решения проблемы несогласованности уравнений может служить формирование системы уравнений в однородной системе координат, с использованием методов проективной геометрии, но это умозаключение является предчувствием
Мыслите в правильном направлении, но проективная геометрия тут не при чем. Эта проблема решается использованием аффинно-инвариантных методов, таких как метод Ньютона и BFGS. Есть отдельные методы, которые борются только с разной размерностью координат. Самый известный из них, это Adam.
Вообще решение систем нелинейных уравнений и нелинейная оптимизация — активно развивающаяся область. К примеру, менее чем 10 лет назад, было обнаружено, что задачу посадки на Марс можно свести к выпуклой оптимизации — Minimum-Landing-Error Powered-Descent Guidance for Mars Landing Using Convex Optimization. SpaceX использует что-то похожее для более сложной задачи посадки ракет на Землю — Autonomous Precision Landing of Space Rockets (статья начинается на 15 странице), но деталей, к сожалению, не раскрывает.
Из Open Source библиотек решения нелинейных уравнений советую глянуть на проект со странным названием COIN-OR. Еще есть проприетарная библиотека SNOPT, но есть открытое описание используемого там алгоритма. Для выпуклых задач есть CVX, CVXPY, CVXOPT и CVXGEN.
Из книжек мне понравилась Convex Optimization. Stephen Boyd and Lieven Vandenberghe. Для общего случая нелинейной оптимизации/решения систем нелинейных уравнений я пока читал только разрозненные статьи.
Спасибо большое за ссылки. Если уж продолжать о предчувствиях, то мое воображение иногда рисует картинки, на которых изображены миллион-ядерные чипы, каждое ядро которого — аппаратная реализация метода Ньютона (или чего-то такого). Ну а используются они… Правильно, для аппроксимации многомерных функций (читай: обучения нейронных сетей). Только все это галлюцинации, в эту тему я пока не вник.
Да, конечно же я в курсе про эти базисы Грёбнера. Только вот насколько я помню, там есть некоторые ограничения. Там вроде только полиномы раскладываются на них, а произвольные функции… Мне сложно представить, как это возможно. Хотя, что уж там, и про полиномы мне представить не проще. Но я был бы вам благодарен, если бы вы дали свою краткую характеристику на эту тему, мне было бы очень интересно понять, насколько реально реализовать, скажем подобный решатель геометрических ограничений с использованием этого метода. Если необходимо, я предоставлю дополнительную информацию, хотя примерно о типе уравнений можно судить по предыдущей статье.
Правда теоретическая сложность решения не будет радовать, двойная экспонента от числа переменных, если грубо сказать.
Даже не знаю, как тут оценить. С одной стороны, мы тратим много времени (двойная экспонента — это как?). С другой стороны, мы получает аналитически-точное решение (В каком виде?). Т.е. больше нам ничего вычислять не надо, мы (грубо говоря) получили f(p0...px) — векторную функцию (значения неизвестных параметров) от векторного аргумента (степени свободы). Можем крутить ее, быстро вычисляя результат. Я тут даже не понимаю, с какой стороны подойти, я когда все это читал, вообще не понял, в каком виде я хотел бы получить ответ от этой штуки. Исходная задача обычно формулируется так: есть несколько неизвестных, которые мы считаем координатам точек, и есть уравнения в символьном виде, которые их связывают (в основном, теорема Пифагора для длин, равенство скалярного произведения для углов). Мне было бы очень интересно посмотреть, как это считается для построения достижимой области для простого манипулятора, т.к. я даже не понимаю, что следует ожидать от этого метода, и чего не следует.
Кстати, как дилетант использования подобных приложений:
1. Подходит ли для проектирования каркасного дома (и из любых других материалов)
2. Подходит ли для проектирования станков и автоматизации
3. Готовую модель для визуализации куда лучше переносить
- Думаю, с этой проблемой SolveSpace справится без проблем. Я имею ввиду, сделать разметку досок, панелей и прочее. Солвер и массивы в режиме assembly тут вытаскивают.
- Несложные механические детали можно (например, детали 3d принтера или CNC-станка), сборки, моделирование механики — без проблем. Единственное, что сейчас является проблемой — это моделирование сложных поверхностей (скругления, фаски, заметание, резьба и т. д.)
- Готовую модель можно гнать через obj или stl в Blender, например, да куда угодно. Есть даже экспорт в STEP, но он неясно насколько хорошо работает. Есть еще вариант сразу записывать pdf или svg, можно делать чертежи сборочные и т. д. Есть экспорт на web-страницу в качестве интерактивной 3d модели
фактически привязать к этому уже бизнес-процессы и будет все у меня документация :) верно? в добавок на все CNC сразу же и нужные модельки
Ну вы описали явно систему, выходящую за рамки этой программы. Что вы описали — это сейчас называют модными словами BIM и PLM. Это вам нужно к лидерам рынка обращаться (однажды я работал в таком стартапе, но фирма лопнула). SolveSpace — это не более, чем программа моделирования простейших деталек для 3д печати, огромные промышенные сборки она не потянет (пока в нее развитие кто-нибудь не вложит много денег, примеры есть).
Вполне подойдет, вот только нужно будет снижать кол-во треугольников иначе начинаются жесткие тормоза (по крайне-мере в линуксе). Да даже когда снизишь их кол-во всё равно тормоза, даже на простейшей модели (в реальном масштабе). Может в окошках по другому, попробуйте.
>Подходит ли для проектирования станков и автоматизации
Подходит, но придется столкнуться с костылями в виде создания 2D каркаса нужной вам механики и цепляние на этот каркас деталей в 3D, причем иногда параметрический решатель не хочется их цеплять и постоянно ругается. Но если набить руку, можно научиться обходить эти проблемы. И опять же жесткие тормоза, когда пытаешься подвигать созданную механику в 3D. Но опять же — линукс, за винды не скажу.
В целом, мне программа нравится своей миниатюрностью, простотой и нативной работой в линуксе, если бы я сидел на виндах, то скорее всего спиратил SolidWorks.
Но недавно нашел вот такое решение www.tflexcad.ru/download/t-flex-cad-free С первого взгляда очень понравилось. Плюс возможность загрузить бесплатную версию для некоммерческих целей. А для коммерческих она также стоит вполне разумных денег.
Например, я перешел на SolveSpace из Tinkercad, т.к. мне потребовалась относительно сложная механика и как оказалось в SolveSpace многие вещи делать гораздо проще, чем в Tinkercad. Так что если кому-то нужно именно что-то уровня Tinkerpad, то SolveSpace просто идеальный выбор.
Но недавно нашел вот такое решение www.tflexcad.ru/download/t-flex-cad-free
Да, очень милый факт: у них даже решателя нет в том виде, в котором я о нем говорю. А делать можно все!
Параметрическое моделирование в САПР SolveSpace: «Неисповедимы пути Решателя» или «Червоточины Ньютона»