Весьма нетривиальная оптимизация

[alex55555]

vpb в сообщении #1357357 писал(а):

Так тогда, вообще говоря, $f(\Phi)$ не ограничено сверху, и как ставить вопрос о максимуме ? Конкретно, если есть две точки $x_i$ и $y_j$ такие, что (а) можно $x_i$ непосредственно прислонить к $y_j$, для подходящего $\Phi$, и (б) $f(x_i)-g(y_j)>0$ , то $f(\Phi)$ не ограничено (если их прислонить друг к другу, то вообще обращается в плюс бесконечность).

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

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

Интереснее, что сделать тогда критерием оптимума. Например - наибольшая разница энергии в пределах заданного сдвига. Но без бесконечностей, понятно.

[_genius_]

vpb в сообщении #1357558 писал(а):

Есть такая возможность ускорить вычисление $f(\Phi)$. Рассмотрим функции от $x$ и $y$:

$$ p(x)=\sum_{j=1}^M h(d(x,y_j))g(y_j)\,, \qquad q(y)=\sum_{i=1}^N h(d(x_i,y)) f(x_i)\,.$$

Тогда легко видеть, что

$$f(\Phi)=\sum_{j=1}^Mq(\Phi y_j)-\sum_{i=1}^Np(\Phi^{-1}x_i)$$

(следует учесть, что $d(x,\Phi y)=d(\Phi^{-1}x,y)$. Это подсказывает такой путь: затабулировать $p(x)$, $q(y)$ достаточно
плотно по ${\mathbb R}^3$, а потом пользоваться указанными соотношениями (интерполируя $p$ и $q$ из близлежащих затабулированных точек). Тогда вычисление $f(\Phi)$ будет требовать не миллиарда операций, а порядка ста тысяч.

Реализовал вашу идею с сетками. Попробую описать в двумерном виде как я выбирал интервалы, благо принцип тот же:



Вокруг обоих тел рисуется по ящику (мин./макс. $x, y, z$), затем ищутся их диагонали. Диагональ первого ящика прибавляется со всех сторон ко второму, а диагональ второго ящика со всех сторон к первому.

И затем уже для этих внешних ящиков табулируются $q$ (вокруг первого расширенного диагоналями второго) и $p$ (вокруг второго расширенного диагоналями первого).

По идее этих границ должно быть более чем достаточно.

Однако теперь единственная проблема это найти $\Phi^{-1}$, я не понимаю как это сделать для поворотов.

Допустим второе тело вращается вокруг оси $x$ на 180 градусов, не своей какой-то центральной оси, а обычной, общей, если можно так выразиться. А затем смещается в угол ящика для $q$.

Возможно ли для этой ситуации найти $\Phi^{-1}$ для первого тела? Если тупо повернуть на -180 вокруг общей оси $x$ и затем вычесть тот же вектор смещения который прибавялся ко второму телу, в ящик для $p$ я не попадаю. Также попробовал транспонировать матрицу поворота и потом тоже вычесть вектор смещения - снова не попал.
Я предполагаю что это невозможно и вращать надо вокруг собственных осей и тогда все сойдется. Но как их правильно найти?

[vpb]

Рад, что Вам мой совет пригодился.

Давайте сначала кое-что проясним по первой половине Вашего сообщения.
1) Вы предполагаете, неявно, что максимум будет достигаться при таком положении, когда тела весьма близки, касаются или почти касаются друг друга ?
2) Почему диагонали во внутренних ящиках оказываются намного длиннее, чем отрезки того же цвета во внешних ящиках ? Если Вы действуете, исходя из предположения 1), то должны быть одинаковой длины (вы их, наверное, напополам делите?).

[_genius_]

vpb в сообщении #1360241 писал(а):

Рад, что Вам мой совет пригодился.

Давайте сначала кое-что проясним по первой половине Вашего сообщения.
1) Вы предполагаете, неявно, что максимум будет достигаться при таком положении, когда тела весьма близки, касаются или почти касаются друг друга ?
2) Почему диагонали во внутренних ящиках оказываются намного длиннее, чем отрезки того же цвета во внешних ящиках ? Если Вы действуете, исходя из предположения 1), то должны быть одинаковой длины (вы их, наверное, напополам делите?).

