Оптимизация
Оптимизация – это задача определения экстремума целевой функции в некоторой точке конечномерного векторного пространства, которая ограничена набором линейных и/или нелинейных равенств и/или неравенств.
Общей задачей оптимизации задается большое разнообразие их классов. От класса задачи зависит эффективность ее решения. Классификация задач определяется целевой функцией и допустимой областью. В соответствии с задачами оптимизации методы оптимизации делятся на:
- Локальные методы, которые сводятся к какому-нибудь локальному экстремуму целевой функции.
- Глобальные методы, которые имеют дело с многоэкстремальными целевыми функциями.
Методы оптимизации, которые существуют в настоящее время, также можно разделить на три группы: детерминированные, стохастические и комбинированные. К другим критериям классификации методов оптимизации относятся:
- Размерность допустимого множества. Согласно данному признаку методы оптимизации делятся на методы одномерной и многомерной оптимизации.
- Требования к гладкости и наличие у целевой функции частных производных. Согласно данному признаку методы оптимизации делятся на прямые методы, которые требуют вычисление целевой функции только в точках приближений; методы первого порядка, которые требуют вычисления первых частных производных целевой функции; методы второго порядка, которые требуют вычисления вторых частных производных.
- Способ решения. Согласно данному признаку методы оптимизации делятся на аналитические (условия Каруша - Куна - Таккера и метод множителей Лагранжа), численные методы и графические методы.
Стохастическая оптимизация
Стохастическая оптимизация – это класс алгоритмов оптимизации, которая использует случайность в процессе поиска оптимума.
Алгоритмы стохастической оптимизации, кроме градиентных, относятся к поисковым методам детерминированной оптимизации. Алгоритмы однопараметрической стохастической оптимизации используются в непрямых алгоритмах оптимизации. Алгоритмы стохастической оптимизации используются при решении задач оптимизации, которые возникают при физическом моделировании, то есть когда экспериментальные данные подвергаются различным искажениям. В данном случае ставится задача оптимизации некоторого выбранного критерия качества (у которого нет математического описания, но имеется возможность получить значения функции в результате натурных экспериментов), а алгоритмы стохастической оптимизации используются поитерационно. Алгоритмы однопараметрической многоэкстремальной стохастической оптимизации не требуют непрерывности функции (они могут использоваться в решении задач оптимизации гладких функций), что существенно для практических задач, потому что, как правило, исследователь не знает свойств целевой функции, которая построена математической моделью. Помимо этого отсутствует необходимость в получении точки экстремума с высокой степень точности, так как используемая математическая модель не абсолютно адекватная реальная конструкция.
Во всех известных алгоритмах стохастической оптимизации векторы х, которые определяются из рекуррентного соотношения, являются случайными, поэтому необходимо рассматривать сходимость в вероятностном смысле. В большинстве случаев при стохастической оптимизации используются три вида сходимости:
- Сходимость по вероятности.
- Сходимость в среднеквадратичном.
- Сходимость почти наверное, или с вероятностью один.
К главным требованиям сходимости алгоритмов стохастической оптимизации относятся ограниченность и замкнутость решения целевой функции, требования, которые накладываются асимптотическую скорость изменения шаговых множителей и ряд естественных предположений, касающихся ограниченности воздействия случайных помех. В некоторых случаях, когда не требуется определить экстремум с высокой степенью точности, алгоритмы стохастической оптимизации конкурируют с алгоритмами нелинейного программирования. Большинство алгоритмов детерминированной оптимизации обладают малой эффективностью в условиях помех. Подавляющее большинство алгоритмов стохастической оптимизации обладают свойством сглаживания, поэтому могут применяться в решении задач недифференцируемой детерминированной оптимизации.