Алгоритм поиска экстремума функции от 4-х переменных

[Rasool]

Мы занимаемся измерением поверхностей деталей с помощью измерительных систем.
Возникает такая задача. Дано: измеренные значения фактических точек поверхности детали и чертежные, идеальные значения точек поверхности чертежа детали.
На практике всегда имеются отклонения фактических точек вследствие неточного его изготовления. Нужно правильно оценить результаты измерений и определить степень годности или брака измеренных профилей детали относительно чертежных значений профилей. Есть допуск на отклонения фактических точек профиля поверхности 3D детали. Также есть допуск на смещения образа детали вдоль осей 0X, 0Y и поворота детали вокруг осей 0X, 0Z.
Допуск - это диапазон разрешенных отклонений измеренных фактических точек от чертежных.
Отсюда нужно правильно, как бы вписать, идеальную деталь в фактическую и оценить результаты отклонения фактических точек профиля поверхности 3D детали от идеальной 3D детали.
По величинам смещений и разворотов отклонений по контрольным точкам всех измеренных сечений детали далее ясно, как следует скорректировать технический процесс изготовления детали, чтобы последующие детали имели профиль полностью в допуске.
Возникает задача максимально возможного совмещения профилей детали с чертежом путем смещения образа детали вдоль осей 0X, 0Y и поворота детали вокруг осей 0X, 0Z (рис.1). Т.е. возникает задача минимизации числа точек за полем допуска или максимизации числа точек в поле допуска.

Проект, которым я сейчас занимаюсь, разрабатывался поколениями программистов до меня. В нем имеется готовая плавная функция $f(x_1, x_2, x_3, x_4)$ оценки числа фактических точек вне допуска в зависимости от смещения образа детали вдоль осей 0X ($x_1$), 0Y ($x_2$) и поворота детали вокруг осей 0X ($x_3$), 0Z ($x_4$).
Т.е. возникает задача поиска глобального минимума числа точек вне поля допуска в четырехмерном пространстве состояний перебором возможных значений четырех координат: смещения образа детали вдоль осей 0X, 0Y и поворота детали вокруг осей 0X, 0Z.

Отсюда у меня такой вопрос. Какой способ поиска глобального экстремума лучше применить?
Мне в голову пришло следующее. На первом этапе делаем некое подобие градиентного спуска: для начального положения в четырехмерном пространстве генерируем угловые точки, точки центров ребер, точки центра плоских квадратов, точки центра трехмерных кубов четырехмерного гиперкуба с центром в начальной точке поиска и сторонами, равными заданным шагам перебора координат $\Delta x_1, \Delta x_2, \Delta x_3, \Delta x_4$. На следующем шаге алгоритма точки с минимальным значением $f(x_1, x_2, x_3, x_4)$ становятся центрами новых гиперкубов.
Таким образом реализуется что-то вроде градиентного спуска - идет поиск положений с минимумом точек за полем допуска с заданными шагами $\Delta x_1, \Delta x_2, \Delta x_3, \Delta x_4$.
После того, как локальный минимум будет найден (найдено положение, которое больше нельзя улучшить при заданных шагах), то реализуется второй этап:
Положение с минимальным значением точек за полем допуска становится центром гиперкуба $2\Delta x_1, 2\Delta x_2, 2\Delta x_3, 2\Delta x_4$.
Внутри этого гиперкуба методом дихотомии (бисекции) реализуется поиск положения с минимальным значением числа точек за полем допуска. Критерий остановки - заданный минимальный шаг дихотомии $\Delta x_1_\min$, $\Delta x_2_\min$, $\Delta x_3_\min$, $\Delta x_4_\min$.

Недостаток описанного метода - реализуется поиск только локального минимума. Глобальный минимум мы можем пропустить. Что можно сделать, чтобы гарантированно получить глобальный минимум?

[Pavia]

1) Метод наименьших квадратов даёт гарантируемый глобальный оптимум.
2) Метод секущих.

Из не гарантированных:
3) Равномерная или случайная сетка покрывающая весь диапазон возможных значений. Далее используешь узлы этой сетки как начальные значения для метода градиентного спуска. Далее из всех решений ищешь максимум или минимум.
Если сетка достаточно плотная то алгоритм гарантированно найдет глобальный оптимум.
4) ICP
https://ru.wikipedia.org/wiki/Итеративный_алгоритм_ближайших_точек
По этой теме очень много работ. Может что-то найдёте.

[Rasool]

Спасибо, будем думать.

[B@R5uk]

Разве у детали нет базовых плоскостей от которых ведётся отсчёт всех размеров? Не надо ничего крутить/вписывать, лишь проверить правильность изготовления.

Далее. Ваша функция, если я правильно понял, возвращает целое число, то есть она дискретная. Искать минимум такой функции не так то просто, кроме того, эта информация менее информативна, чем, например, сумма квадратов нормированных на допуск отклонений. Для последней непрерывной функции можно использовать алгоритм Нелдера-Мида. Он крайне прост и очень эффективен.