1) Да, именно так, я уверен в этом и поэтому выбрал $h = e^{-d}$ ну или наоборот, из-за такого выбранного мной $h$ максимум достигается именно при касании
2) Не обращайте внимания, это всего лишь эскиз на скорую руку, на деле отрезки одного цвета имеют одинаковую длину: $\sqrt{(x_{\max}-x_{\min})^2 + (y_{\max}-y_{\min})^2 + (z_{\max}-z_{\min})^2}$

[vpb]

_genius_ в сообщении #1360244 писал(а):

Не обращайте внимания, это всего лишь эскиз на скорую руку, на деле отрезки одного цвета имеют одинаковую длину

Я так и подумал, вообще говоря. Однако совет на будущее (для диссертаций, статей, и т.д.): такие вещи надо как-то оговаривать, иначе читатель впадет в недоумение. (Типа: "предупредим читателя, что отрезки $AB$ и $A_1B_1$ на правом и левом изображениях имеют одинаковую длину, а на рисунках изображены разными из типографских соображений", или десятком других аналогичных способов).

Что до оставшейся части, мне надо немного подумать.

[vpb]

Я думаю, во избежание недоразумений надо освежить кое-какие чисто математические понятия. Например, понятия "отображение", "преобразование", "композиция", "обратное преобразование" (а позже доберемся до движений и ортогональной группы).

Рассмотрим обычную прямую, т.е. ${\mathbb R}$, множество всех действительных чисел. Рассмотрим на ${\mathbb R}$ преобразование $\varphi$, которое переводит каждую точку $x\in{\mathbb R}$ в другую, а именно в точку $x'=\varphi(x)=-2x+3$. Ответьте (если сможете) на вопросы (если они понятны):
(1) куда $\varphi$ переводит точку $2$ ?
(2) какая точка переходит в $7$ ?
(3) как записать формулой обратное преобразование $\varphi^{-1}$ ?

Пусть $\alpha$ --- другое преобразование, $\alpha(x)=3x-2$. Найдите (запишите формулой) преобразования $\beta=\alpha\circ\varphi$ и $\gamma=\varphi\circ\alpha$.

[_genius_]

vpb в сообщении #1360272 писал(а):

Я думаю, во избежание недоразумений надо освежить кое-какие чисто математические понятия. Например, понятия "отображение", "преобразование", "композиция", "обратное преобразование" (а позже доберемся до движений и ортогональной группы).

Рассмотрим обычную прямую, т.е. ${\mathbb R}$, множество всех действительных чисел. Рассмотрим на ${\mathbb R}$ преобразование $\varphi$, которое переводит каждую точку $x\in{\mathbb R}$ в другую, а именно в точку $x'=\varphi(x)=-2x+3$. Ответьте (если сможете) на вопросы (если они понятны):
(1) куда $\varphi$ переводит точку $2$ ?
(2) какая точка переходит в $7$ ?
(3) как записать формулой обратное преобразование $\varphi^{-1}$ ?

Пусть $\alpha$ --- другое преобразование, $\alpha(x)=3x-2$. Найдите (запишите формулой) преобразования $\beta=\alpha\circ\varphi$ и $\gamma=\varphi\circ\alpha$.

Я пока плохо понимаю, к чему вы клоните, т.к. вращений в одномерном пространстве нет, а проблемы у меня именно с ними. Но думаю вам виднее.
1) $x' = -1$
2) $x = -2$
3) $\varphi^{-1}(x') = -\frac{1}{2}\cdot(x'-3)$
4) $\beta=\alpha\circ\varphi = 3\cdot(-2x+3) - 2 = -6x+7$
5) $\gamma=\varphi\circ\alpha = -2\cdot(3x-2) + 3 = -6x+7$
Коммутативно как я и думал.

[vpb]

_genius_ в сообщении #1360292 писал(а):

Но думаю вам виднее

Это действительно так.

_genius_ в сообщении #1360292 писал(а):

для меня это сюрприз

Тем не менее, так (некоммутативно) и должно быть. (И это говорит о том, что вопросы я Вам задал не зря).

1) Понятен ли смысл формулы $d(\Phi x, y)=d(x, \Phi^{-1}y)$ ? Как это доказать, если понятно ?

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

[_genius_]

vpb в сообщении #1360298 писал(а):

_genius_ в сообщении #1360292 писал(а):

Но думаю вам виднее

Это действительно так.

_genius_ в сообщении #1360292 писал(а):

для меня это сюрприз

Тем не менее, так (некоммутативно) и должно быть. (И это говорит о том, что вопросы я Вам задал не зря).

