МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ТУ-УГМК

С.П Трофимов

Контрольная работа

Методическая разработка для заочной формы обучения

по дисциплине
«Методы оптимизации»

В.Пышма

2017

Оглавление

Теоретическая часть

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

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

f(x)→ extr, x Eⁿ. (1)

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

1. Необходимое условие оптимальности 1- порядка

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

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

2. Необходимое условие оптимальности 2- порядка

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

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

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

1. Достаточное условие оптимальности 2- порядка

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

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

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

3. Если матрица Н(х^*)-знакопеременная, то х^* не является точкой локального экстремума.

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

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

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

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

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

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

2. В стационарных точках x^* (точках, являющихся решением системы (2)) исследовать на знакоопределенность матрицу вторых производных. Точки, в которых гессиан Н(x^*) положительно определен, являются точками глобального минимума; стационарные точки, в которых Н(х^*) отрицательно определен, являются точками глобального максимума. Если гессиан знакопеременный, то x^* не является экстремумом. Если гессиан полуопределенный, то для определения оптимальности нужны дополнительные исследования.

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

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

2. Численные методы безусловной минимизации

Численное решение задачи минимизации (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(x), используемых для формирования d^k и t_k, численные методы принято делить на три группы:

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

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

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

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

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

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

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

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

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

xⁿ⁺²= - центр тяжести;

xⁿ⁺³= xⁿ⁺²+( xⁿ⁺²- x^h) – новая точка (“растянутое” отражение наихудшей вершины).

Метод дробления шага

Строится последовательность точек {x^k}, k=0,1,..., таких, что f(x^k)<f(x^k-1), k=0,1,... .Точки последовательности{x^k} вычисляются по правилу

x^k+1=x^k-t_kgrad f(x^k), k=0,1,.... (4)

Точка х⁰ задается пользователем; grad f(x^k) – градиент минимизируемой функции, вычисленный в точке x^k; величина шага t₀ задается пользователем и остается постоянной до тех пор, пока функция убывает в точках последовательности, что контролируется путем проверки выполнения условия

f(x^k+1)-f(x^k) <0 (или <-ε). Если условие убывания не выполняется, величина шага уменьшается, как правило, вдвое, то есть, t_k=t_k/2.

Метод наискорейшего градиентного спуска

Строится последовательность точек {x^k}, k=0,1,..., таких, что f(x^k)<f(x^k-1), k=0,1,... .Точки последовательности {x^k} вычисляются по правилу

x^k+1=x^k-t_kgrad f(x^k), k=0,1,... . Точка х⁰ задается пользователем; grad f(x^k) – градиент минимизируемой функции, вычисленный в точке x^k; величина шага t_k определяется из условия минимума функции φ(t_k)=а(x^k-t_kgrad f(x^k)). Задача минимизации одномерной функции φ(t_k) может быть решена с использованием необходимого условия минимума =0 с последующей проверкой достаточного условия минимума >0 или с использованием численных методов.

Метод сопряженных направлений (Флетчера – Ривса)

Строится последовательность точек {x^k}, k=0,1,..., таких, что f(x^k)<f(x^k-1), k=0,1,... .Точки последовательности{x^k} вычисляются по правилу:

x^k+1=x^k-t_kd^k, k=0,1,....;

d^k=- grad f(x^k)+β_k-1d^k-1; (4)

d⁰=- grad f(x⁰);

β_k-1=║ grad f(x^k)║²∕║ grad f(x^k-1)║²

Точка х⁰ задается пользователем; величина шага t_k определяется из условия минимума функции φ(t)=а(x^k-t d^k)). Задача минимизации одномерной функции φ(t_k) может быть решена с использованием необходимого условия минимума (dφ/dt)=0 с последующей проверкой достаточного условия минимума >0 или с использованием численных методов.

Метод Ньютона

Строится последовательность точек {x^k}, k=0,1,..., таких, что f(x^k)<f(x^k-1), k=0,1,... .Точки последовательности{x^k} вычисляются по правилу x^k+1=x^k+d^k, k=0,1,..... Точка х⁰ задается пользователем с учетом знакопостоянства и невырожденности матрицы Гессе в задаваемой начальной точке и близости выбранной точки к предполагаемой точке минимума. Направление спуска определяется для каждого значения k по формуле

d^k=-H^-1(x^k)grad f(x^k), где Н – матрица Гессе.

Порядок выполнения лабораторной работы

1. Записать необходимые условия экстремума. Аналитически или используя прикладные пакеты найти стационарные точки.

2. Проверить выполнение достаточных условий экстремума в найденных стационарных точках. Найти глобальный минимум функции. Оценить обусловленность задачи в точке минимума и “овражность” графика в окрестности точки минимума. Сделать предварительный вывод о работоспособности избранного численного метода.

3. Выбрать пакет, в котором будет строиться график. Рекомендации приведены в Приложении. Построить график функции, задавая пределы изменения координат с учетом аналитически найденных точек минимума – максимума.

4. Выбрать несколько начальных точек для реализации численного метода. Задать критерий завершения итерационного процесса. Найти минимум. Сравнить результаты с аналитически найденным значением глобального минимума. Исследовать сходимость алгоритма, фиксируя точность определения минимума, количество итераций метода и количество вычислений минимизируемой функции в зависимости от задаваемой точности поиска. Результатом выполнения данного пункта должны быть выводы об объёме вычислений в зависимости от задаваемой точности и начального приближения.