Метод средней точки (метод Больцано)

ПОяснительная записка к курсовому проекту

По курсу: “Оптимизация в САПР”

Студент группы 2311     _________          С.А. Мальгин

Санкт-Петербург 2005

Оглавление

Задание на проектирование_ 4

Введение_ 5

МетодЫ решения оптимизационной задачи_ 6

Методы одномерной минимизации_ 6

Метод Свенна_ 6

Метод золотого сечения 6

Алгоритм ЗС-1_ 7

Алгоритм ЗС-2_ 8

Метод Фибоначчи_ 8

Алгоритм Фибоначчи-1_ 8

Алгоритм Фибоначчи-2_ 9

Метод средней точки (метод Больцано) 9

Метод квадратичной интерполяции – экстраполяции_ 10

Метод Пауэлла_ 11

Метод Давидона_ 11

Методы многомерной минимизации_ 13

Метод Коши_ 13

Метод Циклического покоординатного спуска_ 13

Метод параллельных касательных_ 14

Метод Гаусса-Зейделя 15

Метод комплексов Бокса_ 15

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

Метод Ньютона_ 19

Метод Зангвилла_ 19

Флетчера-Ривса_ 20

Метод Пауэлла_ 21

Блок-схемы_ 23

Метод Свенна_ 23

Метод ЗС-1_ 24

Метод ЗС-2_ 25

Метод Фибоначчи-1_ 26

Метод Фибоначчи-2_ 27

Метод Больцано_ 28

Метод квадратичной интерполяции – экстраполяции_ 29

Метод Пауэлла_ 30

Метод Давидона_ 31

Результаты тестирования программы__ 35

Результат тестирования методов для одномерной функции_ 35

Результат тестирования методов для двухмерной функции_ 35

Результат тестирования методов для трёхмерной функции_ 36

Результат тестирования методов для четырёхмерной функции_ 36

Результат тестирования метода комплексов Бокса_ 37

Результат тестирования парсера_ 37

Инструкция для пользователя_ 38

Заключение_ 39

Приложение – листинг программы__ 40

Задание на проектирование

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

1. Программа должна позволять:

- проводить оптимизации целевых функций с числом переменных n≤5.

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

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

- задавать с клавиатуры критерий останова (норма градиента и число итераций) и продолжать решение после внесения дополнительных уточнений в текущую точку и критерий останова.

- вводить с клавиатуры минимизируемые функции многих переменных, содержащих скобки, степени и основные математические функции (Eps, Ln, Sin, Cos и т.д.).

2. Программа должна быть дружественной пользователю:

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

- содержать блокировку ошибочных действий при вводе данных и обеспечивать простоту исправления ошибки.

- желательно, чтобы при демонстрационном режиме была возможность выбора из нескольких (трех-пяти) тестовых функций и запуск на поиск решения без ввода вида функции с клавиатуры

3. Программа должна быть хорошо структурирована:

- текст программы должен быть оформлен в соответствии с правилами модульного программирования.

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

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

Введение

Одним из важнейших направлений оптимизации является задача поиска оптимального решения различных функций многих переменных. Поэтому целью курсового проекта является углубленное изучение методов оптимизации в САПР. Наибольший акцент делается на методы безусловной оптимизации. Курсовой проект предполагает разработку программы автоматизированного поиска оптимального решения с использованием процедур, написанных и отлаженных самостоятельно, а также процедур, разработанных ранее при выполнении цикла лабораторных работ в курсах «Методы оптимизации» и «Теория принятия решений». Эти курсы включают в себя следующие основные направления:

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

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

3. Линейный поиск по направлению.

4. Градиентные методы.

5. Методы безусловной оптимизации первого порядка.

6. Методы безусловной оптимизации нулевого порядка.

Для реализации курсового проекта наиболее подходящим и рекомендуемым является алгоритмический язык Microsoft Visual С++ 6.0, т.к. он обладает полным набором средств для создания и управления различными прикладными задачами, в том числе, и задачей поиска минимума функции. При разработке рекомендуется использовались технологии объектно-ориентированного программирования.

