Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Контрольная работа по "Методы оптимизации"

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

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

по курсу «Методы оптимизации»

Томск, 2010 г.

1. Привести примеры методов поиска нулей функции.

1) Метод половинного деления (метод дихотомии).

Считаем, что отделение корней произведено и на интервале [a,b] расположен один корень, который необходимо уточнить с погрешностью .

Итак, имеем . Метод дихотомии заключается в следующем. Определяем половину отрезка и вычисляем . Проверяем следующие условия

Если , то c – корень. Здесь - заданная точность.
Если , то корень лежит в интервале .
Если , то корень лежит на отрезке .

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

Так как за каждую итерацию интервал, где расположен корень, уменьшается в два раза, то через n итераций интервал будет равен ,

при этом , , .

В качестве корня возьмем . Тогда погрешность определения корня будет равна . Если выполняется условие , то процесс поиска заканчивается и .

2) Метод хорд.

Рассмотрим более быстрый способ нахождения корня на интервале [a,b], в предположении, что .

Рис.1а Рис. 1б

Рассмотрим рис.1а. Проведем через точки А и В хорду. Уравнение хорды

В точке , в результате получим первое приближение корня

Проверяем условия

(а) ,

(б) .

Если выполняется условие (а), точку заменяем на , получим

Продолжая этот процесс, получим для n-го приближения

Если подвижен конец , тогда

3) Метод Ньютона (метод касательных).

Пусть корень уравнения отделен на отрезке . Предположим мы нашли -ое приближение корня . Тогда -ое приближение мы можем получить следующим образом. Положим

Раскладывая в ряд в точке , получим

Отсюда следует

2. Основные оценки эффективности оптимизационных процессов.

Асимптотическая сходимость и скорость сходимости. С практической точки зрения эффективность алгоритма зависит от числа итераций, необходимых для получения приближенного решения x^* с заданной точностью e.

Для получения критерия с некоторым абсолютным значением необходимо прибегнуть к другому типу анализа, взяв за объект исследования асимптотическую сходимость – поведение последовательности точек {x_k} в окрестности предельной точки x^*. Это значит, что каждому алгоритму приписывается индекс эффективности – скорость сходимости.

Предположим, что последовательность {x_k} сходится к точке x^*.

|| . || - знак евклидовой нормы в пространстве Rⁿ.

Линейная сходимость. Выполняется неравенство:

_, (2.1)

где a - коэффициент сходимости.

Суперлинейная сходимость:

® _{0. (2.2)}

Сходимость порядка p. Если существует такое число p > 1 (2,3…), что

_<_c_< _¥_, (2.3)

где c – константа, значит, имеем сходимость порядка p;

p = 2 – квадратичная сходимость;

p = 3 – кубическая сходимость;

p = n – сходимость порядка n.

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

Замечание. Иногда к выражению скорости сходимости последовательности {x_k} приходят и при исследовании способа сходимости последовательности { f(x_k) } к f(x^*).

Возможны ситуации, когда последовательность {x_k}, для которой норма || x_k – x^* || линейно сходится к нулю, а последовательность {f(x_k)} даже не является монотонно убывающей. Обратно, значения |f(x_k)– f(x^*)| могут линейно сходиться к нулю, когда расстояние || x_k - x^* || не является монотонным. В большинстве же случаев оценка скорости сходимости по норме || x_k - x^* || равносильна оценке разности | f(x_k)–f(x^*) |.

Для оценки эффективности выбранных методов можно рекомендовать три характеристики: время, затраченное на получение решения; точность решения; чувствительность к изменению параметра сходимости. Для одномерных методов оптимизации первые две характеристики можно исследовать на типовых тестовых функциях, например, f(x) = sin ^k (x), путем варьирования значений показателя степени k на множестве нечетных чисел от 1 до 79. Отметим, что для всех k min f(x) достигается в точке x ^*= 4,71239, при этом f (x^*) = -1,0. Однако с увеличением k степень гладкости функции, которая обладает узкими впадинами в окрестности x^*, уменьшается. Проверку методов на чувствительность можно осуществить путем варьирования значений параметра сходимости k и параметров алгоритма.

Точность решения можно измерить как относительную (в процентах) ошибку оценивания координаты истинного минимума.