Однако, как и любой численных алгоритм, алгоритм Нелдера-Мида находит один локальный минимум, так что выбор начального условия критичен. Как эту проблему решать уже предложил оратор выше. Кроме того, отыскав несколько локальных минимум в смысле МНК отклонений, можно отталкиваясь от этих решений как от начальных найти несколько оптимальный в желаемом вами смысле решений.

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

[Rasool]

Т.е. сначала можно искать минимум СКО измеренных точек от чертежных, а потом искать минимум числа точек за полем допуска?

[dsge]

Rasool в сообщении #1042367 писал(а):

Мне в голову пришло следующее. На первом этапе делаем некое подобие градиентного спуска: для начального положения в четырехмерном пространстве генерируем угловые точки, точки центров ребер, точки центра плоских квадратов, точки центра трехмерных кубов четырехмерного гиперкуба с центром в начальной точке поиска и сторонами, равными заданным шагам перебора координат $\Delta x_1, \Delta x_2, \Delta x_3, \Delta x_4$. На следующем шаге алгоритма точки с минимальным значением $f(x_1, x_2, x_3, x_4)$ становятся центрами новых гиперкубов.

Это, так называемый, pattern search method (google gives details).

[Rasool]

Rasool в сообщении #1042367 писал(а):

Возникает задача максимально возможного совмещения профилей детали с чертежом путем смещения образа детали вдоль осей 0X, 0Y и поворота детали вокруг осей 0X, 0Z (рис.1). Т.е. возникает задача минимизации числа точек за полем допуска или максимизации числа точек в поле допуска.

Эта процедура называется "припасовкой" детали. Заказчик прислал нам тех. задание с просьбой добавить припасовку по двум методам припасовки: методу Гаусса, методу Чебышева.
Вопрос такой: собственно, в чем заключаются эти два метода в приложении к припасовке? Нашел следующее: http://physics.herzen.spb.ru/library/01/01/nm_labs/approximation.htm

[Алексей К.]

B@R5uk в сообщении #1045307 писал(а):

Разве у детали нет базовых плоскостей от которых ведётся отсчёт всех размеров? Не надо ничего крутить/вписывать, лишь проверить правильность изготовления.

В большинстве случаев --- есть. Но не всегда.
Спустимся для простоты из 3D в 2D, а в качестве детали рассмотрим монету с эллиптическим профилем.
Никакого способа для построения базиса (начала координат и оси абсцисс), кроме кручения-двигания и поиска минимума, нет.

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

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

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

Так что, возвращаясь в 3D, полагаю, что поставленная автором задача имеет право на. Возможно, имеется какая-то базовая плоскость, всего одна, чего недостаточно для построения системы координат: остальное всё равно надо "докручивать".

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

При Брежневе в такого рода задачах всегда хорошо работал МНК. Но это так, если вся поверхность у нас --- один эллипсоид, или какой-то другой овоид, сплайноид, фигоид --- лишь бы эталон был известен. А вот если у нас несколько поверхностей, типа цилиндрической боковушки и двух офигических шапочек --- то тут надо думать: с какой из поверхностей сравнивать данную точку $(x_i,y_i,z_i)$? Впрочем, если $i$-тая точка конкретно приписана $j$-той поверхности, то и тут думать особо не о чем.

[Rasool]

Примерно, такая деталь.

[Rasool]

dsge в сообщении #1073464 писал(а):

Это, так называемый, pattern search method (google gives details).

Спасибо, сейчас работаю над его усовершенствованием.

[Rasool]

dsge в сообщении #1073464 писал(а):

Rasool в сообщении #1042367 писал(а):

Мне в голову пришло следующее. На первом этапе делаем некое подобие градиентного спуска: для начального положения в четырехмерном пространстве генерируем угловые точки, точки центров ребер, точки центра плоских квадратов, точки центра трехмерных кубов четырехмерного гиперкуба с центром в начальной точке поиска и сторонами, равными заданным шагам перебора координат $\Delta x_1, \Delta x_2, \Delta x_3, \Delta x_4$. На следующем шаге алгоритма точки с минимальным значением $f(x_1, x_2, x_3, x_4)$ становятся центрами новых гиперкубов.

Это, так называемый, pattern search method (google gives details).

Не является ли это вариацией так называемого ICP-алгоритма?

[NO.]

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

[Rasool]

NO. в сообщении #1133461 писал(а):

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

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

[Rasool]

Rasool в сообщении #1133392 писал(а):

Не является ли это вариацией так называемого ICP-алгоритма?

И где можно подробно почитать про ICP алгоритм, в википедии даны только сведения общего плана?

[Markiyan Hirnyk]

Почему бы не попробовать применить очень эффективный пакет DirectSearch (см. http://www.maplesoft.com/applications/view.aspx?SID=101333) вместо изобретения велосипеда? Подробности по требованию.