1.4 Оптимизация в математике и ее методы

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

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

Постановка задачи оптимизации

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

Стандартная математическая задача оптимизации формулируется таким образом. Среди элементов χ, образующих множества Χ, найти такой элемент χ^*, который доставляет минимальное значение f(χ^*)заданной функции f(χ). Для того, чтобы корректно поставить задачу оптимизации необходимо задать:

Допустимое множество — множество

;

Целевую функцию — отображение ;

Критерий поиска (max или min).

Тогда решить задачу означает одно из:

Показать, что .

Показать, что целевая функция не ограничена снизу.

Найти .

Если , то найти .

Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек x₀ таких, что всюду в некоторой их окрестности для минимума и для максимума.

Если допустимое множество , то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.

Классификация методов оптимизации

Методы оптимизации классифицируют в соответствии с задачами оптимизации:

Локальные методы: сходятся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максимумом/минимумом.

Глобальные методы: имеют дело с многоэкстремальными целевыми функциями. При глобальном поиске основной задачей является выявление тенденций глобального поведения целевой функции.

Существующие в настоящее время методы поиска можно разбить на три большие группы:

• детерминированные;

• случайные (стохастические);

• комбинированные.

По критерию размерности допустимого множества, методы оптимизации делят на методы одномерной оптимизации и методы многомерной оптимизации.

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

• прямые методы, требующие только вычислений целевой функции в точках приближений;

• методы первого порядка: требуют вычисления первых частных производных функции;

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

Помимо того, оптимизационные методы делятся на следующие группы:

• аналитические методы (например, метод множителей Лагранжа и условия Каруша-Куна-Таккера);

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

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

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

1) Определение границ системы оптимизации

Отбрасываем те связи объекта оптимизации с внешним миром, которые не могут сильно повлиять на результат оптимизации, а, точнее, те, без которых решение упрощается

2) Выбор управляемых переменных

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

3) Определение ограничений на управляемые переменные

… (равенства и\или неравенства)

4) Выбор числового критерия оптимизации

Создаём целевую функцию