2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5  След.
 
 Re: Весьма нетривиальная оптимизация
Сообщение29.11.2018, 20:43 


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

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

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

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

 Профиль  
                  
 
 Re: Весьма нетривиальная оптимизация
Сообщение10.12.2018, 14:34 


25/02/11
123
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$ я не попадаю. Также попробовал транспонировать матрицу поворота и потом тоже вычесть вектор смещения - снова не попал.
Я предполагаю что это невозможно и вращать надо вокруг собственных осей и тогда все сойдется. Но как их правильно найти?

 Профиль  
                  
 
 Re: Весьма нетривиальная оптимизация
Сообщение10.12.2018, 17:01 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Весьма нетривиальная оптимизация
Сообщение10.12.2018, 17:15 


25/02/11
123
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}$

 Профиль  
                  
 
 Re: Весьма нетривиальная оптимизация
Сообщение10.12.2018, 17:40 
Заслуженный участник


18/01/15
3075
_genius_ в сообщении #1360244 писал(а):
Не обращайте внимания, это всего лишь эскиз на скорую руку, на деле отрезки одного цвета имеют одинаковую длину
Я так и подумал, вообще говоря. Однако совет на будущее (для диссертаций, статей, и т.д.): такие вещи надо как-то оговаривать, иначе читатель впадет в недоумение. (Типа: "предупредим читателя, что отрезки $AB$ и $A_1B_1$ на правом и левом изображениях имеют одинаковую длину, а на рисунках изображены разными из типографских соображений", или десятком других аналогичных способов).

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

 Профиль  
                  
 
 Re: Весьма нетривиальная оптимизация
Сообщение10.12.2018, 19:16 
Заслуженный участник


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

Рассмотрим обычную прямую, т.е. ${\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$.

 Профиль  
                  
 
 Re: Весьма нетривиальная оптимизация
Сообщение10.12.2018, 20:11 


25/02/11
123
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$
Коммутативно как я и думал.

 Профиль  
                  
 
 Re: Весьма нетривиальная оптимизация
Сообщение10.12.2018, 20:28 
Заслуженный участник


18/01/15
3075
_genius_ в сообщении #1360292 писал(а):
Но думаю вам виднее
Это действительно так. :-)
_genius_ в сообщении #1360292 писал(а):
для меня это сюрприз
Тем не менее, так (некоммутативно) и должно быть. (И это говорит о том, что вопросы я Вам задал не зря).

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

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

 Профиль  
                  
 
 Re: Весьма нетривиальная оптимизация
Сообщение10.12.2018, 20:52 


25/02/11
123
vpb в сообщении #1360298 писал(а):
_genius_ в сообщении #1360292 писал(а):
Но думаю вам виднее
Это действительно так. :-)
_genius_ в сообщении #1360292 писал(а):
для меня это сюрприз
Тем не менее, так (некоммутативно) и должно быть. (И это говорит о том, что вопросы я Вам задал не зря).

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

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


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

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

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

 Профиль  
                  
 
 Re: Весьма нетривиальная оптимизация
Сообщение10.12.2018, 21:22 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Весьма нетривиальная оптимизация
Сообщение10.12.2018, 21:30 
Заслуженный участник


20/08/14
11067
Россия, Москва

(Оффтоп)

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

 Профиль  
                  
 
 Re: Весьма нетривиальная оптимизация
Сообщение10.12.2018, 21:37 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Весьма нетривиальная оптимизация
Сообщение10.12.2018, 21:40 


25/02/11
123
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. Почитайте, полезно. В Вашей ситуации геометрию вообще понимать нужно.

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

 Профиль  
                  
 
 Re: Весьма нетривиальная оптимизация
Сообщение10.12.2018, 21:50 
Заслуженный участник


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

-- 10.12.2018, 20:55 --

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

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

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

-- 10.12.2018, 21:00 --

_genius_ в сообщении #1360317 писал(а):
возможно ли это в принципе
Конечно, возможно. Только надо сначала разобраться, насколько Вы предмет понимаете. А то я напишу что-то, а Вам непонятно будет.

 Профиль  
                  
 
 Re: Весьма нетривиальная оптимизация
Сообщение10.12.2018, 22:11 


25/02/11
123
vpb в сообщении #1360318 писал(а):
Ну, что я могу сразу сказать с несомненностью --- это то, что вообще не следует что-либо делать тупо ... :-)

-- 10.12.2018, 20:55 --

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

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

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

-- 10.12.2018, 21:00 --

_genius_ в сообщении #1360317 писал(а):
возможно ли это в принципе
Конечно, возможно. Только надо сначала разобраться, насколько Вы предмет понимаете. А то я напишу что-то, а Вам непонятно будет.


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 72 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Gg322


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group