- •О.К. Мурга
- •Оглавление
- •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.4. Порядок выполнения лабораторной работы
Кратко описать изучаемые прямые методы безусловной минимизации функций многих переменных.
Выполнить алгоритмическую реализацию описанного метода деформируемого многоугольника.
Дать геометрическую иллюстрацию указанной преподавателем задачи и выполнить вручную две итерации по составленному алгоритму.
Провести с использованием компьютерного комплекса расчеты полученной задачи при различных значениях параметров алгоритма.
Проанализировать влияние параметров алгоритма на его сходимость. Дать геометрическую интерпретацию поиска.
Сформулировать вывод о влиянии параметров алгоритма на эффективность поиска решения задачи. Содержание работы отразить в отчете.
2.1.5. Задания для лабораторной работы
Минимизировать функцию f(X)=2x12+x22x1x2,используя в качестве начального многогранник с вершинами X1=(2;2)T, X2=(3;2,5) T, X3=(2;3)T.
Минимизировать функцию f(X)=5x12+5x22+8x1x2,используя в качестве начального многогранник с вершинами X1=(-1;4)T, X2=(-1;8) T, X3=(-3;6)T.
Минимизировать функцию f(X)=4x12+x2240x112x2+136,используя в качестве начального многогранник с вершинами X1=(8;9)T, X2=(10;11)T, X3=(8;11)T.
Минимизировать функцию f(X)=2x12+2x22+2x1x214x112x2+29, используя в качестве начального многогранник с вершинами X1=(6;3)T, X2=(9;3)T, X3=(7;4)T.
Минимизировать функцию f(X)=x12+4x2210x148x2+169, используя в качестве начального многогранник с вершинами X1=(7;3)T,X2=(9;1)T,X3=(9;3)T.
Минимизировать функцию f(X)=x12+9x224x118x2+13,используя в качестве начального многогранник с вершинами X1=(4;3)T, X2=(6;3)T, X3=(6;4)T.
Минимизировать функцию f(X)=9x12+x2236x12x2+37,используя в качестве начального многогранник с вершинами X1=(5;3)T, X2=(7;5)T, X3=(5;5)T.
Минимизировать функцию f(X)=100(x2x12)2+(1x1)2, используя в качестве начального многогранник с вершинами X1=(-1;1)T, X2=(-0,5;1)T, X3=(-1;2)T.
2.2 Методы покоординатного спуска
Рассмотрим прямые методы решения задачи безусловной минимизации (2.1), использующие вместо итерационных процедур вида (2.3) простейшие вычислительные алгоритмы, основанные на рекуррентной формуле
Xk+1= Xk+ kSk, (2.12)
где Sk – направление поиска точки Xk+1 из точки Xk, а положительное число k – величина шага в этом направлении.
Способ выбора Sk и k будет определять одну из четырех рассматриваемых далее модификаций метода покоординатного спуска.
2.2.1 Метод циклического покоординатного спуска
Метод циклического покоординатного спуска заключается в изменении каждый раз одной переменной, тогда как другие остаются постоянными. Опишем этот метод для задачи (2.1).
Пусть X0– некоторое начальное приближение, а 0–некоторое положительное число, являющееся параметром алгоритма. Допустим, что уже известны точка XkÎEn и число k0 при некотором k0. Обозначим ej=(0,…,0,1,0,…,0)–единичный координатный вектор, у которого j-я координата равна 1, остальные равны нулю, j=1,…,n. Положим
Sk=ejk, jk=kn +1, (2.13)
где целая часть числа k/n. Условие (2.13) обеспечивает циклический перебор координатных векторов e1,…,en, т.е. S0=e1,…, Sn-1=en, Sn=e1,…,
S2n-1=en, S2n=e1….
Вычислим значение функции f(X) в точке X= Xk+ kSk и проверим неравенство
f(Xk+ kSk) f(Xk). (2.14)
Если оно выполняется, то полагаем
Xk+1= Xk+ kSk, k+1=k. (2.15)
В случае, если условие (2.14) не выполняется, вычисляем значение функции f(X) в точке X= Xk kSk и проверяем неравенство
f(Xk - kSk) f(Xk). (2.16)
При выполнении условия (2.15) полагаем
Xk+1= Xk - kSk, k+1=k. (2.17)
Будем считать (k+1)–й этап удачным, если выполнилось хотя бы одно из условий (2.14) или (2.16). Если же ни одно из этих условий не выполнено, считаем (k+1)–й этап неудачным и полагаем
Хk+1=Xk, k+1= (2.18)
где (0;1) –фиксированное число, являющееся параметром алгоритма. Условие (2.18) означает, что если за один цикл из n этапов при переборе направлений всех координатных векторов e1,…,en с шагом k реализовался хотя бы один удачный этап, то длина шага k не дробится и сохраняется на протяжении по крайней мере следующего цикла из n этапов. Если же среди последних n этапов ни одного удачного не оказалось, то шаг k дробится.
Скорость сходимости данного метода невысока. Несмотря на это, метод циклического покоординатного спуска широко применяется на практике благодаря простоте реализации.
Заметим, что такой метод работает плохо, если в выражение минимизируемой функции входят произведения x ix j, т.е. если имеет место взаимодействие между x i, i=1,…,n.
Указанного в конце предыдущего пункта недостатка можно избежать с помощью следующей модификации метода покоординатного спуска, известной под названием метода Зейделя.