Нахождение локального экстремума функций

[Punisher174]

Здравствуйте.
Есть система из двух нелинейных функций: $f(x, y)$ и $g(x, y)$, которые требуется минимизировать.
Как находить экстремумы для одной функции - умею, для систем - не сталкивался.
Подскажите, пожалуйста, какие-нибудь методы.
Спасибо.

[Otta]

Punisher174 в сообщении #745078 писал(а):

Есть система из двух нелинейных функций: $f(x, y)$ и $g(x, y)$, которые требуется минимизировать.

Что значит "минимизировать систему"?
Экстремумы ищут у функций со значениями в $\mathbb R$.
У Вас две таких функции. Можно смотреть на их пару как на функцию из $\mathbb R^2$ в $\mathbb R^2$. Но у такой функции векторные значения. Можно искать минимум нормы этой вектор-функции, например. Если нужно именно это. Так что все-таки нужно?

[Punisher174]

Как вы правильно сказали, нужно минимум нормы вектор-функции.

[Otta]

Ну а норма вектор-функции - это обычная скалярная функция из $\mathbb R^2$ в $\mathbb R$, экстремум которой Вы, говорите, искать умеете.

[Punisher174]

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

$$ \begin{cases} \lVert x_1(t_1) - x_2(t_2)\rVert \to \min$\\ \lVert y_1(t_1) - y_2(t_2)\rVert \to \min$\\ \end{cases} $$

Ну и минимизировать надо по $t_1 \text{ и } t_2$.

[provincialka]

Что значит "функции не пересекаются"? Каков смысл букв $x,y,t$? Это скаляры или векторы? Зачем вам два минимума?

[Punisher174]

Минимум нужен один, просто я некорректно записал. "Не пересекаются значит", что на рассматриваемом отрезке изменения параметра не существует таких $ t_1 \text{ и } t_2 $, т.е нет корней у рассматриваемой системы нелинейных уравнений.

[ewert]

Punisher174 в сообщении #745158 писал(а):

Требуется найти ближайшие точки на функциях.
Постановка задачи, как мне кажется, может быть выражена в виде:

$$\begin{cases}\lVert x_1(t_1) - x_2(t_2)\rVert \to \min$\\\lVert y_1(t_1) - y_2(t_2)\rVert \to \min$\\\end{cases}$$

Это лишь кажется; это оптическая иллюзия. Ближайшие точки -- это пара точек, на которой достигается минимум одной функции $\rho(\vec r_1,\vec r_2)=\|\vec r_1-\vec r_2\|.$ А уж что понимать под нормой -- дело вкуса. Вы, скорее всего, неудачно попытались понимать под ней $\|\vec r_1-\vec r_2\|_{\infty}=\max\{|x_1-x_2|,|y_1-y_2|\}$ (выбор, надо сказать, не самый лучший, хотя в принципе и допустимый).

[svv]

У автора две кривые, заданные параметрически: $\mathbf r_1(t)=(x_1(t), y_1(t))$ и $\mathbf r_1(t)=(x_2(t), y_2(t))$.
Он хочет найти такие значения $t_1$ и $t_2$, при которых расстояние между точками $\mathbf r_1(t_1)$ и $\mathbf r_2(t_2)$ минимально. Ну, и затем найти само это расстояние.

Кривые по условию задачи не пересекаются (иначе точка пересечения и давала бы решение).

Punisher174, для этого Вам надо найти такие $t_1$ и $t_2$, при которых минимальна скалярная функция
$(x_1(t_1)-x_2(t_2))^2+(y_1(t_1)-y_2(t_2))^2$
Квадратный корень здесь изначально был, но его можно убрать.

Punisher174, у Вас кривые Безье? (я почти уверен в этом)

[Punisher174]

ewert, спасибо.
svv, да Вы абсолютно правильно меня поняли.

Цитата:

Punisher174, у Вас кривые Безье? (я почти уверен в этом)

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

Цитата:

Punisher174, для этого Вам надо найти такие $t_1$ и $t_2$, при которых минимальна скалярная функция
$(x_1(t_1)-x_2(t_2))^2+(y_1(t_1)-y_2(t_2))^2$
Квадратный корень здесь изначально был, но его можно убрать.

Решить чем-нибудь наподобие градиентного спуска?
Еще вопрос.
В случае, когда точки пересечения имеются, я решал эту проблему "в лоб", просто как систему уравнений. Считаю это не слишком оптимальным. Есть ли другие методы?
Намного ли производительнее будет находить точки пересечения, если одну кривую аппроксимировать отрезками?

[svv]

Как решить это численно — пусть лучше Вам посоветуют другие участники, у кого больше опыта.

Допустим, чтобы найти минимум, я продифференцировал по $t_1$ и $t_2$ эту функцию,
$(x_2(t_2)-x_1(t_1))^2+(y_2(t_2)-y_1(t_1))^2$,
и приравнял частные производные нулю. Получатся уравнения:
$(x_2(t_2)-x_1(t_1))\; x'_1(t_1)+(y_2(t_2)-y_1(t_1))\;y'_1(t_1)=0$
$(x_2(t_2)-x_1(t_1))\; x'_2(t_2)+(y_2(t_2)-y_1(t_1))\;y'_2(t_2)=0$
Хорошие уравнения, красивые.

(Оффтоп)

Эти уравнения имеют простой геометрический смысл. Введем векторы:
$\mathbf R=\mathbf r_2(t_2)-\mathbf r_1(t_1)=(x_2(t_2)-x_1(t_1), y_2(t_2)-y_1(t_1))$ — это вектор, соединяющий точки $\mathbf r_1$ и $\mathbf r_2$,
$\mathbf u_1(t_1)=(x'_1(t_1), y'_1(t_1))$ — это касательный вектор к первой кривой при $t=t_1$,
$\mathbf u_2(t_2)=(x'_2(t_2), y'_2(t_2))$ — это касательный вектор ко второй кривой при $t=t_2$.
Тогда уравнения можно записать так:
$(\mathbf R, \mathbf u_1)=0$
$(\mathbf R, \mathbf u_2)=0$
Это значит, что когда расстояние достигает минимума, вектор, соединяющий ближайшие точки, перпендикулярен обеим касательным.

Но есть одна неприятность. Эти уравнения не отлавливают случаи, когда одна (или обе) из "ближайших" точек находится на конце кривой (или на концах кривых). В таком случае $t_1$, $t_2$, обеспечивающие минимум, не обязаны быть решениями записанных уравнений. А вероятность такой ситуации (навскидку) высока.
То есть при таком способе надо дополнительно проверять концы кривых.