IX Международная студенческая научная конференция Студенческий научный форум - 2017

При проектировании большинства систем довольно часто возникает необходимость определения наилучших значений параметров или структуры объектов. Такая задача называется оптимизационной. Сегодня оптимизационные задачи используются для решения инженерных, экономических, а также статистических задач.

В математике задача оптимизации - это задача на нахождение экстремума ( максимума или минимума) вещественной функции в заданной области. Для решения таких задач используются различные методы. Они делятся на следующие группы:

• графические методы,

• аналитические методы,

• численные методы.

Их использование зависит от конкретной ситуации. Так, например, использование графических методов для нахождения экстремума функции в n-мерном пространстве просто невозможно, в связи с невозможностью графического представления такого пространства, что касается аналитических методов, то их применение усложняется необходимостью указания дополнительных сведений и расчетов. Таким образом, будет целесообразнее использование численных методов.

Численные методы оптимизации можно классифицировать на:

• Методы направленного поиска экстремума.

• Методы случайного поиска экстремума.

В свою очередь среди методов направленного поиска экстремума выделяют следующие виды:

• Методы нулевого порядка, или методы поиска. Эти методы требуют для своей реализации только вычисления значений функции.

• Методы первого порядка, или градиентные методы. Данные методы требуют для своей реализации вычисления значений функции и ее первых производных.

• Методы второго порядка, или методы Ньютона.

Рассмотрим некоторые алгоритмы безусловной минимизации гладких функций нескольких переменных реализованных с помощью системы MathCAD. Решим задачу минимизации на примере квадратичной функции двух переменных ƒ(x) = ƒ( x¹, x²): ƒ(x) = X^TAX + B^TX + C, где А - матрица 2х2, И - 2-вектор, а С-скаляр.

Исходные данные представления в таблице 1.

Таблица 1.

А, В, С	Вид экстремума
	min

Метод Ньютона

Данный метод основан на квадратичной аппроксимации минимизируемой функции в окрестности точки x ^(k) . Градиент приравнивается к нулю, тем самым облегчая поиск минимума квадратичной функции.

Главным достоинством метода Ньютона заключается в том, что метод позволит найти минимум функции за один шаг, в случае если минимизируемая функция является квадратичной, а также если функция относится к классу поверхностей вращения, т.е. обладает симметрией

Однако у метода есть и свои недостатки. Необходимо вычислять и обращать матрицы вторых производных. Тем самым увеличивается время выполнения программы, а также есть вероятность получения значительных погрешностях в вычислениях. Ниже приведен пример-программа вычисления минимума функции методом Ньютона в математическом пакете MathCad.

 

 

Метод наискорейшего спуска

Метод наискорейшего спуска заключается в следующем: определяем в начальной точке антиградиент минимизируемой функции; примечательно, что в направлении антиградиента делаем ни один шаг, а движемся в данном направлении до тех пор, пока целевая функция убывает, достигает в некоторой точке минимума. Затем вновь определяем в этой точке антиградиент и ищем новую точку минимума целевой функции и так далее. В данном методе спуск имеет более целеустремлённый характер, производится более крупными шагами и градиент функции вычисляется в меньшем числе точек.

Ниже приведен код программы в математическом пакете MathCad.

 

 

Метод сопряженных градиентов

Данный метод применяется для безусловной оптимизации в многомерном пространстве. Главным достоинством этого метода является то, что он решает квадратичную задачу оптимизации за конечное число шагов. Сначала описывают метод сопряжённых градиентов для оптимизации квадратичного функционала, выводят итерационные формулы и приводят оценки скорости сходимости. А затем показывают, как метод сопряжённых обобщается для оптимизации произвольного функционала, рассматривают различные варианты метода и обсуждают сходимость.

Как и в методе градиентного спуска, в данном методе используется информация только о линейной части приращения в точке. Во многих задачах этот метод превосходит метод градиентного спуска.

Решение исходной задачи приведен ниже в среде MathCad.

 

Заключение.

При создании и построении систем принятия решений возникает необходимость в решении самых разнообразных задач оптимизации. В статье были рассмотрены методы многомерной оптимизации - методы поиски минимума функции. А также были приведены примеры решения исходной задачи разными методами.

Список литературы

1. Барабашова О. В., Крушель Е. Г. Алгоритмы поиска экстремума функции многих переменных. Методические указания. - Волгоград. гос. техн. ун-т, Волгоград, 2000. - 30с.

2. Гладких Б. А. Методы оптимизации и исследование операций для бакалавров информатики. Ч. II. Нелиней- ное и динамическое программирование: учебное пособие. — Томск: Изд-во НТЛ, 2011. — 264 с.

3. Захарова Е.М., Кузнецов Н.А., Минашина И.К., Пащенко Ф.Ф., Рябых Н.Г. Моделирование алго- ритмов оптимизации мультиагентной системы управления перевозочным процессом. Вестник Меж- дународной Академии Системных Исследований. Информатика, Экология, Экономика. 2014. Т. 16. № -1. С. 9-15. 2.

Код для цитирования: Скопировать