Федеральное агентство по образованию и науке Российской Федерации
Волгоградский государственный технический университет
Кафедра «САПР»
Семестровая работа:
Тема: Разработка программной системы многомерной оптимизации
Выполнил:
студент группы ИВТ-362
Додонов А.В.
Проверил:
доцент, к.ф-м.н. Яновский Тимур Александрович
Волгоград 2010
1. Формулировка поставленной задачи
Разработать программную систему многомерной оптимизации. Провести численные исследования на наборе тестовых задач. Метод многомерной оптимизации – метод Розенброка.
2. Математическое решение
Постановка задачи
Требуется найти безусловный минимум функции f(x) многих переменных, т.е.найти такую точку x*, принадлежающую Rn, в которой бы функция имела свой минимум.
Стратегия поиска
Суть метода Розенброка состоит в следующем. Задаётся начальная точка. Из неё осуществляется итеративный поиск направления убывания функции с помощью изменяемых дискретных шагов вдоль n линейно независимых и ортогональных направлений. В случае удачного шага в исследуемом направлении его значение на следующей итерации увеличивается с помощью коэффициента растяжения, а в случае неудачи уменьшается за счёту умножения на коэффициент сжатия(при это направление поиска изменяется на противоположное). Поиск в системе текущих направлений проводится до тех пор, пока все возможности уменьшения функции не будут исчерпаны. Если по каждому направлению поиска имеет место неудача, строится новое множество линейно независимых ортогональных направлений и циклический поиск по отдельным направлениям продолжается. Новые направления поворачиваются по отношению к предыдущим так, что они оказываются вытянутыми вдоль оврага.
3. Алгоритмическое решение
Метод Розенброка:
Шаг 1. Задать начальную точку х0, число е > 0 для остановки алгоритма, коэффициент растяжения
α > 1 и сжатия -1 < β < 0, в качестве начальных линейно независимых и ортогональных направлений d1,d2,…,dn выбрать координатные направления:
d1 = {1, 0,…, 0}, d2 = {0, 1,…, 0}, …, dn = {0, 0,…, 1};
начальную длину шага вдоль каждого из направлений поиска ∆10, …, ∆n0 > 0;
N – максимальное число неудачных серий шагов по всем направлениям на одной итерации.
Положить y1= x0, k = 0, i = 1, ∆i = ∆i0 для всех i.
Шаг 2. Сделать шаг по i-му направлению:
а) если f(yi + ∆idi) < f(yi), шаг считается удачным. В этом случае следует положить yi+1 = yi + ∆idi,
∆i = α ∆i и перейти к шагу 3.
б) если f(yi + ∆idi) ≥ f(yi), шаг считается неудачным. В этом случае следует положить yi+1 = yi ,
∆i = β ∆i и перейти к шагу 3.
Шаг 3. Проверить выполнение условий:
а) если i < n, то положить i = i +1 и перейти к шагу 2(сделать шаги по оставшимся направлениям);
б) если i = n, проверить успешность поиска по текущим ортогональным направлениям:
- если f(yn+1) < f(y1), т.е. хотя бы один спуск по направлению на шаге 2 был успешным, положить y1 = yn+1, i = 1 и перейти к шагу 2;
- если f(yn+1) = f(y1), т.е. каждый из n последних шагов был неудачным, оценить успешность поиска на текущей итерации:
-- если f(yn+1) < f(xk), т.е. на k-ой итерации был хотя бы один удачный шаг, то перейти к шагу 4.
-- если если f(yn+1) = f(xk), т.е. не было ни одного удачного шага на k-ой итерации, процесс поиска приостановить. Если число l последовательно неудачных серий шагов по всем направлениям на текущей итерации не превышает N, проверить условие окончания, а иначе перейти к шагу 4. Провеяются величиы i, использованные во время последней серии шагов. Если |∆i| ≤ е для всех i, то найдено приближённое решение задачи x* = xk. Иначе положить y1 = yn+1, i = 1 и перейти к шагу 2.
Шаг 4. Положить xk+1 = yn+1 и проверить условие окончания:
а) если ||xk+1 – xk|| ≤ е, то поиск завершить х* = xk+1;
б) если ||xk+1 – xk|| > е, вычислить длины шагов по каждому направлению поиска на k-й итерации из соотношения xk+1 – xk = ∑ λ idi. Далее построить новый набор линейно независимых и взаимно ортогональных направлений поиска с помощью процедуры Грама-Шмидта:
ai = di, при λi = 0,
∑ λ jdj, j = i, …, n при λi ≠ 0,
bi = ai, i = 1,
ai - ∑ (aiT_dj) _dj, j = 1, …, i-1 при i ≥ 2;
_di = bi/||bi||
После нахожления новых направлений следует положить: di = _di, ∆i = ∆i0
для всех i = 1,…n, k = k + 1, y1 = xk+1, i =1, и перейти к шагу 2.
Блок-схема