В математике задача оптимизации - это задача на нахождение экстремума ( максимума или минимума) вещественной функции в заданной области. Для решения таких задач используются различные методы. Они делятся на следующие группы:
графические методы,
аналитические методы,
численные методы.
Их использование зависит от конкретной ситуации. Так, например, использование графических методов для нахождения экстремума функции в n-мерном пространстве просто невозможно, в связи с невозможностью графического представления такого пространства, что касается аналитических методов, то их применение усложняется необходимостью указания дополнительных сведений и расчетов. Таким образом, будет целесообразнее использование численных методов.
Численные методы оптимизации можно классифицировать на:
Методы направленного поиска экстремума.
Методы случайного поиска экстремума.
В свою очередь среди методов направленного поиска экстремума выделяют следующие виды:
Методы нулевого порядка, или методы поиска. Эти методы требуют для своей реализации только вычисления значений функции.
Методы первого порядка, или градиентные методы. Данные методы требуют для своей реализации вычисления значений функции и ее первых производных.
Методы второго порядка, или методы Ньютона.
Рассмотрим некоторые алгоритмы безусловной минимизации гладких функций нескольких переменных реализованных с помощью системы MathCAD. Решим задачу минимизации на примере квадратичной функции двух переменных ƒ(x) = ƒ( x1, x2): ƒ(x) = XTAX + BTX + C, где А - матрица 2х2, И - 2-вектор, а С-скаляр.
Исходные данные представления в таблице 1.
Таблица 1.
А, В, С |
Вид экстремума |
min |
Метод Ньютона
Данный метод основан на квадратичной аппроксимации минимизируемой функции в окрестности точки x (k) . Градиент приравнивается к нулю, тем самым облегчая поиск минимума квадратичной функции.
Главным достоинством метода Ньютона заключается в том, что метод позволит найти минимум функции за один шаг, в случае если минимизируемая функция является квадратичной, а также если функция относится к классу поверхностей вращения, т.е. обладает симметрией
Однако у метода есть и свои недостатки. Необходимо вычислять и обращать матрицы вторых производных. Тем самым увеличивается время выполнения программы, а также есть вероятность получения значительных погрешностях в вычислениях. Ниже приведен пример-программа вычисления минимума функции методом Ньютона в математическом пакете MathCad.
Метод наискорейшего спуска
Метод наискорейшего спуска заключается в следующем: определяем в начальной точке антиградиент минимизируемой функции; примечательно, что в направлении антиградиента делаем ни один шаг, а движемся в данном направлении до тех пор, пока целевая функция убывает, достигает в некоторой точке минимума. Затем вновь определяем в этой точке антиградиент и ищем новую точку минимума целевой функции и так далее. В данном методе спуск имеет более целеустремлённый характер, производится более крупными шагами и градиент функции вычисляется в меньшем числе точек.
Ниже приведен код программы в математическом пакете MathCad.
Метод сопряженных градиентов
Данный метод применяется для безусловной оптимизации в многомерном пространстве. Главным достоинством этого метода является то, что он решает квадратичную задачу оптимизации за конечное число шагов. Сначала описывают метод сопряжённых градиентов для оптимизации квадратичного функционала, выводят итерационные формулы и приводят оценки скорости сходимости. А затем показывают, как метод сопряжённых обобщается для оптимизации произвольного функционала, рассматривают различные варианты метода и обсуждают сходимость.
Как и в методе градиентного спуска, в данном методе используется информация только о линейной части приращения в точке. Во многих задачах этот метод превосходит метод градиентного спуска.
Решение исходной задачи приведен ниже в среде MathCad.
Заключение.
При создании и построении систем принятия решений возникает необходимость в решении самых разнообразных задач оптимизации. В статье были рассмотрены методы многомерной оптимизации - методы поиски минимума функции. А также были приведены примеры решения исходной задачи разными методами.
Список литературы
Барабашова О. В., Крушель Е. Г. Алгоритмы поиска экстремума функции многих переменных. Методические указания. - Волгоград. гос. техн. ун-т, Волгоград, 2000. - 30с.
Гладких Б. А. Методы оптимизации и исследование операций для бакалавров информатики. Ч. II. Нелиней- ное и динамическое программирование: учебное пособие. — Томск: Изд-во НТЛ, 2011. — 264 с.
Захарова Е.М., Кузнецов Н.А., Минашина И.К., Пащенко Ф.Ф., Рябых Н.Г. Моделирование алго- ритмов оптимизации мультиагентной системы управления перевозочным процессом. Вестник Меж- дународной Академии Системных Исследований. Информатика, Экология, Экономика. 2014. Т. 16. № -1. С. 9-15. 2.