Методы многомерной минимизации нулевого порядка по курсу

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Российский Химико-Технологический Университет имени Д. И. Менделеева»
Кафедра информационных компьютерных технологий
ОТЧЕТ

По лабораторной работе №1

на тему:
Методы многомерной минимизации нулевого порядка
по курсу:

Системы поддержки принятия решений

Выполнили студенты группы МК-10:

Лин Тант Аунг
Тэт Наунг Со
Юсуфжонов Ж.
Проверил:
ст. преп. Приходько В. Н.


Москва
2022
Задание на лабораторную работу:
Реализовать поиск безусловного минимума функции многих переменных методам вращающихся направлений.
Теоретическая часть:
Суть метода Розенброка состоит в следующем. Задается начальная точка. Из нее осуществляется итеративный поиск направления убывания функции с помощью изменяемых дискретных шагов вдоль n линейно независимых и ортогональных направлений. В случае удачного шага в исследуемом направлении его значение на следующей итерации увеличивается с помощью коэффициента растяжения, а в случае неудачи уменьшается за счет умножения на коэффициент сжатия (при этом направление поиска изменяется на противоположное). Поиск в системе текущих направлений проводится до тех пор, пока все возможности уменьшения функции не будут исчерпаны. Если по каждому направлению поиска имеет место неудача, строится новое множество линейно независимых и ортогональных направлений и циклический поиск по отдельным направлениям продолжается.
Требуется найти безусловный минимум функции f(х) многих переменных, т.е. найти такую точку, что f(x*) = min f(x).
Отличие этого метода от метода Хука Дживса состоит в способе выбора направлений исследующего поиска. Если в методе Хука — Дживса они фиксированы и коллинеарны направлениям векторов стандартного базиса, то в рассматриваемом методе выбор этих направлений проводят в процессе минимизации целевой функции путем построения на каждом к-м шаге поиска нового ортонормированного базиса методом Грамма Шмидта.
Экспериментальное сравнение алгоритмов Хука Дживса и Розенброка по числу вычислений целевой функции в процессе оптимизации говорит в пользу алгоритмов вращающихся направлений, это выигрыш растет при увеличении размерности. Но необходимо учитывать более существенные вычислительные затраты на пересчет системы ортогональных направлений.
Иллюстрируются этапы одного шага поиска точки минимума целевой функции двух переменных из начальной точки.