Классификация методов безусловной оптимизации. Методы нулевого порядка

Методы оптимизации можно разделить на:

- методы нулевого порядка (анализ значения целевой ф-ции)

-методы первого порядка (анализ значения 1-ой производной)

-методы второго порядка (анализ значения 2-ой производной)

Методы нулевого порядка однопараметрическая функция

- равномерный поиск

-метод деления пополам

-метод дихатомии

-метод Фибоначи

-метод золотого сечения

-метод случайного поиска

-направление случайного поиска

-метод Гаусса (метод покардинатоного поиска)

Все это методы можно использовать и для нескольких стартовых точек (т е из нескольких локальных оптимумов выбирается один)

- симплекс метод

Метод безусловной оптимизации первого порядка.

Методы первого порядка. Градиентные методы

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

Простейший градиентный метод - градиентный метод с постоянным шагом

Понятие условной оптимизации. Пример методов решения задач условной оптимизации.

 

Существуют следующие методы решения задач условной оптимизации:

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

2. Методы в которых существует переход от одной допустимой точки где выполнены все ограничения к другой допустимой точке I – ой группы.

· Метод штрафов (к целевой функции добавляется функция которая представляет собой штраф за нарушение каждого ограничения.

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

· Метод множителей Лагранжа

 

,

Формируется новая функция:

Далее используется любой оптимизационный метод.

Метод случайного поиска

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

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

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

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

Направленный случайный поиск с самообучением заключается в добавлении алгоритмов самообучения, которые корректируют вектор предыстории (случайный вектор Е) преимущественно в направлении удачного предыдущего шага или в направлении, обратном предыдущему неудачному шагу, в случае нелинейной целевой функции, например путем перестройки вероятностей Р1,…….,Рi,Рn составляющих случайного вектора Е=(е1,…,еi,….,en).Так, при целевой функции, близкой линейной, вероятность шага в удачном направлении увеличивается, и наоборот.

Использование методов случайного поиска определяется в основном следующими ситуациями: 1) неприемлемостью или отсутствием соответствующих аналитических и численных методов исследования модели; 2) возможностью создания модели функционирования системы (процесса), получением необходимого количества информации о моделируемой системе (процессе); 3) наличием большого числа случайных факторов в исследуемой системе (процессе); 4) наличием современной вычислительной техники и соответствующего программного обеспечения.