1) Понятен ли смысл формулы $d(\Phi x, y)=d(x, \Phi^{-1}y)$ ? Как это доказать, если понятно ?

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

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

1) Понятен, но чисто интуитивно. Доказать не смогу.

2) Если вращения нет, то надо просто прибавить вектор этого движения к каждой точке тела.

[vpb]

_genius_ в сообщении #1360305 писал(а):

А потом пересчитал и оказалось коммутативно

Да, Вы правы. Я ожидал некоммутативности, поэтому и ошибся. Это такое удивительное совпадение. (Ведь коэффициенты я написал чисто наобум !) Если взять вместо $-2$ любое другое число, например $\alpha(x)=3x-4$, то будет некоммутативно.

[Dmitriy40]

(Оффтоп)

А может сразу перейти к матрицам преобразования координат, там матрица поворота на произвольный угол по любой из осей известна? Берём произведение 4-х матриц (трёх поворотов и сдвига), называем $\Phi$ и тупо берём обратную матрицу по правилам математики - и получаем желаемую $\Phi^{-1}$.
Для практических целей вполне можно взять готовый алгоритм и не выводить его заново с доказательством что он даёт именно нужное решение.

[vpb]

Про композицию перемещений, и про то, что преобразование, обратное к перемещению --- тоже перемещение, когда-то учили в школе (в 1970х-1980х годах, кажется). В 7 классе. См. учебник Колмогоров, Семенович, Черкасов, Геометрия 6--8. Почитайте, полезно. В Вашей ситуации геометрию вообще понимать нужно.

[_genius_]

Dmitriy40 в сообщении #1360313 писал(а):

(Оффтоп)

А может сразу перейти к матрицам преобразования координат, там матрица поворота на произвольный угол по любой из осей известна? Берём произведение 4-х матриц (трёх поворотов и сдвига), называем $\Phi$ и тупо берём обратную матрицу по правилам математики - и получаем желаемую $\Phi^{-1}$.
Для практических целей вполне можно взять готовый алгоритм и не выводить его заново с доказательством что он даёт именно нужное решение. ;-)

Обратная матрица к матрице поворота находится банальным транспонированием. Про матрицы сдвига я слышу впервые в жизни.

Ну и я уже пробовал "тупо" и мои ожидания не оправдались:

_genius_ в сообщении #1360210 писал(а):

Допустим второе тело вращается вокруг оси $x$ на 180 градусов, не своей какой-то центральной оси, а обычной, общей, если можно так выразиться. А затем смещается в угол ящика для $q$.

Возможно ли для этой ситуации найти $\Phi^{-1}$ для первого тела? Если тупо повернуть на -180 вокруг общей оси $x$ и затем вычесть тот же вектор смещения который прибавялся ко второму телу, в ящик для $p$ я не попадаю. Также попробовал транспонировать матрицу поворота и потом тоже вычесть вектор смещения - снова не попал.?

-- Пн дек 10, 2018 21:43:19 --

vpb в сообщении #1360316 писал(а):

Про композицию перемещений, и про то, что преобразование, обратное к перемещению --- тоже перемещение, когда-то учили в школе (в 1970х-1980х годах, кажется). В 7 классе. См. учебник Колмогоров, Семенович, Черкасов, Геометрия 6--8. Почитайте, полезно. В Вашей ситуации геометрию вообще понимать нужно.

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

[vpb]

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

-- 10.12.2018, 20:55 --

_genius_ в сообщении #1360305 писал(а):

Если вращения нет

А если есть ? Есть формула, учили/знаете ли ?

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

-- 10.12.2018, 21:00 --

_genius_ в сообщении #1360317 писал(а):

возможно ли это в принципе

Конечно, возможно. Только надо сначала разобраться, насколько Вы предмет понимаете. А то я напишу что-то, а Вам непонятно будет.

[_genius_]

vpb в сообщении #1360318 писал(а):

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

-- 10.12.2018, 20:55 --

_genius_ в сообщении #1360305 писал(а):

Если вращения нет

А если есть ? Есть формула, учили/знаете ли ?

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

-- 10.12.2018, 21:00 --

_genius_ в сообщении #1360317 писал(а):

возможно ли это в принципе

Конечно, возможно. Только надо сначала разобраться, насколько Вы предмет понимаете. А то я напишу что-то, а Вам непонятно будет.

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