П.1. Сведение системы линейных уравнений к задаче. нелинейной оптимизации (ЗНО) и наоборот

нелинейной оптимизации (ЗНО) и наоборот.

Постановка задачи ЗНО:

Найти (8.1) минимум или максимум в некоторой области D.

Как мы помним из мат. анализа, следует приравнять частные производные к нулю.

Таким образом, ЗНО (8.1) свели к СНУ (8.2)

(8.2) n нелинейных уравнений.

Обратное: пусть дана СНУ

(S достигает своего минимума в точке, где все i-ые зануляются)

П.2. Метод градиента.

Наша задача найти минимум функций n переменных без ограничений на X.

Общая идея метода:

Возьмём некоторую стартовую точку Х (желательно, чтобы она была достаточно близка к минимуму функции).

Пусть - гладкая функция, тогда вектор градиента f в точке :

показывает направление наискорейшего роста функции. Соответственно вектор -показывает направление наискорейшего спуска.

Пойдём вдоль этого вектора, рассмотрим функцию

уравнение луча, исходящего из в направлении –grad

Идём вдоль этого луча до тех пор, пока не начнёт возрастать, т.е. не достигнет своего минимума. В этот момент (в точке ) мы остановимся и повторим такую же процедуру (т.е. пойдём из точки в направлении –grad, т.е. рассмотрим и т.д.)

Данную процедуру повторяем до тех пор, пока не достигнем заданной точности (применяем универсальный критерий прерывания )

Иллюстрация:

Итак, с помощью метода градиента нам удаётся многомерную ЗНО свести к одномерной ЗНО, т.е. нам необходимо научиться находить минимум функций одной переменной (на первом шаге минимум , на втором шаге и т.д.)