Лаб.работа №2. Практическая реализация критериев оптимальности. Методические указания к лабораторной работе 2 по дисциплине "Методы оптимизации"

• Название: Методические указания к лабораторной работе 2 по дисциплине "Методы оптимизации"
• Дата: 11.10.2022
• Размер: 124.5 Kb.
• Имя файла: Лаб.работа №2. Практическая реализация критериев оптимальности.doc
• Тип: Методические указания; #727787

Уральский федеральный университет

Практическая реализация критериев оптимальности
Методические указания к лабораторной работе 2

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

для магистрантов направлений

09.04.01 – Информатика и вычислительная техника

Екатеринбург

2017

I. Теоретический обзор 3

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

Лабораторные задания 5

Задание 1. Классификация задач и методов оптимизации 5

Задание 2. Геометрические и физические свойства производных 6

Задание 3. Критерии оптимальности 6

Задание 4. Линии уровня 6

Задание 5. Числовые характеристики симметричной квадратной матрицы. 6

Задание 6. Формула Тейлора для функции нескольких переменных 7

Задание 7. Нахождение локальных экстремумов 7

Литература 8

Приложение. Рекомендации по использованию EXCEL и MATLAB 8

П1. Построение графиков 8

П2. Действия с матрицами 9

I. Теоретический обзор

1.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) дважды дифференцируема в точке х^* Еⁿ и gradf(x^*)=0.

1. 
   Если матрица Н(х^*) положительно определена, то есть, (Н(х^*) р,р) > 0, p Еⁿ, р≠0, то х^* - точка строгого локального минимума функции f(x) на Еⁿ.
   
2. 
   Если матрица Н(х^*) отрицательно определена, то есть, (Н(х^*) р,р) <0 p Еⁿ, р≠ 0, то х^* - точка строгого локального максимума функции f(x) на Еⁿ.
   
3. 
   Если матрица Н(х^*)-знакопеременная, то х^* не является точкой локального экстремума.
   
4. 
   Если матрица Н(х^*)- полуопределеная, то об оптимальных свойствах х^* ничего сказать нельзя, нужны дополнительные исследования.
   

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

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

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

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

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

Лабораторные задания

Задания содержат параметр V, который определяет вариант заданий. Число V является порядковым номером студента в группе.

Задание 1. Классификация задач и методов оптимизации

1.1. Проведите классификацию задач оптимизации по следующим критериям:

• 
  по наличию ограничений,
  
• 
  по количеству целевых функций;
  
• 
  по виду целевой функции и ограничений;
  
• 
  по характеру оптимальных решений;
  
• 
  по типу переменных;
  
• 
  по количеству переменных
  

1.2. Проведите классификацию методов оптимизации по следующим критериям:

• 
  По количеству итераций;
  
• 
  По порядку применяемых производных;
  
• 
  По скорости сходимости
  

Задание 2. Геометрические и физические свойства производных

2.1. Сформулируйте геометрические и физические свойства 1-ой и 2-ой производных функции одной переменной.
2.2. Сформулируйте определение и геометрические свойства градиента и гессиана функции одной переменной.

Задание 3. Критерии оптимальности

3.1. Сформулируйте необходимые условия локального экстремума 1-го и 2-го порядков.

3.2. Сформулируйте достаточное условие локального экстремума 2-го порядка

Задание 4. Линии уровня

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

4.2. Укажите связь между линиями уровня и градиентами.

4.3. Постройте линии уровня U_α для функции

y = -V*x₁ + 2V*x₂

при α=0, α=1, α=2.

4.4. Постройте линию уровня U_α при α=3 для функции

y = x₁^2 –V*x₁*x₂ +2*x₂^2 + V*x₁.

Вычислите и нарисуйте градиент этой функции в точке (1; 1).

Задание 5. Числовые характеристики симметричной квадратной матрицы.

5.1. Приведите определения и геометрическую интерпретацию числовых характеристик квадратной матрицы:

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

5.2. Найдите гессиан H функции f(x, y) = x^2 +4xy+5y^2 в точке (1; 0).

Постройте множество точек, в которое оператор с матрицей H отображает единичную окружность S₁ с центром в точке (0; 0). Этот образ является эллипсом. Полуоси являются собственными векторами матрицы H, а длины полуосей – собственными числами _i.

