2014 dxdy logo

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

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




 
 Разбираю реализацию метода Пауэлла из ядра opencascad.
Сообщение07.05.2021, 11:59 
Аватара пользователя
Здраствуйте, товарищи.

Захотелось мне разобраться с тем, как решается задача поиска локального минимума функции нескольких переменных на гиперпрямоугольной области определения.
Посмотрел я в исходники геометрического ядра opencascade и нашёл, что для функций, для которых неизвестны производные и всяческие гессианы, они используют метод Пауэлла, который в свою очередь реализован через однопараметрический поиск, использующий метод Брента. Но метод Брента должен вызываться на некотором интервале, который вычисляется классом "math_BracketMinimum" (ref: http://git.dev.opencascade.org/gitweb/? ... aa98fe144d ), механизм работы которого ускользает от меня. В документации на класс написано:

"Given two distinct initial points, BracketMinimum implements the computation of three points (a, b, c) which bracket the minimum of the function and verify A less than B, B less than C and F(A) less than F(B), F(B) less than (C)."

Что это может быть за алгоритм такой и что он на деле делает?

Какие вообще есть подходы к нахождению интервала для последующего применения алгоритма минимизации на интервале?

 
 
 
 Re: Разбираю реализацию метода Пауэлла из ядра opencascad.
Сообщение07.05.2021, 14:34 
Аватара пользователя
Mirmik в сообщении #1517306 писал(а):
Что это может быть за алгоритм такой и что он на деле делает?

Точного описания этого обычно в учебниках не приводится. Теорий тут нет. Детали остаются на совести разработчиков. Надо разбираться в коде программы. Пробуйте. Но основную задачу вы поняли. Перед нами стоит задача нахождения минимума функции на луче. Для этого нужно захватить этот минимум в вилку (bracket). У нас есть первоначальный шаг и направление поиска. На этом направлении заданы три точки. Если Если точка с минимальным значением функции внутри интервала поиска, то всё хорошо. Минимум захвачен в вилку (предполагаем, что функция выпукла). Если эта точка на границе интервала поиска, то увеличиваем этот интервал. умножая его на константу. (В программе, кстати. приводится константа золотого сечения. Может она тут при делах). Повторяем эту процедуру, пока точка не окажется внутри интервала поиска.

 
 
 
 Re: Разбираю реализацию метода Пауэлла из ядра opencascad.
Сообщение10.05.2021, 18:28 
Аватара пользователя
Рискуя попасть пальцем в небо, предположу, что класс реализует алгоритм золотого сечения для поиска экстремума унимодальной функции. Это оптимальный метод для функций из этого класса.

 
 
 
 Re: Разбираю реализацию метода Пауэлла из ядра opencascad.
Сообщение10.05.2021, 20:49 
Аватара пользователя
Я всё же склоняюсь к тому, что в обсуждаемом модуле происходит не поиск минимума (он будет выполняться позднее), а предварительный захват минимума в вилку. Об этом говорит текст, выдаваемый при отладке
Цитата:
The bracketed triplet is:
.

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group