- •О.К. Мурга
- •Оглавление
- •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.3.2. Метод наискорейшего спуска
В этом варианте градиентного метода минимизирующая последовательность {Xk} также строится по правилу (2.22). Однако величина шага ak находится в результате решения вспомогательной задачи одномерной минимизации
min{jk(a) | a>0 }, (2.27)
где jk(a)=f(Xk a· (Xk)). Таким образом, на каждой итерации в направлении антиградиента выполняется исчерпывающий спуск. Для решения задачи (2.27) можно воспользоваться одним из методов одномерного поиска, изложенных в разделе 1, например, методом поразрядного поиска или методом золотого сечения.
Опишем алгоритм метода наискорейшего спуска.
Шаг 0. Задать параметр точности e>0, выбрать X0ÎEn, положить k=0.
Шаг 1. Найти (Xk) и проверить условие достижения заданной точности || (xk) ||£ e. Если оно выполняется, то перейти к шагу 3, иначе к шагу 2.
Шаг 2. Решить задачу (2.27), т.е. найти ak. Найти очередную точку , положить k=k+1 и перейти к шагу 1.
Шаг 3 Завершить вычисления, положив X*= Xk, f *= f(Xk).
2.3.3. Типовой пример
Минимизировать функцию
f(x)=x12 +4x22 6x1 8x2 +13; (2.28)
Вначале решим задачу классическим методом. Запишем систему уравнений, представляющих собой необходимые условия безусловного экстремума
Решив ее, получим стационарную точку X*=(3;1). Далее проверим выполнение достаточного условия, для чего найдем матрицу вторых производных
f ¢¢(X)=
Так как, согласно критерию Сильвестра, эта матрица положительно определена при , то найденная точка X* является точкой минимума функции f(X). Минимальное значение f *=f(X*)=0. Таково точное решение задачи (11).
Выполним одну итерацию метода градиентого спуска для (2.28). Выберем начальную точку X0 =(1;0), зададим начальный шаг a=1 и параметр l=0,5. Вычислим f(X0)=8.
Найдем градиент функции f(X) в точке X0
(X0)= = (2.29)
Определим новую точку X=X0-a· (X0), вычислив ее координаты
x1=
x2= (2.30)
Вычислим f(X)= f(X0a· (X0))=200. Так как f(X)>f(X0), то выполняем дробление шага, полагая a=a·l=1·0,5=0,5. Снова вычисляем по формулам (2.30) x1=1+4a=3; x2=8a=4 и находим значение f(X)=39. Так как опять f(X)>f(X0), то еще уменьшаем величину шага, полагая a=a·l=0,5·0,5=0,25. Вычисляем новую точку с координатами x1=1+4·0,25=2; x2=8·0,25=2 и значение функции в этой точке f(X)=5. Поскольку условие убывания f(X)<f(X0) выполнено, то считаем, что найдена очередная точка минимизирующей последовательности X1=(2;2). Первая итерация градиентного спуска завершена.
Выполним одну итерацию по методу наискорейшего спуска для (2.28) с той же начальной точкой X0=(1;0). Используя уже найденный градиент (2.29), находим
X= X0-a· (X0)
и строим функцию j0(a)=f(X0-a· (X0))=(4a-2)2+4(8a-1)2. Минимизируя ее с помощью необходимого условия
j 0¢(a)=8·(4a - 2)+64·(8a - 1)=0
находим оптимальное значение величины шага a0=5/34.
Определяем точку минимизирующей последовательности
X1= X0-a0· (X0) .
Первая итерация завершена. Подсчитав компоненты вектора (X1)
можно убедиться, что скалярное произведение
< (X0), (X1)> ,
то есть что Х1 – точка минимума функции (2.28).