Статические задачи оптимизации

Статические задачи оптимизации называются также задачами математического программирования.

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

, (1.1)

который минимизирует (или максимизирует) целевую функцию

,

т.е.

или . (1.2)

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

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

Задачи линейного программирования характеризуются тем, что функции и являются линейными по .Требуется найти вектор с компонентами , обеспечивающий минимум (или максимум) функции

(1.3)

при условиях , .

В основе большинства методов решения задач линейного программирования лежит симплекс-метод [10,12].

К задачам нелинейного программирования относятся все задачи с нелинейной целевой функцией или нелинейными ограничениями. Частным случаем являются задачи квадратичного программирования, которые характеризуются квадратичной зависимостью целевой функции и линейной зависимостью функций . Методы решения задач этого типа в основном базируются на теореме Куна-Таккера [4].

В детерминированных задачах целевая функция является детерминированной (неслучайной) функцией параметров. В стохастических задачах параметры являются случайными величинами, а целевая функция представляет собой статистическую характеристику случайной функции параметров.

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

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

Методы случайного поиска характеризуются наличием элемента случайности в алгоритме поиска (например, случайными могут быть величины пробного шага, рабочего шага и другие). К этим методам относятся методы ненаправленного случайного поиска, комбинированные методы поиска, методы случайного поиска с самообучением.