5.3. Постройте линию уровня U_α=1 функции f(x, y) в точке (1, 0). Линия уровня также является эллипсом, полуоси которого – собственные векторы, а длин полуосей являются сингулярными числами матрицы и обратно пропорциональны квадратному корню из соответствующего собственного числа, то есть равны 1/_i^0,5. В некотором смысле, два эллипса из пунктов 5.2 и 5.3 являются ортогональными и взаимно-обратными.

Задание 6. Формула Тейлора для функции нескольких переменных

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

6.2. Проведите квадратичную аппроксимацию в точке (1; 1) для функции

F(x, y) = (x + y - V) e ^{– (x^2 – xy + y^2)}

Задание 7. Нахождение локальных экстремумов

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

F(x, y) = (x + y - V) e ^{– (x^2 – xy + y^2)}

7.2. Проверьте правильность нахождения точек экстремума двумя свойствами:

• 
  с помощью графика этой функции,
  
• 
  путем случайного перебора точек в малой окрестности точки локального экстремума.
  

Литература

1. 
   Стандарт предприятия: Общие требования и правила оформления дипломных и курсовых проектов (работ). СТП УГТУ-УПИ 1-96. Екатеринбург, 1996.
   
2. 
   Акулич И.Л. Математическое программирование в примерах и задачах. – М.; Высшая школа, 1993. – 335 с.
   
3. 
   Аттетков А.В., Галкин С.В., Зарубин В.С. Методы оптимизации - М.; Издательство МГТУ им. Н.Э. Баумана, 2004. - 432 с
   
4. 
   Васильев В.П. Численные методы решения экстремальных задач. - М.: Наука, 1980. - 518 с.
   
5. 
   Габбасов Р., Кириллова Ф.М. Методы оптимизации. – Минск: Изд-во БГУ, 1981. -
   
6. 
   Дьяконов В. Matlab: учебный курс / В. Дьяконов. СПб.: Питер, 2001. 560 с.
   
7. 
   Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. – М.; Высшая школа, 2005. – 544 с.
   

Приложение. Рекомендации по использованию EXCEL и MATLAB

П1. Построение графиков

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

1. 
   В EXCEL – Мастер диаграмм, подтип Поверхность.
   
   • 
     Используя автозаполнение, на листе EXCEL в столбец А и первую строку с выбранным шагом ввести соответственно значения переменных x₁ и x₂, для которых будут вычисляться значения функции.
     
   • 
     В ячейку В2 ввести выражение для вычисления функции f(x₁,x₂) в точках $A2, B$1 (знак $ - признак абсолютной адресации, при которой будут зафиксированы первый столбец– перебор значений переменной x₁ и первая строка – перебор значений переменной x₂) и нажать одновременно три клавиши Ctrl, Shift, Enter, поскольку формула используется для обработки массивов. В строке формул должны появиться фигурные скобки.
     
   • 
     Выделить ячейку В2 и, протянув маркер заполнения сначала вниз, пробегая все ячейки, заполненные в столбце А. а затем вправо, пробегая все ячейки, заполненные в строке 1, заполнить массив значений функции в узловых точках области построения графика.
     
   • 
     На вкладке Стандартные Мастера диаграмм выбрать Поверхность. Поверхностная диаграмма дает 3-мерное изображение функции, а Контурная диаграмма представляет вид сверху на поверхностную диаграмму и является аналогом линий уровня исследуемой функции.
     
2. 
   В MATLAB – функции plot3, mesh, surf, surfl.
   
   • 
     С помощью функции meshgrid получить двумерные массивы координат узловых точек области построения графика: u=a:∆₁:b; v=c: ∆₂:d; [x,y]=meshgrid(u,v);
     
   • 
     Задать исследуемую функцию: f= f(х,у);
     
   • 
     Применяя указанные выше функции, получить трехмерное изображение: plot3(x,y,f) или mesh(x,y,f), surf(x,y,f), surfl(x,y,f).
     

П2. Действия с матрицами

Для нахождения собственных значений и собственных векторов матрицы Гессе могут быть использованы следующие инструменты MATLAB

• 
  λ = eig(a) - функция eig(a) возвращает собственные значения заданной матрицы a. Пример задания матрицы 4х4: a = [16 3 2 13; 5 10 11 8; 9 6 7 12; 4 15 14 1] .
  
• 
  [v,d] = eig(a) – при таком обращении функция возвращает собственные векторы v и собственные значения как элементы диагональной матрицы d.
  

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

1. В EXCEL – функция МОБР возвращает обратную матрицу для матрицы, хранящейся в массиве.

2. В MATLAB – функция y=inv(a) возвращает обратную матрицу для матрицы a.