3. Что такое квадратичная форма? Критерии определенности квадратичных форм (теорема Сильвестра)

Квадратичные функции. Во многих задачах оптимизации рассматриваются функции вида:

или в матричном виде:

, (3.1)

где x и b есть векторы – столбцы размерности n;

А – симметричная матрица (n x n);

С – константа.

Градиент и матрица Гессе функции (3.1) равны соответственно

grad f(x) = Ax + b,

H_f(x) = A = (a _{i j}).

Таким образом, для того чтобы функция (3.1) была выпуклой в Rⁿ, достаточно, чтобы матрица А была положительно определена.

Критерии определенности матрицы (теорема Сильвестра).

Положительная определенность:

все диагональные элементы матрицы должны быть положительны;
все ведущие главные определители должны быть положительны.

Положительная полуопределенность:

все диагональные элементы неотрицательны;
все главные определители неотрицательны.

Главный определитель – это определитель главного минора.

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

Стационарной точкой функции f(x) называется такая точка x^*, в которой выполняется равенство

Если стационарная точка не соответствует локальному экстремуму, то она является точкой перегиба или седловой точкой.

Отрицательная определенность.

Если f(x) положительно определена, то функция –f(x) определена отрицательно.

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

Таким образом, первый минор , второй минор , третий и т.д., т.е. знаки чередуются.

Отрицательная определенность:

все диагональные элементы матрицы должны быть отрицательны;
знак главных определителей должен чередоваться с «-» на «+», начиная с «-».

4. Найти минимум целевой функции на отрезке методом Ньютона.

Точность . Начальная точка

Очередная точка ищется по формуле:

Находим производные:

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

Пусть . Т.к. , при итерационного процесс сходится.

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


0	-60	94	0.64	0
0.64	-13.63	52.93	0.9	-22.1
0.9	-1.81	39.14	0.94	-24.01
0.94	-0.05	36.82	0.94	-24.06
0.94	0	36.75	0.94	-24.06

Таким образом, .

5. Является ли выпуклой функция на отрезке .

Находим производные:

Дважды дифференцируемая функция f(x) выпукла на , если вторая производная при всех .

Функция возрастает на интервале: . Функция на отрезке больше или равна нулю при всех значениях этого отрезка, значит, функция выпукла на отрезке .

Унимодальность функции.

Достаточные условия.

Для проверки унимодальности функции f(x) на практике обычно используют следующие критерии:

– если функция f(x) дифференцируема на отрезке [a, b] и производная f'(x) не убывает на этом отрезке, то f (x) Î Q [a, b];

– если функция f(x) дважды дифференцируема на отрезке [a, b] и вторая производная f''(x)≥0 при х Î [a, b], то f(x) ÎQ[a, b].

Необходимые условия.

Функция называется унимодальной на отрезке [a, b], если она непрерывна на [a, b] и существуют числа и , причем , такие, что:

если , то на отрезке функция монотонно убывает;
если , то на отрезке функция монотонно возрастает;
при имеем .

Отметим, что возможно вырождение в точку одного или двух из отрезков , и .

Рассмотрим функцию на отрезке .

Проверяем достаточные условия:

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

Функция убывает на интервале .

Функция возрастает на интервале .

Поскольку по условию, можно принять , тогда и функция монотонно убывает на отрезке . При этом надо взять равным , т.е. . Тпереь выполняются также условия 2) и 3).

Таким образом, - условия унимодальности выполняются.

Функция на отрезке является унимодальной.

6. Метод сопряженных градиентов для квадратичных функций.

Предполагается, что квадратичная функция имеет вид:

Идея метода состоит в последовательном построении направлений , взаимно сопряженных относительно матрицы (-сопряженных). На каждом шаге "" направление получается как линейная комбинация градиентов [] в точке и предшествующих направлений (), причем коэффициенты линейной комбинации выбираются так, чтобы было сопряженным ко всем предшествующим направлениям.

Для удобства введем обозначения: .

Таким образом,

Запишем изменение градиента при переходе от точки к точке . С учетом обозначений имеем:

или ,

что выражает свойство квадратичных функций.

Схема алгоритма МСГ.

Положить .

Ш. 1 Пусть - начальная точка; ,

Ш. 2 Определить , где

Затем ,

находится из условия (сопряжены относительно матрицы ).