МетодЫ решения оптимизационной задачи

Курсовая работа включает в себя подавляющее большинство методов оптимизации, прочитанных в курсах «Методы оптимизации» и «Теория принятия решений». Каждый метод представлен в виде отдельной функции-члена класса. Все однотипные методы (в плане необходимых сведений для поиска) имеют одинаковое число аргументов. В большинстве своём - это начальная точка, погрешность максимальное количество шагов.

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

Методы одномерной минимизации

Метод Свенна

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

Начальный этап.

(1) задать произвольную начальную точку x₀ÎRⁿ

(2) выбрать начальный шаг h=Dx=0,01

Основной этап

Шаг 1. Установить направление убывания функции. Для этого взять x₂=x₁+h. Если f(x₁) <f(x₂), то поменять направление движения: h₁=-h₁ и взять x₂=x₁+h₁.

Шаг 2. Вычислить f_k в точках x_k+1=x_k+h_k, где k=2,3,4,…,m-1; h_k=2h_k-1 – движение с удвоением шага, до тех пор, пока не придём в точку x_m такую, что f(x_m)<f(x_m-1).

Шаг 3. Установить начальный интервал локализации минимума

      a₁=x_m-2

      b₁=x_m

Метод золотого сечения

Метод золотого сечения – это процедура одномерного поиска минимума на интервале [a₁,b₁] или [0,1]. На каждом шаге пробная точка l_k или m_k внутри текущего интервала локализации [a_k,b_k] делит его в отношении, постоянном для всех интервалов - золотое сечение. Можно показать, что , откуда , следовательно , значит . Одним из корней этого уравнения является t₁=0,618 – первое золотое число. Отметим, что t₁²=0,618²=0,382 – второе золотое число. Следует отметить, что в методе золотого сечения имеет место правило симметрии (эквидистантности) точек относительно концов интервала, а также правило одного вычисления, т.е. на каждой итерации требуется одно и только одно новое вычисление (кроме первой итерации), т.к. точки на соседних итерациях совпадают.

Алгоритм ЗС-1

Начальный этап

(1) Выбрать погрешность расчёта e=10^-3¸10^-7. Получить начальный интервал методом Свенна.

(2) Вычислить стартовые точки l₁=a₁+0,382L₁, m₁=a₁+0,618L₁ (следует отметить, что золотые числа следует вычислять точно)

(3) Принять k=1 – счётчик числа итераций

Основной этап

Шаг 1.Сократить ТИЛ рассмотрением 2-х ситуаций:

(1) Если f(l)<f(m),то

a_k+1=a_k

b_k+1=m_k

m_k+1=l_k

l_k=a_k+1+0,382L_k+1

              иначе

a_k+1=l_k

b_k+1=b_k

l_k+1=m_k

m_k=a_k+1+0,618L_k+1

(2) Положить k=k+1, L_k+1=|b_k+1-a_k+1|

Шаг 2. Проверить критерий окончания поиска: если |a_k+1-b_k+1|£e - остановиться – минимум найден. Точнее фиксируем аппроксимирующий минимум как . Иначе вернуться на шаг 1.

Алгоритм ЗС-2

Начальный этап

(4) Выбрать погрешность расчёта e=10^-3¸10^-7. Получить начальный интервал методом Свенна.

(5) Вычислить стартовые точки l₁=a₁+0,382L₁, m₁=a₁+0,618L₁ (следует отметить, что золотые числа следует вычислять точно)

(6) Принять k=1 – счётчик числа итераций

Основной этап

Шаг 1. Взять очередную пробную точку x₂=a_k+b_k-x₁, симметричную исходной и сократить ТИЛ рассмотрением 4-х возможных ситуаций:

(1) Если (x₁<x₂) и (f(x₁)<f(x₂)) то b=x₂;

(2) Если (x₁<x₂) и (f(x₁)>=f(x₂)) то a=x₁;

(3) Если (x₁>x₂) и (f(x₁)<f(x₂)) a=x₂;

(4) Если (x₁>x₂) и (f(x₁)>=f(x₂)) b=x₁;

