- •О.К. Мурга
- •Оглавление
- •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. Задания для лабораторной работы.
- •Список литературы
Влияние параметров алгоритма на эффективность поиска
Проанализируем влияние параметров a, g, b на эффективность процедуры поиска.
Коэффициент отражения a используется для проектирования вершины с наибольшим значением f(X) через центр тяжести деформируемого многогранника.
Коэффициент g вводится для растяжения вектора поиска в случае, если отражение дает вершину со значением f(X), меньшим, чем наименьшее значение f(X), полученное до отражения.
Коэффициент сжатия b используется для уменьшения вектора поиска, если операция отражения не привела к вершине со значением f(X),меньшим, чем второе по величине, после наибольшего, значение f(X), полученное до отражения.
Таким образом, с помощью операций растяжения или сжатия размеры и форма деформируемого многогранника изменяются так, чтобы они удовлетворяли топологии решаемой задачи. После того, как это изменение выполнено, размеры многогранника поддерживаются неизменными, пока особенности целевой функции не потребуют применения многогранника другой формы. Это возможно реализовать только при =1. Как показывают численные эксперименты, при решении задачи с 1 требуется большее количество вычислений функции. С другой стороны, параметр не должен быть много больше единицы, т.к. деформируемый многогранник легче адаптируется к топологии задачи при меньших значениях . Кроме того, большое значение может замедлить сходимость, т.к. в окрестности минимума размеры многогранника должны уменьшаться. Поэтому значение =1 можно выбрать как компромисс.
Влияние на процедуру поиска параметров и менее четко выражено. Как показывают результаты решения тестовых задач, можно рекомендовать следующие диапазоны значений для этих параметров: 0,40,6; 23. При этом отмечается, что влияние коэффициента на эффективность поиска заметнее, чем влияние . При (0;0,4) имеет место преждевременное окончание поиска, а при 0,6 требуется выполнить больше шагов для достижения окончательного решения.
2.1.3. Типовой пример.
Выполним одну итерацию поиска по методу деформируемого многогранника для задачи минимизации функции f(X)=4(x1-5)2+(x2-6)2.
Поскольку функция зависит от двух переменных, в начале поиска используется многогранник с тремя вершинами X1=(8;9)T, X2=(10;11)T, X3=(8;11)T.
Зададим значения параметров =1, =2. Вычислим значения функции в них : f(X1)=45; f(X2)=125; f(X3)=65.
Вершиной с наименьшим значением функции оказывается XL=X1. Вершиной с наибольшим значением функции является Xh=X2. Далее находим центр тяжести вершин, исключая X2.
.
Отражая “худшую” точку Xh относительно найденной X4 , получим точку
Xn+3= X5= X4+( X4- X2)= ,
значение функции в которой f(X5)=13.
Поскольку f(X5) f(XL)=45, выполняем операцию растяжения, определяя точку
Xn+4= X6= X4+( X5- X4)= ,
и значение функции в ней f(X6)=8,
Так как f(X6) f(XL), заменяем вершину Xh на Xn+4, полагая X2= X6 и тем самым завершая первую итерацию поиска.
На рис.4 приведена геометрическая интерпретация поиска по деформируемому многограннику на пяти начальных этапах минимизации функции f(X)=4x12+x2240x112x2+136.
Рис.4. Траектория поиска по деформируемому многограннику.
Очевидно, линиями уровня функции являются эллипсы . На рисунке изображены линии уровня, соответствующие значениям функции 2, 5, 10, 20 и 30. Пунктиром выделены многогранники с вершинами Xj(i), в обозначениях которых j – номер вершины деформируемого многогранника на i-том этапе поиска. Сплошными линиями показана траектория поиска, соединяющая вершины многогранника, соответствующие наименьшим значениям f(X) в каждом из них. Убедитесь в соответствии графической иллюстрации описанному с помощью формул (6)-(9) алгоритму.