Методы оптимизации
1. Классические методы оптимизации
2. Численные методы оптимизации функции одной переменной
Классические методы оптимизации
Функция 
дважды дифференцируема в точке 
и в некоторой ее окрестности.
Если для всех точек х этой окрестности 
или 
, то функция 
имеет экстремум в точке 
. Точка , в которой все частные производные функции 
равны нулю, называется стационарной точкой.
Необходимые условия экстремума
Если в точке функция имеет экстремум, то частные производные функции в этой точке равны нулю:
, 
.
Для получения достаточных условий следует определить в стационарной точке знак дифференциала второго порядка. Обозначается 
и равен сумме произведений второго порядка на соответствующие приращения аргументов:
Достаточные условия экстремума
а) в стационарной точке 
функция имеет максимум, если 
, и минимум, если 
, при любых 
и
, не обращающихся в нуль одновременно;
б) если 
может принимать в зависимости от и и положительные и отрицательные значения, то в точке экстремума нет
в) если может обращаться в нуль не только при нулевых приращениях и , то вопрос об экстремуме остается открытым.
Для функции двух переменных 
достаточные условия еще не очень сложны. Существуют четыре частные производные второго порядка
,
, 
,
. Из них две смешанные производные, если непрерывны, то раны. Найдем значения частных производных второго порядка в стационарной точке 
:
, 
,
,
.
Обозначим через 
определитель, составленный из 
:
Тогда достаточные условия экстремума функции двух переменных имеют вид:
а) - если 
>0 и 
, то в точке функция имеет максимум,
- если >0 и 
, то в точке функция имеет минимум;
б) если <0, то экстремума нет;
в) если=0, то вопрос об экстремуме остается открытым.
Пример Исследовать на экстремум функцию 
.
1. Найдем частные производные
2. Приравняем их к нулю:
Решая полученную систему уравнений, получаем три стационарные точки:
,
, 
.
3. Найдем вторые частные производные:
4.вычисляем значения вторых частных производных в каждой стационарной точке, составляем определитель и применяем достаточные условия экстремума:
- в точке - 
, 
, 
.
. Следовательно, вопрос об экстремуме остается открытым.
- в точке 
- 
, , 
.
. Функция в точке имеет минимум.
- в точке 
- , , .
. Функция в точке имеет минимум.
В практических задачах часто возникает необходимость поиска экстремума функции в ограниченной области.
Функция 
имеет в точке
заданной области 
глобальный максимум или глобальный минимум, если неравенство
или 
выполняется для любой точки 
. Если область замкнута и ограничена, то дифференцируемая функция достигает в этой области своих наибольшего и наименьшего значений или в стационарной точке, или в граничной точке области (теорема Вейерштрасса).
Следовательно, чтобы найти наибольшее(наименьшее) значения функции в области , нужно
1) найти все стационарные точки внутри области и вычислить значения функции в них.
2) Исследовать функцию на экстремум на границе области
3) Сравнить значения функции, вычисленные в п.1 и п.2.
Численные методы оптимизации
Методы оптимизации –поиска экстремума функции (в практических задачах – критериев оптимальности) при наличии ограничений или без ограничений очень широко используются на практике.
Это задачи оптимального проектирования оптимального управления, построение нелинейных математических моделей объектов управления. Существует большое количество численных методов оптимизации.
Постановка задачи одномерной оптимизации
Решением задачи называется 
при котором 
для любого значения
. При практическом решении задач не различаются два значения 
и 
, если
, 
- задаваемая погрешность.
Основные методы
Метод сканирования
Метод заключается в последовательном переборе всех значений с шагом с вычислением критерия оптимальности в каждой точке. Путем выбора наибольшего(наименьшего) из всех вычисленных значений 
и находится решение задачи. Достоинство метода состоит в том, что можно найти глобальный максимум(минимум) критерия, если – многоэкстремальная функция и поиск не зависит от вида оптимизируемой функции. К недостаткам метода относится значительное число повторных вычислений критерия. Существуют различные модификации метода сканирования, применяемые для сокращения объема вычислений. Одна из модификаций – использование алгоритма с переменным шагом. Вначале величина шага выбирается достаточно большой и выполняется грубый поиск, который локализует область нахождения глобального оптимума. После того, как область определена, производится поиск с меньшим шагом только в пределах новой области. Объем вычислений критерия оптимальности при этом существенно сокращается.
Метод деления пополам.
Метод основан на делении текущего отрезка
содержащего экстремум, на две равные части с последующим выбором одной из половин, в которой локализуется максимум(минимум) в качестве следующего текущего отрезка. Экстремум локализуется путем сравнения двух значений критерия оптимальности в точках, отстоящих от середины отрезка на 
, где -погрешность. Если 
, то максимум располагается на правой половине отрезка, в противном случае – на левой. Процесс поиска завершается при достижении отрезком величины заданной погрешности . К недостаткам метода относится его работоспособность только для одноэкстремальных функций .
Метод золотого сечения
Метод основан на делении текущего отрезка , где содержится искомый экстремум
