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

Градиент: Матрица Гессе:

Оптимальная точка Необходимое условие максимума: - оптимальная точка Достаточное условие максимума: - отрицательно определена

Пример. Квадратичная функция

Аналитическое решение

Пример. Квадратичная функция

Траектория поиска решения - длина шага - вектор направления

Выбор длины шага Постоянный шаг: Алгоритм регулировки длины шага Использование методов одномерного поиска Оптимизация длины шага:

Правила остановки

Метод релаксации (покоординатного спуска/подъема) Метод Ньютона Метод наискорейшего спуска/подъема (градиентный) Метод сопряженных градиентов (Флетчера-Ривса) Методы переменной метрики (квазиньютоновские): Бройдена, ДФП (Дэвидона-Флетчера-Пауэла) Выбор направления

Метод релаксации

Шаг 1

Метод релаксации Шаг 2

Метод релаксации Шаг 3

Метод релаксации Шаг 4 Шаг 5

Метод релаксации Шаг 6 Шаг 7

Метод релаксации Оптимальная точка:

Метод релаксации

Метод Ньютона

Шаг 1

Метод Ньютона Для квадратичных функций метод Ньютона сходится за 1 шаг

Метод Ньютона

Метод наискорейшего подъема

Шаг 1

Метод наискорейшего подъема Шаг 2 Шаг 3

Метод наискорейшего подъема Шаг 4 Оптимальная точка:

Метод наискорейшего подъема

Метод сопряженных градиентов

Шаг 1

Метод сопряженных градиентов Шаг 2 Для квадратичных функций число шагов равно числу переменных

Метод сопряженных градиентов

Метод Бройдена

Шаг 1

Метод Бройдена Шаг 2

Метод Бройдена

Метод ДФП

Шаг 1

Метод ДФП Шаг 2

Метод ДФП