Планирование

Геометрический смысл  метода сопряженных градиентов состоит в следующем (Рис. 1.4). Из заданной начальной точки х[0] осуществляется спуск в направлении р[0] = -f'(x[0]). В точке х[1] определяется вектор-градиент f'(x [1]). Поскольку х[1] является точкой минимума функции в направлении р[0], то f’(х[1]) ортогонален вектору р[0]. Затем отыскивается вектор р [1],H-сопряженный к р [0] . Далее отыскивается минимум функции вдоль направления р[1] и т. д.

Рис. 1.4. Траектория спуска в методе сопряженных градиентов

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

 

Список литературы

 

1. Аоки М. Ведение в методы оптимизации. М.: Наука. 2008. 344с.
2. Бояринов А.И., Кафаров В.В. Методы оптимизации в химической технологии. М.: Химия. 2005. 576с.
3. Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. - M.: Наука, 2007. - 382с.
4. Фурунжиев Р.И., Бабушкин Ф.М., Варавко В.В. Применение математических методов и ЭВМ: Практикум. Мн.: Выш.шк. 2007. 191с.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Аналитическая часть

 

2.1 Вопросы по теме «Численные методы безусловной оптимизации первого порядка»

 

1. Что называется градиентом дифференцируемой функции?

2. В какую сторону направлен вектор антиградиент?

3.Чему равен градиент функции в точке минимума?

4. Какие методы более экономичны в смысле количества итераций и надежности ?

5.  Опишите алгоритм метода наискорейшего спуска?

6. Какие функции называются  овражными?

7. В чем преимущество  метода сопряженных градиентов?

8. Что является одной из наиболее существенных проблем в методах сопряженных градиентов?

9. В чем особенность  метода Флетчера-Ривса?

10.В чем состоит геометрический смысл метода сопряженных градиентов?

 

 

2.2 Тест

 

1)Оптимизация-это

 

А) математическая задача, которая предполагает поиск экстремумов функций, в определенной выбранной области. 

Б) особый случай применения логической операции деления объема понятия, представляющий собой некоторую совокупность делений

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

Г)  противозаконный захват чего-либо или насильственное присвоение чужих прав

 

2) В настоящее время для решения оптимальных задач применяют в основном следующие методы:

 

А) методы эмпирического  исследования

Б) вариационное исчисление; динамическое программирование; принцип максимума

В) методы исследования функций классического анализа; методы, основанные на использовании неопределенных множителей Лагранжа

Г) верно б и в

 

3) Вектор-градиент направлен:

 

А) в сторону наискорейшего  убывания функции

Б) в сторону наискорейшего  возрастания функции в данной точке

В) перпендикулярно к плоскости, проведенной через точку х[0]

Г) нет верного ответа

 

4) Какие методы основаны  на свойствах градиента?

 

 А) методы первого  порядка

Б) методы второго порядка

В) методы третьего порядка

Г) методы четвертого порядка

 

5) При использовании метода  наискорейшего спуска на каждой  итерации величина шага а_k выбирается из какого условия?

 

А) минимума функции f(x) в направлении подъема

 Б) минимума функции f(x) в направлении спуска

В) максимума функции f(x) в направлении подъема

Г) максимума функции f(x) в направлении спуска

 

6)Как называются функции,  значения которых вдоль некоторых  направлений изменяются гораздо  быстрее (иногда на несколько  порядков), чем в других направлениях  и их поверхности уровня в  простейшем случае сильно вытягиваются?

 

А)цепные

Б) периодические

В) овражные

Г) системные

 

7) два n-мерных вектора х и у называют сопряженными по отношению к матрице H (или H-сопряженными), если:

 

А) скалярное произведение (x, Ну) = 0. 

Б) скалярное произведение (x, Ну) = 1. 

В) скалярное произведение (x, Ну) = -1. 

Г) нет верного ответа

 

8) На чем основан метод Флетчера-Ривса?

А) для квадратичной функции n переменных n одномерных поисков вдоль взаимно сопряженных направлений позволяют найти максимум.

Б) для квадратичной функции n переменных n одномерных поисков вдоль взаимно сопряженных направлений позволяют найти минимум.

В)это итерационный численный метод нахождения корня (нуля) заданной функции

Г)верно а и б

 

 

9)Какие методы являются  одними из наиболее эффективных для решения задач минимизации?

А) линейное программирование

Б) методы исследования функций  классического анализа

В) методы сопряженных направлений

Г) метод множителей Лагранжа

 

10)Как называется вектор, противоположный градиенту (-f’(х[0])),

 

А) антиградиентом 

 Б) полиградиентом

В) полином

Г) нет верного ответа

 

Ответы: 1)а, 2)г, 3)б, 4)а, 5)б, 6)в, 7)а, 8)б, 9)в, 10)а

 

 

2.3 Примеры задач:

 

Исследование  функции на безусловный экстремум

Рассматривается задача

f (x) > extr, xRⁿ. (1)

Метод поиска безусловного экстремума основывается на следующих  утверждениях:

Пусть функция f (x) дифференцируема в точке х^*Rⁿ. Тогда если х^*- локальное решение задачи (1), то

grad f (x^*) =0. (2)

Пусть функция f (x) дважды дифференцируема в точке х^*Rⁿ. Тогда

а) если х^* - точка локального минимума в задаче (1), то матрица Гессе Н (х^*) неотрицательно определена, т.е. рRⁿ выполняется неравенство (Н (х^*) р,р) ?0;

б) если х^* - точка локального минимума в задаче (1), то матрица Н (х*) неположительно определена, т.е. рRⁿ выполняется неравенство (Н (х^*) р,р) ?0.