Увеличить счётчик числа итераций k=k+1

Шаг 2. Проверить критерий окончания поиска: если |a_k+1-b_k+1|£e - остановиться – минимум найден. Точнее фиксируем аппроксимирующий минимум как . Иначе вернуться на шаг 1.

Метод Фибоначчи

Метод Фибоначчи является процедурой линейного поиска минимума унимодальной функции f(x) на замкнутом интервале [a, b], отличающейся от процедуры золотого сечения тем, что очередная пробная точка делит интервал локализации в отношении двух последовательных чисел Фибоначчи. Последовательность чисел Фибоначчи задаётся условиями F₀ = F₁ = 1, F_k+1 = F_k + F_k-1, k = 1,2,... Начальными членами последовательности будут 1, 1, 2, 3, 5, 8, 13,... Стратегия поиска Фибоначчи требует заранее указать n - число вычислений минимизируемой функции и e - константу различимости двух значений f(x). Рассмотрим один из возможных вариантов метода.

Алгоритм Фибоначчи-1

Начальный этап

(1) Задать константу e, начальный интервал [a₁, b₁], длину конечного интервала L_n и определить число n так, чтобы выполнялось условие F_n > (b₁ - a₁)/L_n.

(2) Взять две пробные точки l₁ = a₁ + (F_n-2/F_n)(b₁ - a₁) и m₁ = a₁ + (F_n-1/F_n)(b₁-a₁). Положить k = 1.

Основной этап

Шаг 1. Сократить текущий интервал локализации:

(1) Если f(l_k) < f(m_k), то положить a_k+1 = a_k, b_k+1 = m_k,m_k+1 =l_k и вычислить новую точку l_k+1 = a_k+1 + (F_n-k-2/F_n-k)L_k+1, где L_k+1 = b_k+1 - a_k+1; перейти на шаг 2.

(2) Если f(l_k)>> f(m_k),то положить a_k+1 =l_k, b_k+1 = b_k, l_k+1 = m_k и вычислить m_k+1 = a_k+1 + (F_n-k-1/F_n-k) L_k+1.

Шаг 2. Проверить критерий окончания поиска:

(1) Заменить k на k+1. (2) Если k = n - 1, перейти на шаг 3, иначе - на шаг 1.

Шаг 3. Найти аппроксимирующий минимум х^(*):

(1) Положить m_k = l_k + e.

(2) Если f(l_k) > f(m_k), то x^(*) = (l_k + b_k)/2. В противном случае - x^(*) = (a_k + m_k)/2.

Алгоритм Фибоначчи-2

Начальный этап

(1) Задать константу e, начальный интервал [a₁, b₁], длину конечного интервала L_n и определить число n так, чтобы выполнялось условие F_n > (b₁ - a₁)/L_n.

(2) Выбрать одну пробную точку . Положить

k = 1.

Основной этап

Шаг 1. Проверить критерий окончания поиска: если k=n, то остановиться и положить x*=x₂.

Шаг 2. Сократить текущий интервал локализации рассмотрением 4-х ситуаций, аналогично методу золотого сечения-2.

Метод средней точки (метод Больцано)

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

Начальный этап. Для запуска метода необходимо:

(1) задать [a₁,b₁]- начальный интервал локализации минимума, на границах которого знаки производных различны, т.е. f'¢(a₁)f'¢(b₁)<0; e - малое положительное число;

(2) положить к=1 и перейти к основному этапу.

Основной этап

Шаг 1. Взять пробную точку х_k в центре текущего интервала и проверить критерий окончания поиска: (1) x_k = (a_k + b_k)/2; (2) если ½f'¢(x_k)½ ≤ e и L_k= ½b_k - a_k½≤ e, то остановиться (х_k = х* -аппроксимирующий минимум).

Шаг 2. Сократить текущий интервал:

(1) Если f ¢(x_k) > 0, то положить a_k+1 = a_k и b_k+1 =x_k, в противном случае - a_k+1 =x_k, b_k+1 =b_k;

(2) заменить k на k+1 и вернуться на шаг 1.