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

Министерство образования  Российской  Федерации

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТ

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

по дисциплине “Методы оптимизации“.

Автор методического  обеспечения: А.А. Мицель, А.А. Шелестов.

 

 

 

 

 

 

 

 

                                                                                     

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

-  Томск  2005 -

 

 

Задания:

 

1. Унимодальные функции. Критерии для проверки унимодальности.
2. Основные критерии останова работы оптимизационных алгоритмов.
3. Сравнение эффективности одномерных методов оптимизации.
4. Среди всех прямоугольников заданной площади S определить прямоугольник, имеющий наименьший периметр.
5. Экспериментами установлено, что траектория космического корабля описывается уравнением    . Найти корень уравнения любым методом с использованием производных.
6. Метод Поллака-Рибьера.
7. Вариант Бройдена-Флетчера-Гольдфабра-Шенно.
8. Найти минимум целевой функции методом Ньютона.

                 x0= (15,23 ;4,41);

9.   Задана функция   и две первые точки, найденные  

            в процессе поиска минимума  x0= [-1,2;1]   x1 = [-1.3; 0.7]. Методом Коши найти

      направление  поиска точки x2.

10. Осуществить одну  итерацию по методу Хука-Дживса. Предложить варианты

      модификации, улучшающие его эффективность. ;

      x0 =  [-1,-1];

 

 

 

 

 

Задание №1.

    Унимодальные функции. Критерии для проверки унимодальности.

 

Ответ:

    Если функция имеет один локальный  экстремум, то она называется унимодальной. 

Критерий  унимодальности класса дифференцируемых функций одной переменной.

Предположим, что в некоторой точке а:

                                          - f’(a)  = 0;

                                          - f’’(a) ≠ 0.

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

 

Дополнение:

 

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

 Общематематический  интерфейс связывает «моду» с распределением вероятностей. Там унимодальности проверяются, например, с помощью неравенств Чебышева.

Берклеевский курс физики  отводит  понятию мода содержание - волновой пакет слабо диспергирующий во времени.

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

Кроме того, Функция – это правило соответствия между двумя множествами. Следовательно, оно (правило) не может иметь ни максима, ни минимума.  Максимум может иметь только график функции.

 

   

 

Задание №2.

    Основные критерии останова работы оптимизационных алгоритмов

 

Ответ:

При нахождении точки оптимизирующей решение задания используется понятие  нормы. Положим, что при поисках решения варьируются несколько параметров . Эти параметры описывают «точку» n- мерного пространства. Нормой пространства называется неотрицательная функция, обозначаемая   переменных  . 

 Сами «точки»  образовывают векторное пространство.

  Точка называется точкой останова, если норма разности    

  где  - точность, задаваемая условиями решения.

Обычно строится последовательность  точек  являющихся всё более точными  приближениями нужного решения. Если »  n- мерное пространство полное и последовательность приближений является последовательностью Коши то условие

 обеспечивает сходимость  к  .

 

Добавление: Различают  методы  функциональной оптимизации (выход из задачи по достижении максимума или минимума значения функции), векторной оптимизации для случаев, когда оптимальность определяется значениями, оптимизирующими несколько функций. В теории полезности  используется критерий предпочтения. Особый интерес представляют критерии оптимальности, используемые в теории решения «неточных» задач. (См. М.М.Ботвинник «Алгоритм игры в шахматы» ).

 

 

Задание №3.

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

 

Ответ:

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

  Так, заменяя функцию её аппроксимацией, мы заранее соглашаемся на неточность решения.

 

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

 

Задание №4.

   Среди всех прямоугольников заданной площади S определить прямоугольник, имеющий наименьший периметр.

 

Решение:

    Пусть x одна сторона прямоугольника. Т.к. S = x*y то вторая его сторона

S/x. Периметр L = 2(x+S/x).

Производная полученного выражения  обращается в нуль

При . Поскольку вторая производная   при x>0 положительна, в точке  имеет место минимум.

      Ответ: Оптимальный по условию задачи прямоугольник –  квадрат со стороной ед. длины.

 

 

Задание №5.

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

 

Решение:

    Пусть   значение функции отличное от нуля. Примем . Тогда . Новое значение   Последовательность 

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

 

Вычисления приведены в таблице.  Ответ

   

.

 

Xn	F(x)	F’(x)	Xn+1
0.75000	2.95499	4.97750	0.45316
0.45316	1.91681	2.37246	0.04920
0.04920	1.11651	2.24632	-0.19932
-0.19932	0.35563	4.12528	-0.24243
-0.24243	0.16768	4.60274	-0.26064
-0.26064	0.08189	4.81799	-0.26914
-0.26914	0.04051	4.92115	-0.27326
-0.27326	0.02015	4.97174	-0.27528
-0.27528	0.01005	4.99679	-0.27629
-0.27629	0.00502	5.00926	-0.27679
-0.27679	0.00251	5.01549	-0.27704
-0.27704	0.00125	5.01859	-0.27717
-0.27717	0.00063	5.02015	-0.27723
-0.27723	0.00031	5.02092	-0.27726
-0.27726	0.00016	5.02131	-0.27728
-0.27728	0.00008	5.02150	-0.27728
-0.27728	0.00004	5.02160	-0.27729
-0.27729	0.00002	5.02165	-0.27729
-0.27729	0.00001	5.02167	-0.27729

 

 

Задание №6.

   Метод Поллака-Рибьера.

 

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

