Итерационные процессы с учетом градиента

Ограничения и условия в задачах оптимизации встраивают тем или иным образом  в общий функционал, после чего решают задачу поиска экстремума. Наиболее популярной структурой функционала является взвешенная сумма квадратов невязок, полученных из условий и ограничений. Это обеспечивает всему функционалу квадратичную зависимость по каждому неизвестному параметру и, как следствие, локальный минимум всему функционалу.

Изменение искомых параметров можно подчинить какой-либо детерминированной динамической процедуре, обеспечивающей сходимость итерационного процесса движения к точке минимума. Наиболее распространенным, имеющем множество модификаций, процессом является метод градиента:  вектор скорости изменения неизвестных параметров пропорционален с обратным знаком вектору градиента функционала:

Это условие соответствует выбору наибольшей скорости убывания  функционала, что несложно увидеть, рассмотрев выражение для производной функционала по времени:

.

Правую часть можно рассматривать как скалярное произведение двух n-компонентных векторов:  вектора градиента

и вектора скорости изменения координат-параметров

.

Скалярное произведение максимально, когда векторы коллинеарные.

В результате система градиентных уравнений наискорейшего приближения к значениям оптимальных параметров приобретает вид:

 .

Вид функционала существенно влияет на достижение локального минимума в итерационном процессе решения полученного градиентного уравнения. Численная итерационная процедура для решения последнего легко записывается, если производные правых частей системы представить конечными разностями первого порядка и переписать уравнения, разрешенными относительно очередных приближений искомых решений:

Равенство нулю градиента функционала может означать остановку итерационного процесса на одной из седловых точек, когда производные первого порядка по всем переменным  равны нулю, а некоторые из производных второго порядка имеют разные знаки по обе стороны от точки остановки решения. Это возможно, когда функция  нелинейная. Чтобы сдвинуться с точки промежуточной остановки на пути к локальному минимуму, необходимо провести оценку знаков вторых смешанных производных по всем неизвестным. В общем виде, в случае многомерного нелинейного функционала, смешанные производные второго порядка могут быть представленными в векторной форме. Для этого в разложении Тейлора достаточно произвести перегруппировку частных производных так, чтобы группы слагаемых представляли скалярные произведения векторов и матриц из частных производных:

,

где          , – вектор-столбец и вектор-строка очередных приращений,

 – строчная форма  записи вектора градиента,

 – матрица вторых частных производных (гессиан),

 – квадратичная форма с матрицей Гессе,

.

Условием достижения локального минимума является положительная определенность квадратичной формы с матрицей Гессе  в точке остановки, в которой . Квадратичная форма положительна тогда и только тогда, когда все главные миноры ее квадратной матрицы, например, матрицы A, положительны:

 .

Из проведенных рассмотрений можно сделать заключение, что для линейных функционалов любая остановка итерационного процесса соответствует локальному экстремуму, так как производные выше второй равны нулю.