2014 dxdy logo

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

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




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


25/12/15
8
Здраствуйте, товарищи.

Захотелось мне разобраться с тем, как решается задача поиска локального минимума функции нескольких переменных на гиперпрямоугольной области определения.
Посмотрел я в исходники геометрического ядра 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 
Заслуженный участник


30/01/09
5065
Mirmik в сообщении #1517306 писал(а):
Что это может быть за алгоритм такой и что он на деле делает?

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

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


01/08/06
2868
Уфа
Рискуя попасть пальцем в небо, предположу, что класс реализует алгоритм золотого сечения для поиска экстремума унимодальной функции. Это оптимальный метод для функций из этого класса.

 Профиль  
                  
 
 Re: Разбираю реализацию метода Пауэлла из ядра opencascad.
Сообщение10.05.2021, 20:49 
Заслуженный участник


30/01/09
5065
Я всё же склоняюсь к тому, что в обсуждаемом модуле происходит не поиск минимума (он будет выполняться позднее), а предварительный захват минимума в вилку. Об этом говорит текст, выдаваемый при отладке
Цитата:
The bracketed triplet is:
.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: maxal, Toucan, PAV, Karan, Супермодераторы



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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