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

• Название: 1. Исследование функции на безусловный экстремум 3
• Дата: 20.12.2018
• Размер: 0.69 Mb.
• Имя файла: 1541130846473078.docx
• Тип: Исследование; #61169
• страница: 1 из 6

Оглавление

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

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

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

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

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

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

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

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

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

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

Пример выполнения лабораторной работы 10

3. Решение задачи минимизации со смешанными ограничениями 17

Седловые точки функции Лагранжа 19

Метод седловой точки в задачах квадратичного программирования 21

Метод проекции градиента для задачи условной оптимизации 22

Метод условного градиента для задачи условной оптимизации 22

Метод возможных направлений для задачи условной оптимизации 23

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

Пример выполнения лабораторной работы 24

4. Основные понятия линейного программирования 34

Модель задачи линейного программирования 34

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

Двойственность в линейном программировании 37

5. Задача транспортного типа 39

Построение модели транспортной задачи 39

Методы нахождения начального плана перевозок. 42

Метод потенциалов 43

Контрольные задания 45

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

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

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

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

Задание 5. Одномерная оптимизация 47

Задание 6. Многомерная оптимизация по направлению 47

Задание 7. Методы безусловной оптимизации 48

Контрольные вопросы 48

Задание 8. Методы условной оптимизации 48

Контрольные вопросы 49

Задание 9. Задача линейного программирования и симплекс-метод 49

Задание 10. Транспортная задача 49

Литература 50

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

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

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

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

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

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

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

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

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

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

gradf(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. 
   Найденные точки локального экстремума исследуются на глобальный экстремум (если это возможно). В частность, если матрица Гессе неотрицательно (неположительно) определена на всем пространстве Еⁿ, то все стационарные точки функции являются точками глобального минимума (максимума).