27. Методы решения задач нелинейного программирования.
Методы решения задач выпуклого программирования без ограничений | ||
Методы, использующие первую производную | Методы, использующие первую и вторую производную | Методы прямого поиска |
Градиентные методы | Метод Ньютона | Метод Нелдера-Мида |
Направление поиска экстремума определяется градиентной целевой функцией | Направление поиска экстремума определяется первой и второй производной целевой функции | Поиск по деформируемому многограннику |
Методы прямого поиска.
Целевая функция вычисляется в некотором конечном числе дискретных точек пространства оптимизируемых переменных. Точки могут быть выбраны случайно или не случайно.
Сеточные методы | Строится начальная сетка точек, в которых вычисляются значения показателя эффективности. Относительно наилучшей точки строится новая более мелкая сетка и процесс повторяется |
ЛП-поиск | Основан на идее равномерного покрытия пространства оптимизируемых переменных неслучайной сеткой точек, которая строится с помощью ЛП-последовательности. |
Случайный поиск | Основан на идее случайного задания, как шага, так и направления поиска. В результате нескольких пробных шагов выбирают тот, который дает лучшее значение целевой функции. Затем процесс повторяется до выполнения условия останова. |
Генетические методы | Поиск производится из популяции решений, а не из одной точки. Каждая итерация метода производит “естественный отбор”, который отсеивает худшие решения. Лучшие решения “скрещиваются” между собой и “мутируют” путем небольших замен элементов решений. “Скрещивания” и “мутации” генерируют новые решения, и итерация повторяется. |
Метод мультистарта | Строится множество точек равномерно распределенных в пространстве оптимизируемых переменных. Из каждой точки запускается алгоритм локальной оптимизации. Лучшее локальное решение считается глобальным. |
Методы решения задач в системе “Математика”.
Nelder-Mead | Метод Нелдера-Мида Поиск по деформируемому многограннику |
Differential Evolution | Метод дифференциальной эволюции генетической точки |
Simulated Annealing | Метод моделирования обжига |
Random Search | Метод мультистарта |