- •О.К. Мурга
- •Оглавление
- •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.2.6. Порядок выполнения лабораторной работы
1. Кратко описать изучаемые методы покоординатного поиска минимума функций многих переменных.
2. Составить алгоритм метода циклического покоординатного поиска.
3. Дать графическую иллюстрацию задачи индивидуального задания и выполнить вручную по две итерации циклического покоординатного поиска и Зейделя.
Выполнить с использованием компьютерного комплекса расчеты индивидуальной задачи по каждому из рассмотренных алгоритмов.
5. Провести сравнительный анализ полученных результатов. Дать геометрическую интерпретацию решения задачи по каждому из алгоритмов.
6. Сформулировать выводы об эффективности изученных методов покоординатного. спуска. Содержание проделанной работы отразить в отчете.
2.2.7. Задания для лабораторной работы
1. Минимизировать функцию f(X)=5x12+5x22+6x1x2 из начальной точки X0=(2;4)T.
2. Минимизировать функцию f(X)=5x12+5x226x1x2 из начальной точки X0=(-4;3).
3. Минимизировать функцию f(X)=5x12+5x22+8x1x2 из начальной точки X0=(3;5)T.
4. Минимизировать функцию f(X)=5x12+5x228x1x2 из начальной точки X0=(-3;4)T.
5. Минимизировать функцию f(X)=2x12+x22x1x2 из начальной точки X0=(-1;2)T.
6. Минимизировать функцию f(X)=2x12+2x22+2x1x214x112x2+29 из начальной точки X0=(-1;4)T.
7. Минимизировать функцию f(X)=2x12+2x222x1x24x12x2+5 из начальной точки X0=(-1;3)T.
8. Минимизировать функцию f(X)=100(x2x12)2+(1 x1) 2 из начальной точки X0=(-1;0)T.
2.3. Градиентные методы
Рассмотрим задачу безусловной минимизации (2.1) предполагая, что функция f(X) непрерывно дифференцируема на En. Для численного решения задачи применим простейшую итерационную процедуру вида
Xk+1= Xk+ akSk, k=0,1,2,..., (2.21) позволяющую при определенных условиях построить минимизирующую последовательность для функции f(X), т.е. такую последовательность точек ХkEn , что f*.
От того, как выбирается направление поиска Sk и как определяется величина шага ak,зависят свойства итерационной процедуры (2.21) такие, как поведение функции f(X) на элементах последовательности {Xk}, сходимость к решению, скорость сходимости, объем требуемых вычислений.
Известно, что направление наибыстрейшего возрастания функции f(X) в точке X совпадает с направлением градиента функции f(X), то есть вектора
(X)= ,
а направление наибыстрейшего убывания – с направлением антиградиента, то есть вектора . Это свойство градиента и лежит в основе итерационных процедур градиентных методов, которые отличаются друг от друга лишь способом выбора величины градиентного шага.
2.3.1. Метод градиентного спуска
В соответствии с основной идеей градиентного метода будем строить элементы минимизирующей последовательности {Xk} с помощью рекуррентной формулы (2.21), где в качестве направления Sk выбирается направление антиградиента, как направление наискорейшего убывания функции f(X) в малой окрестности точки Xk. То есть, вычислительная схема метода градиентного спуска такова:
Xk+1= xk ak · (X k), k=0,1,2,… (2.22)
Величина шага выбирается так, чтобы выполнялось условие
f(Xk+1) < f(Xk) , k=0,1,2,... (2.23)
В качестве критерия окончания счета на практике используют условия
| f(Xk+1) f(Xk) | £ e1, (2.24)
|| Xk+1 Xk || £ e2, (2.25)
|| (Xk) || £ e3, (2.26)
где ei заданные параметры точности.
Опишем алгоритм рассмотренного метода градиентного спуска.
Шаг 0. Задать параметр точности e>0, начальный шаг a>0, параметр алгоритма lÎ(0;1), выбрать X0ÎEn, вычислить значение f(X0), положить k=0.
Шаг 1. Найти градиент (Xk) и проверить условие достижения заданной точности || (Xk) || £ e. Если оно выполняется, то перейти к шагу 4, иначе к шагу 2.
Шаг 2. Найти новую точку в направлении антиградиента X= Xk a· (Xk) и вычислить f(X). Если f(X) < f(Xk), то положить Xk+1=Xk, f(Xk+1)=f(Xk), k=k+1, и перейти к шагу 1, иначе перейти к шагу 3.
Шаг 3. Положить a=a·l, где 0<l<1 и перейти к шагу 2.
Шаг 4. Завершить вычисления, положив X*= Xk, f *= f(Xk).