- •О.К. Мурга
- •Оглавление
- •1. Методы одномерной оптимизации 6
- •2. Методы безусловной оптимизации 13
- •3. Методы оптимизации при наличии ограничений 35
- •4. Приближённое решение задачи оптимального управления 53
- •Введение
- •1. Методы одномерной оптимизации
- •1.1. Методы перебора
- •1.1.1. Метод равномерного поиска
- •1.1.2. Метод поразрядного поиска
- •1.2. Методы исключения отрезков
- •1.2.1. Метод дихотомии
- •1.2.2. Метод золотого сечения
- •1.3. Сравнительный анализ методов одномерного поиска
- •1.4. Порядок выполнения лабораторной работы
- •1.5. Задания для лабораторной работы.
- •2. Методы безусловной оптимизации
- •2.1. Прямые методы безусловной оптимизации
- •2.1.1. Поиск по правильному симплексу
- •2.1.2. Поиск по деформируемому многограннику
- •Влияние параметров алгоритма на эффективность поиска
- •2.1.3. Типовой пример.
- •2.1.4. Порядок выполнения лабораторной работы
- •2.1.5. Задания для лабораторной работы
- •2.2 Методы покоординатного спуска
- •2.2.1 Метод циклического покоординатного спуска
- •2.2.2. Метод Зейделя.
- •2.2.3. Метод Хука-Дживса
- •2.2.4. Метод Пауэлла.
- •2.2.5. Типовые примеры
- •2.2.6. Порядок выполнения лабораторной работы
- •2.2.7. Задания для лабораторной работы
- •2.3. Градиентные методы
- •2.3.1. Метод градиентного спуска
- •2.3.2. Метод наискорейшего спуска
- •2.3.3. Типовой пример
- •2.3.4. Порядок выполнения лабораторной работы
- •2.3.5. Задания для лабораторной работы
- •3. Методы оптимизации при наличии ограничений
- •3.1. Методы последовательной безусловной оптимизации
- •3.1.1. Метод штрафных функций
- •3.1.2. Метод барьерных функций
- •3.1.3. Комбинированный метод штрафных функций
- •3.1.4. Типовой пример
- •3.1.5. Задание для лабораторной работы
- •3.2. Метод возможных направлений
- •3.2.1. Постановка задачи выпуклого программирования
- •3.2.2. Описание метода возможных направлений
- •3.2.3. Построение начального приближения
- •3.2.4. Выбор наилучшего подходящего направления
- •3.2.5. Определение длины шага
- •3.2.6. Типовой пример
- •3.2.7. Задания для лабораторной работы
- •3.3. Метод случайного поиска
- •3.3.1. Поиск с возвратом при неудачном шаге
- •3.3.2. Алгоритм наилучшей пробы
- •3.3.3. Алгоритм статистичекого градиента
- •3.3.4. Порядок выполнения работы
- •3.3.5. Задания для лабораторной работы
- •4. Приближённое решение задачи оптимального управления
- •4.1. Постановка задачи оптимального управления
- •4.2. Градиентный метод решения задачи оптимального управления
- •4.2.1. Описание градиентного метода в функциональном пространстве.
- •4.2.2. Алгоритм метода.
- •4.2.3. Порядок выполнения лабораторной работы.
- •4.2.4. Задания для лабораторной работы.
- •Список литературы
2.1. Прямые методы безусловной оптимизации
2.1.1. Поиск по правильному симплексу
Поиск минимума целевой функции f(x) по данному методу основан на выборе в качестве пробных точек вершин правильного симплекса. Напомним, что правильным симплексом в En называется множество из n+1 равноудаленных друг от друга точек вершин симплекса. Так, в E2 правильным симплексом является равносторонний треугольник, в E3 – тетраэдр.
Из аналитической геометрии известно, что если X0– одна из вершин правильного симплекса в En, то координаты остальных вершин X1,…, Xn находятся по формулам
(2.4) где d1= , d2= , t длина ребра.
По известному симплексу можно построить новый симплекс путем отражения какой-либо вершины симметрично относительно центра тяжести Xс остальных вершин симплекса. Новая и старая вершины k и Xk связаны соотношением
= , = . (2.5)
В результате получается новый правильный симплекс с тем же ребром и вершинами
k=2 Xс Xk, Xj , j=0,…,n, jk.
На рис.1 представлена иллюстрация описанной операции отражения в пространстве E2.
Рис. 1. Построение нового симплекса в Е2 отражением точки X2:
а начальный симплекс X0, X1, X2; б новый симплекс X0, X1, ;
центр отражения точка Xс=( X0+X1)2.
На каждой итерации поиска сравниваются значения функции f(x) в вершинах симплекса и выполняется описанная процедура отражения для той вершины, в которой f(x) принимает наибольшее значение. Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. Иначе выполняют ещё одну попытку отражения для вершины со следующим по величине значением f(x). Если и она не приводит к уменьшению функции, то сокращают длину ребра и строят новый симплекс с этим ребром. При этом в качестве базовой выбирают ту вершину X0 старого симплекса, в которой функция принимает наименьшее значение. Поиск точки минимума X* заканчивают, когда либо ребро симплекса, либо разность между значениями функции в вершинах симплекса становятся достаточно малыми. Опишем один из вариантов алгоритма этого метода.
Шаг 0. Задать параметр точности e, выбрать базовую точку X0 и длину ребра t, построить по формулам (2.4) начальный симплекс и вычислить f(X0).
Шаг 1. Вычислить значения функции f(X) в вершинах симплекса X1,…, Xn.
Шаг 2. Упорядочить вершины симплекса X0,…,Хn так,чтобыf(X0)£…£f(Xn).
Шаг 3. Проверить условие достижения точности
Если оно выполняется, то перейти к шагу 7, иначе – к шагу 4.
Шаг 4. Найти по формуле (4) центр тяжести Xc вершин X0,X1,…,Xn-1и выполнить отражение вершины Xn: n=2Xc Xn.Если f( n) < f(Xn), то положить Xn= n и перейти к шагу 2, иначе – к шагу 5.
Шаг 5. Найти центр тяжести Xc вершин X0,X1,…,Xn-1,Xn и выполнить отражение вершины Xn-1: n-1 =2Xc Xn-1.Если f( n-1)<f(Xn-1), то положить Xn-1= n-1 и перейти к шагу 2, иначе – к шагу 6
Шаг 6. Построить новый правильный симплекс с вдвое меньшим ребром, считая базовой вершину X0, а остальные n вершин находя по формуле Xj=(Xj+ X0)/2, j=1,…,n и перейти к шагу 1.
Шаг 7. Завершить вычисления, положив X*= X0, f *= f(X0).