Линейное и нелинейное программирование (стр. 4 из 5)
Решение задачи методом полного перебора составляет 6*25=192 вычисленных выражения. Решение задачи методом Баллаша составляет 3*6+(25-3)=47 вычисленных выражений. Итого снижение трудоемкости вычислений по отношению к решению задачи методом полного перебора составляет
. 3.1 Задача поиска глобального экстремума функции
3.1.1 Постановка задачи поиска глобального экстремума функции
Необходимо написать программа для поиска экстремума функции. Задание состоит в следующем: 1) найти точку глобального экстремума функции f(X) методом поиска по координатной сетке с постоянным шагом; 2) найти точку глобального экстремума функции f(X) методом случайного поиска; 3)сравнить результаты вычислений.
Метод поиска глобального минимума, называемый методом поиска по координатной сетке, является надежным, но применим только для задач малой размерности (n<4). Неправильный выбор начального шага сетки может привести к тому, что в действительности один из локальных минимумов может быть принят как глобальный. Из всех значений целевой функции, вычисленных в узлах координатной сетки, выбирается минимальное. Результат: число испытаний 905, f(X*) = -2.500, X*=(-0.500; 2.000)
Метод случайного поиска характеризуется намеренным введением элемента случайности в алгоритм поиска. Этот метод предполагает наличие генератора случайных чисел, обращаясь к которому, в любой нужный момент времени можно получить реализацию случайного вектора с заданным законом распределения. Результат: число испытаний 299, f(X*) = -2.469, X*=(-0.677; 2.173).
Расчет в системе MathCAD: f(X*) = -2.500, X*=(-0.500; 2.000)
Как видим, метод случайного поиска сократил число испытаний на 66%, при этом относительная погрешность составляет 1%. Т.е. мы достигли значительного сокращения вычислений с небольшой относительной погрешностью.
3.2 Задача одномерной оптимизации функции
3.2.1 Постановка задачи одномерной оптимизации функции
Задание для нахождения одномерного локального экстремума функции (одномерная оптимизация) состоит в том, чтобы выполнить поиск минимума заданной функции методом дихотомии (3-4 итерации), уточнить интервал поиска методом Фибоначчи (3 итерации) и завершить поиск методом кубической аппроксимации.
Итерация 1
Итерация 2
Итерация 3
Итерация 4
После четырех итераций получим:
Итерация 1
Итерация 2
Итерация 3
Итерация 4
Поиск окончен. Длина интервала:
3.2.4 Метод кубической аппроксимации
3.3 Задача многомерной оптимизации функции
3.3.1 Постановка задачи многомерной оптимизации функции
Минимизировать функцию, применяя следующие методы: нулевого порядка – Хука-Дживса, первого порядка – наискорейшего спуска (Коши), второго порядка – Ньютона, и провести сравнительный анализ методов оптимизации по количеству итераций, необходимых для поиска экстремума при фиксированной точности и начальных координатах поиска X(0)=[-1,-1]T.
Итерация 1
1 Исследующий поиск
2 Поиск по образцу
Итерация 2
1 Исследующий поиск
2 Поиск по образцу
Итерация 3
1 Исследующий поиск
2 Поиск по образцу
