Метод многомерного поиска первого порядка – наискорейшего спуска
На каждой итерации задача одномерной оптимизации решается точно.
При использовании метода наискорейшего спуска на каждой итерации величина шага λk выбирается из условия минимума функции f(x) в направлении спуска.
Прямой метод Хука-Дживса для решения задач многомерного поиска
Метод нелинейной оптимизации нулевого порядка – не использующий значения производных функций, применяется в том случае, если значения производных сложно получить в виде аналитических функций или процесс вычисления производных довольно трудоемкий.
Метод Хука-Дживса для поиска безусловного локального экстремума функции. Алгоритм делится на две фазы: исследующий поиск и поиск по направлению.
Прямой метод Гаусса для решения задач многомерного поиска
Одномерный поиск на унимодальных функциях: метод Фибоначчи
Одномерный поиск на унимодальных функциях: метод золотого сечения
Одномерный поиск на унимодальных функциях: метод дихотомии
Классификация численных методов решения задач нелинейного программирования
Численные методы – в которых решение задачи НП ищется эвристическим подбором значений неизвестных, доставляющих экстремум min или max целевой функции.
(набор расчетных точек фиксировано (значение очередной расчетной точки
и определено априорно) определяется по рез-ту предыд. итерации)
Пассивный (выбор стартовой точки) => переход к последовательному.
d 2 f / d x2 < 0 – первого порядка
d 2 f / d x2 > 0 – второго порядка
Численные методы многомерных задач сводится к комбинации одномерных.
Метод неопределенных множителей Лагранжа для решения задач нелинейного программирования
Определение и свойства унимодальных и многомодальных функций
Унимодальная функция – на интервале от а до b, если внутри этого интервала существует точка, слева от которой функция только возрастает, справа – убывает.
Основное свойство унимодальных функций, используемое при поиске точек минимума, состоит в том, что вычисление любых двух значений f(x1), f(x2), x1 ¹ x2, x1,x2 Î [a,b] позволяет уменьшить интервал поиска точки минимума. Для решения задачи одномерной оптимизации с унимодальной целевой функцией применяется метод золотого сечения и метод чисел Фибоначчи.
Многомодальная функция – содержит внутри интервала [a, b] несколько точек аналогичных свойству унимодальной.
Задачи нелинейного программирования решаются так: дифференциал означает, что функция определена в сколь угодно малой окрестности возле точки вычисления производно.
grad [f(x)] = 0 – вектор, указывающий направление возрастающей функции.
Правила НП:
1) На области допустимых значений находятся все точки (grad = 0 или производная = 0).
2) С помощью специальных методов находятся все значения целевой функции на границах допустимых значений.
3) Простым переборным сравнением среди стац. и граничных точек, выбирается точка, соотв. наибольшим или наименьшим значением целевой функции.