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

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

 

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

 

 

 

 

 

 

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Томск, 2010 г.

 

 

 

 

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

 

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

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

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

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

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

Так как за каждую итерацию интервал, где расположен корень, уменьшается в два раза, то через 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]  и существуют числа и , причем , такие, что:

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

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

 

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

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

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

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

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

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

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

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

 

 

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

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

.

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