Метод реализуется с помощью  следующих соотношений:

где - параметр, значение которого определяется в результате поиска вдоль прямой.

 

 

Задание №7.

   Вариант Бройдена-Флетчера-Гольдфабра-Шенно.

 

Ответ:

   Последовательность  итераций  строится в соответствии с  правилом

     где направление поиска на К-Ом шаге, определяемое правилом

       . -квадратная матрица, изменяющаяся на каждом шагу и носящая название метрики.

     (1)

Матрица удовлетворяет отношению:

        (2)

Если переставить местами и в (1) и рассмотреть последовательность матриц

       (3)

то полученные матрицы будут  удовлетворять соотношению, обратному (1):

       (4)

Таким образом, выражение (3) позволяет построить аппроксимацию самого гессиана (а не его обращения). Следовательно, можно получить формулу для аппроксимации обращения гессиана из (3):

        (5)

Заменяя на , получим:

     (6)

Формулу (6) можно переписать в виде:

        (7)

 

Задание №8.

 

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

             x0= (15,23 ;4,41);

 

Решение:

 

X                y	X                     Y	X            Y	X              Y
9.717120  4.410000   6.737948  4.410000   5.351773  4.410000   4.859116  4.410000   4.730615  4.410000   4.702820  4.410000   4.697162  4.410000   4.696027  4.410000   4.695800  4.410000   4.695754  4.410000   4.695745  4.410000   4.695743  4.410000   4.695743  4.410000   4.695743  4.410000	4.695743  4.775589   4.695743  4.775589   4.695743  4.831914   4.695743  4.842785   4.695743  4.844945   4.695743  4.845376   4.695743  4.845462   4.695743  4.845480   4.695743  4.845483   4.695743  4.845484   4.695743  4.845484   4.695743  4.845484	4.881223  4.845484   4.914090  4.845484   4.920532  4.845484   4.921815  4.845484   4.922072  4.845484   4.922123  4.845484   4.922133  4.845484   4.922135  4.845484   4.922136  4.845484   4.922136  4.845484	4.922136  4.938929   4.922136  4.956557   4.922136  4.960045   4.922136  4.960741   4.922136  4.960880   4.922136  4.960908   4.922136  4.960914   4.922136  4.960915   4.922136  4.960915   4.922136  4.960915

.

 

 

X              Y	X              Y	X              Y	X              Y
4.969039  4.960915   4.978153  4.960915   4.979966  4.960915   4.980329  4.960915   4.980401  4.960915   4.980416  4.960915   4.980418  4.960915   4.980419  4.960915   4.980419  4.960915	4.980419  4.984412 4.980419 4.989045 4.980419  4.989969 4.980419  4.990154 4.980419  4.990191 4.980419  4.990198 4.980419  4.990200	4.980419  4.990200 4.992179  4.990200 4.994515  4.990200 4.994981  4.990200 4.995074  4.990200 4.995093  4.990200 4.995097  4.990200 4.995097  4.990200 4.995098  4.990200	4.995098  4.996083 4.995098  4.997255 4.995098  4.997490 4.995098  4.997536 4.995098  4.997546

 

Предъявляются результаты вычислений, проведённые по методу Ньютона. 

Схема вычислений:

 

1. Фиксируется вторая переменная.
2. С помощью метода касательных отыскивается точка x для которой

F’(x) = 0. Правило итераций  x_n+1= x_n –0.5*f(x_n)/f’(x_n);

3. Фиксируется первая переменная.
4. С помощью метода касательных отыскивается точка y для которой

F’(y) = 0. Правило итераций  y_n+1= y_n –0.5*f(y_n)/f’(y_n);

  

                 Если нужная точность не  достигнута, то возврат к п.1

                 5    Конец работы.  

 

 

Задание №9.

   Задана функция  и две первые точки, найденные в   процессе поиска минимума  x0= [-1,2;1]   x1 = [-1.3; 0.7]

Методом Коши найти направление  поиска точки x2.

 

Решение:

            Метод Коши – это метод антиградиентного спуска.

           f(x0)= 8.712;   f(x1) = 85,843;

            Вектор – градиент

                                             (-498,93; -198);

             Противоположный градиенту вектор           (498,93; 198);

 

   

Задание №10.

   Осуществить одну итерацию по методу Хука-Дживса.

  Предложить варианты модификации, улучшающие его эффективность.

  ;  x0 = [-1,-1];

 

Решение:

Задаётся шаг оптимизации: h = 0.01;

Начальный вектор принимается равным  [-1,-1];

     F(x0) = 7

По числу переменных.

F(-1+h. -1 ) =  6.9502;  т.е. x1 = (-0.99;-1);

Второй шаг

      F(-0.99,-1+h) = 6.8607<6.9502 т.е. итог итерации  (-0.99;-0.99);

 

 

Список использованной литературы:

 

1. Акулин. Математическое программирование в примерах и задачах. Москва. Высшая школа. 1993г.
2. Рубан А.Н. Оптимизация систем. Учебное пособие. – Томск: Изд-во Томск.
3. Аоки М. Введение в методы оптимизации. – М.: Наука, 1988.
4. Гилл Ф. и др. Практическая оптимизация.– М.: Мир, 1992.
5. Бахвалов Н.С. Численные методы. – М.: Наука, 1989.
6. Полак Э. Численные методы оптимизации. Единый подход. – М.: Мир, 1994.
7. Справочная служба «Yandex».