Ш. 3 Положить Ш. 2.

Критерий останова одномерного поиска вдоль каждого из направлений записывается в виде: .

Значения выбираются таким образом, чтобы направление было -сопряжено со всеми построенными ранее направлениями.

7. Метод Дэвидона–Флетчера–Пауэлла.

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

Если функция не квадратичная, то МН не отличается высоким быстродействием и надежностью. В модифицированном МН последовательность итераций строится в соответствии с формулой: .

Метод сопряженных градиентов.

Предполагается, что квадратичная функция имеет вид:

Для удобства введем обозначения: .

Таким образом,

Запишем изменение градиента при переходе от точки к точке . С учетом обозначений имеем:

или ,

что выражает свойство квадратичных функций.

Метод Флетчера–Ривза (МФР).

Флетчер и Ривз расширили предшествующий метод на случай произвольных функций. В применении к квадратичным функциям он становится равносильным методу сопряженных градиентов.

Квазиньютоновские методы основаны на свойствах квадратичных функций. Данные методы обладают положительными чертами метода Ньютона, однако используют только первые производные. С чем это связано?

Итерационный поиск по методу Ньютона осуществлялся по формуле (обобщенный случай с ):

. (7.1)

Трудность может возникнуть, когда матрица Гессе не является положительно определенной. В этом случае направление перемещения

(7.2)

может не быть направлением спуска и глобальная сходимость метода не будет обеспечена.

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

, (7.3)

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

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

Следовательно, на конечном этапе сходимости мы вновь придем к методу Ньютона.

Если метод применяется к произвольной функции, то может рассматриваться на каждом шаге как аппроксимация (положительно определенная) обращения матрицы Гессе функции .

Для аппроксимации матрицы пользуются следующим рекуррентным соотношением:

, (7.4)

где - корректирующая матрица.

Матрица будет использоваться в формулах (7.1), (7.2), (7.3). Задача заключается в том, чтобы построить матрицу таким образом, чтобы последовательность давала приближение к . При этом для получения решения требуется один дополнительный поиск вдоль прямой, если - квадратичная функция. Данный подход приводит к успеху при решении задач с нелинейными ЦФ общего вида.

Еще раз напомним свойства квадратичных функций

Изменение градиента при переходе из точки в выражается соотношением

или

. (7.5)

Предположим, что матрица аппроксимируется по формуле

где - скалярная величина. Наиболее предпочтительным является приближение, удовлетворяющее соотношению (7.5), то есть .

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

, .

С другой стороны, можно потребовать, чтобы новое приближение удовлетворяло также формуле (7.5) с учетом свойств квадратичных функций:

, . (7.6)

Подставляя (7.4) в (7.6), получим:

Выразим отсюда :

. (7.7)

С помощью непосредственной подстановки можно убедиться, что матрица

(7.8)

Этот алгоритм использует матрицу коррекции ранга 2. В формуле (7.8) положим

и .

Тогда получим:

(7.9)

Данная рекуррентная формула сохраняет свойства симметрии и положительной определенности матриц. Поэтому, если - симметричная положительно определенная матрица, то матрицы будут так же симметричными положительно определенными матрицами (см. ниже теорему).

Обычно удобно выбирать , где - единичная матрица. Точка получается из перемещением в направлении .

В формуле (4.34): .

Обозначим .

Достоинства метода

Метод ДФП – наиболее широко используемый градиентный метод.
Устойчивость – при решении самых различных задач, возникающих на практике.

Недостаток. Необходимость хранения матрицы порядка .

8. Найти минимум целевой функции одним из квазиньютоновских методов:

Решаем методом Дэвидона–Флетчера–Пауэлла.

Градиент функции:

Направление для поиска:

Находим точку .

Итерация 1.

;

Следующее направление для поиска:

Находим точку

Итерация 2.

;

Следующее направление для поиска:

Находим точку .

Итерации продолжаются аналогично.

9. К какому методу относится данное уравнение

Метод Марквардта
Метод Коши
Модифицированный метод Ньютоа
Метод Ньютона

Итерационная формула метода Ньютона:

Эта формула есть не что иное, как МН в применении к решению системы нелинейных уравнений:

Уравнение относится к методу Ньютона.

Контрольная работа по Методы оптимизации 📙 Контрольная → 🆔 62881