Пусть функция f (x) дважды дифференцируема в точке х^*Rⁿ и

grad f (x^*) =0. Тогда

а) если матрица Н (х^*) положительно определена, т.е. рRⁿ, р?0, (Н (х^*) р,р) >0, то х^* - точка строгого локального минимума функции f (x) на Rⁿ;

б) если матрица Н (х^*) отрицательно определена, т.е. рR, р?0, (Н (х^*) р,р) <0, то х^* - точка строгого локального максимума функции f (x) на Rⁿ.

Если grad f (x^*) =0, то х^* называется стационарной точкой. Для выпуклой (вогнутой) на Rⁿ функции стационарные точки являются точками ее глобального минимума (максимума). Строго выпуклые (вогнутые) функции имеют единственный глобальный минимум (максимум).

Критерий выпуклости функции. Дважды непрерывно дифференцируемая на выпуклом множестве Хс непустой внутренностью функция является выпуклой (вогнутой) на этом множестве в том и только том случае, когда матрица Гессе Н (х^*) неотрицательно (не положительно) определена для всех хХ.

При исследовании на знакоопределенность  матрицы вторых производных функции  рекомендуется применять критерий Сильвестра или анализ собственных  значений матрицы.

Схема поиска безусловных  экстремумов функции:

Составить и решить систему  алгебраических уравнений (2).

В стационарных точках (точках, являющихся решением системы (2)) исследовать  на знакоопределенность матрицу  вторых производных; точки, в которых Н (х) >0, являются точками глобального минимума; стационарные точки, в которых Н (х) <0, являются точками глобального максимума.

Исходя из вида исследуемой  функции, проанализировать стационарные точки, в которых матрица вторых производных не является строго знакоопределенной.

Найденные точки локального экстремума исследуются на глобальный экстремум (если это возможно). В  частности, если матрица Гессе неотрицательно (не положительно) определена на всем пространстве Еⁿ, то все стационарные точки функции являются точками глобального минимума (максимума).

Численные методы минимизации функции

Численное решение задачи минимизации (1), как правило, связано  с построением минимизирующей последовательности точек x⁰,x¹,x²,…,xⁿ,…, обладающих свойством

f (x^k) <f (x^k-1), k=0,1,… (3)

Общее правило построения минимизирующей последовательности имеет  вид

x ^k+1=x ^k+t _kd ^k, k=0,1,…,

где х⁰ - начальная точка поиска; d^k - приемлемое направление перехода из точки x^k в точку x^k+1, которое обеспечивает выполнение условий (3) и называется направлением спуска; t_k - величина шага. Начальная точка поиска задается исходя из физического содержания решаемой задачи и априорных данных о существовании и положении точек экстремума.

При решении вопроса о  выборе численного метода рекомендуется  оценить поведение линий уровня целевой функции в окрестностях предполагаемой точки экстремума. Число m = L/l, где L и l - максимальное и минимальное собственные значения гессиана функции f в предполагаемой точке экстремума x⁰ (характеризующее разброс собственных значений оператора f (x)), называетсячислом обусловленности гессиана функции f в точке x⁰. Если m >> 1, то функция f называетсяплохо обусловленной или овражной. Овражность, то есть вытянутость линий уровня вдоль одного направления, приводит к тому, что градиентные методы поиска экстремума функции сходятся медленно.

В зависимости от наивысшего порядка частных производных  функции f (x), используемых для формирования d^k и t_k, численные методы принято делить на три группы:

Методы нулевого порядка, использующие информацию только о значениях  функции f (x) (методы деформируемого многогранника, конфигураций). Эти методы могут применяться в тех случаях, когда функция задана неявно или не задана аналитически, но известен ряд значений функции или эти значения вычисляются непосредственно в ходе реализации алгоритма. Они также могут быть полезны в случаях, когда производные функции могут быть заданы аналитически, но их выражения очень громоздки.

Методы первого порядка, использующие информацию о значениях  самой функции f (x) и ее первых производных (методы наискорейшего градиентного спуска, дробления шага, Гаусса-Зейделя, Флетчера-Ривса).

Методы второго порядка, использующие, кроме того, и информацию о вторых производных функции f (x) (метод Ньютона и его модификации).

Метод конфигураций (Хука - Дживса)

Следует выделить два этапа  метода конфигураций:

1) исследование с циклическим  изменением переменных и 2) ускорение  поиска по образцам.

Исследующий поиск начинается в точке х⁰, называемой старым базисом. Направления поиска - координатные направления. По каждому направлению поочередно с шагом +t₀ (-t₀) проверяется выполнение условия (2) и в качестве нового базиса берется точка с координатами, полученными в результате удачных шагов из начальной точки по каждому направлению.

Направление от старого базиса к новому задает направление ускорения  поиска: в качестве следующей точки  минимизирующей последовательности проверяется  точка y¹=x⁰+ (x¹-x⁰). Здесь - ускоряющий множитель, задаваемый пользователем. Если полученная точка является удачной, то она берется в качестве следующей точки для исследования. В противном случае исследование ведется из точки x¹.

Метод деформируемого многогранника (Нелдера - Мида).

При решении задачи поиска минимума функции f (x) методом Нелдера-Мида строится последовательность множеств из n+1 точек, которые являются вершинами выпуклого многогранника. На каждом последующем k+1-м шаге из системы точек xⁱ (k), i=1, …,n+1, полученной на k-м шаге, выводится точка x^h (k), в которой функция f (x) имеет наибольшее значение (худшая точка). Вместо x^h (k) в систему вводится новая точка, выбираемая на отрезке прямой, проходящей через худшую точку и центр тяжести оставшихся n вершин многогранника: