Методы оптимизации функций многих переменных

Методические указания к лабораторным работам

по дисциплине "Информационные системы на предприятии"

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

2006

УДК 519.8 (075.8)

доцент, к.т.н. В.А.Пухов

МЕТОДЫ ОПТИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Методические указания к лабораторным работам по дисциплине

“ Методы оптимизации и нелинейное программирование ”/ 2006. 32 с.

В методических указаниях приведен краткий обзор основных методов решения задач и задания для выполнения лабораторных работ по двум темам курса «Методы оптимизации и нелинейное программирование»: решение нелинейных задач безусловной оптимизации и задач с ограничениями. Приведены варианты заданий к лабораторным работам, примеры выполнения заданий, требования к оформлению отчета и контрольные вопросы.

Библиогр.: 6 назв. Прил. 1.

Подготовлено кафедрой “Информатики и информационных технологий”.

Ó, 2006

Введение

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

Данные указания содержатописание выполнения двух лабораторных работ: методы безусловной и условной оптимизации. В теоретической части по каждой теме приводятся базовые понятия, теоремы и алгоритмы, которые потребуются для выполнения работ. Для выполнения графической и расчетной части задач и реализации численных методов оптимизации студенты должны применить знание языков программирования и пакетов MATLAB, MATCAD, EXCEL. Выбор конкретного инструмента оставляется самому студенту.

Проведенные вычисления, графические работы, анализ полученных результатов должны быть оформлены в виде отчета в соответствии со стандартными требованиями, предъявляемыми к отчетам и пояснительным запискам [1]. Сведения из теории, содержащиеся в данных методических указаниях, в отчет включать не рекомендуется.

Введение 3 Лабораторная работа № 2. Методы безусловной оптимизации 4

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

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

1.2. Численные методы минимизации функции 6

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

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

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

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

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

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

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

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

IV. Задания для лабораторного практикума 15

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

Лабораторная работа №3. Методы условной оптимизации 16

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

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

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

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

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

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

IV. Задания для лабораторного практикума 27

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

Литература 28

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

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

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

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

Цель лабораторной работы: закрепление навыков исследования функций на выпуклость; решение задач на нахождение безусловного экстремума выпуклой функции аналитически и численными методами; изучение способов визуализации функций двух переменных в EXCEL и MATLAB.

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

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

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

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

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

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

Grad f(x^*)=0 (2)

2. Пусть функция f(x) дважды дифференцируема в точке х^*Еⁿ. Тогда

   1. Если х^* - точка локального минимума в задаче (1), то матрица Гессе Н(х^*) неотрицательно определена, то есть, для любого вектора р выполняется неравенство

(Н(х^*) р,р) ≥0.

2. Если х^* - точка локального минимума в задаче (1), то матрица Н(х^*) неположительно определена, то есть, для вектора любого р выполняется

(Н(х^*) р,р) ≤0.

3. Пусть функция f(x) дважды дифференцируема в точке х^* Еⁿ и f(x^*)=0.

   1. Если матрица Н(х^*) положительно определена, то есть, (Н(х^*) р,р) ≥0, для любого вектора р ≠0, то х^* - точка строгого локального минимума функции f(x) на Еⁿ.

   2. Если матрица Н(х^*) отрицательно определена, то есть, (Н(х^*) р,р) 0 для любого вектора р≠ 0, то х^* - точка строгого локального максимума функции f(x) на Еⁿ.

Для выпуклой (вогнутой) на Еⁿ функции стационарные точки являются точками ее глобального минимума (максимума). Строго выпуклые (вогнутые) функции имеют единственный глобальный минимум (максимум).

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

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

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

1. Составить и решить систему алгебраических уравнений (2).

2. В стационарных точках (точках, являющихся решением системы) исследовать на знакоопределенность матрицу вторых производных; точки, в которых Н(х)>0, являются точками глобального минимума; стационарные точки, в которых Н(х)<0, являются точками глобального максимума.

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

4. Найденные точки локального экстремума исследуются на глобальный экстремум (если это возможно). В частность, если матрица Гессе неотрицательно (неположительно) определена на всем пространстве Еⁿ, то все стационарные точки функции являются точками глобального минимума (максимума).