Министерство образования РФ

Владимирский государственный университет

Кафедра физики и прикладной математики

Методические указания к лабораторным работам по курсу лекций "методы оптимизации" Сост. К.В. Демидов, а. В. Духанов

Владимир 2003

Сост: доц. Демидов, асс. Духанов

Методические указания к лабораторным работам по курсу лекций "Методы оптимизации" /Владим. гос. ун-т; Сост: К.В. Демидов, А.В. Духанов. Владимир, 2003.

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

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

Содержание

Лабораторная работа № 1. Минимизация функций одной переменной методами дихотомии и золотого сечения 4

Лабораторная работа №2. Метод ломаных 9

Лабораторная работа №3. Метод касательных 14

Лабораторная работа №4. Градиентные методы 17

Лабораторная работа №5. Метод покоординатного спуска 24

Лабораторная работа №6. Метод штрафных функций 26

Список литературы 30

Лабораторная работа № 1. Минимизация функций одной переменной методами дихотомии и золотого сечения

Постановка задачи

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

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

Опр. 1. Функция является унимодальной на отрезке , если непрерывна на и , такие, что

1)  строго монотонно убывает при (если );

2)  строго монотонно возрастает при (если );

3)  , при .

Случаи, когда один или два из отрезков вырождаются в точку, не исключаются.

Метод дихотомии (деления отрезка пополам)

Алгоритм

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

Определим точки по формулам:

(1)

Рис. 1. Определение точек и .

Найдем и сравним значения функции в точках . Здесь возможны два случая:

1)  (см. рис. 1);

2)  .

Определим новый отрезок в зависимости от того, какой из этих случаев имеет место. В первом случае концы отрезка (рис. 1) определяются следующим образом:

, (2)

во втором случае

(3)

Для нового отрезка заново вычисляются точки по формуле (1) и определяется очередной отрезок меньшей длины при помощи формул (2) или (3). Дальнейшие итерации выполняются аналогично. При этом в силу унимодальности функции искомая точка минимума принадлежит каждому из построенных отрезков.

Итерации по определениию отрезков продолжаются до тех пор, пока не будет достигнута заданная точность .

Определение количества итераций при заданной точности

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

. (5)

Учитывая необходимость достижения заданной точности , получаем, что количество требуемых итераций должно удовлетворять неравенству:

(6)

или

(7)