Методы Оптимизации Систем Автоматизированного Проектирования

Построение последовательности заканчивается в точке, для которой
Если функция f(x) является квадратичной, то, независимо от начального приближения и степени овражности, с помощью метода Ньютона ее минимум находится за один шаг. Действительно, в этом случае аппроксимирующая функция совпадает с f(x) и метод Ньютона при положительной определенности матрицы Гессе отыщет минимум за один шаг.
Алгоритм метода.
Начальный этап
Задать ,.
Найти градиент функции в произвольной точке

и матрицу Гессе H(x)
Положить k=0.
Основной этап
Шаг 1. Вычислить
Шаг 2. Проверить выполнение критерия останова
а) если критерий выполнен, расчет окончен,
б) если критерий не выполнен, то перейти к шагу 3.
Шаг 3. Вычислить матрицу Гессе
Шаг 4. Найти обратную матрицу
Шаг 5. Проверить положительную определенность матрицы

Шаг 6. Найти
Шаг 7. Положить k= k +1 и перейти к шагу 1.

Сходимость метода.

Теорема 5. Пусть функция f(x) дважды непрерывно дифференцируемая сильно выпуклая функция с константой l > 0 на , и удовлетворяет условию

а начальная точка такова, что

Тогда последовательность сходится к точке минимума с квадратичной скоростью

Пример.

Стр.: 1, ..., 3