Теория оптимизации

Задачи оптимизации

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

1. Найти максимальную производительность при фиксированной себестоимости. В данном случае критерием оптимизации является производительность.
2. Найти минимальную себестоимость при фиксированной производительности. В данном случае критерием оптимизации является себестоимость.

После этого необходимо осознать, от чего зависит критерий оптимизации – определить влияющие величины, которые можно изменять произвольно. Данный этап является очень важным в осознании задачи оптимизации, так как определяет способ численной оценки критерия. Еще необходимо четко осознать, каким условиям должны удовлетворять элементы, оказывающие влияние на критерий. Таким образом формируется множество оптимизации. На основе выбранного критерия составляется целевая функция, которая представляет собой зависимость критерия оптимальности параметров, влияющих на ее значение. Вид целевой функции или критерия оптимальности определяется конкретной задачей оптимизации. Таким образом задача оптимизации сводится к определению экстремума целевой функции.

Методы оптимизации

Методами оптимизации являются:

1. Методы одномерного поиска. К данным методам относятся метод дихотомии, метод золотого сечения и метод Фибоначчи.
2. Прямые методы поиска. К данным методам относятся алгоритмы Хука и Дживса, Гаусса, Розенброка, а также симплексный метод Нелдера-Мида и метод Пауэлла и сопряженные направления.
3. Методы первого порядка. К данным методам относятся многопараметрический поиск, метод сопряженных градиентов и алгоритм наискорейшего спуска.
4. Методы второго порядка. К данным методам относится метод Ньютона.
5. Методы переменной метрики. К данным методам относятся алгоритм Пирсона, метод Бройдена, алгоритм аппроксимацией матрицы Гессе, метод Дэвидона-Флетчера-Пауэлла, алгоритм Флетчера, проективный алгоритм Ньютона-Рафсона, а также методы Гольдфарба и Гринштата.
6. Методы штрафных функций.
7. Статистические методы поиска. К данным методам относятся алгоритмы глобального поиска, простой случайный поиск, простейшие алгоритмы направленного случайного поиска (метод статистического градиента и алгоритмы наилучшей пробы, парной пробы, наилучшей пробы с направляющим гиперквадратом.
8. Линейное программирование. К данным методам относятся метод последовательного уточнения оценок и симплекс метод.
9. Методы решения транспортной задачи. К данным методам относятся алгоритм метода потенциалов, метод северо-западного угла, метод минимального элемента.
10. Параметрическое линейное программирование.

Методы оптимизации занимаются построением оптимальных решений для математических моделей. Вид математической модели определяет метод или методы, которые используются для построения оптимального решения. В большинстве случаев математическая модель может быть представлена в виде целевой функции f(x) или критерия оптимальности (в некоторых случаях без ограничений, которая минимизируется или максимизируется. То есть необходимо найти минимум или максимум поставленной задачи, при этом xD является областями значений $x = (х_1, х_2, х_3, …, x_n)$. В большинстве случаев область возможных значений D задается. В этом случае задача формулируется следующим образом:

$f(x) = max(min)$

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

1. Методы нулевого порядка. В данном случае используются только данных о самих функциях для поиска экстремума.
2. Методы первого порядка. В данном случае используются функции и производные первого порядка.
3. Методы второго порядка. В данном случае используются функции и производные первого и второго порядка.