Лабораторная работа: Методы оптимизации функций многих переменных
Пусть функция f ( x) дифференцируема в точке х* 
Rn . Тогда если х* - локальное решение задачи (1), то
gradf ( x* ) = 0. (2)
Пусть функция f (x ) дважды дифференцируема в точке х* Rn . Тогда
а) если х* - точка локального минимума в задаче (1), то матрица Гессе Н (х* ) неотрицательно определена, т.е. 
р Rn выполняется неравенство (Н (х* ) р,р ) ≥0;
б) если х* - точка локального минимума в задаче (1), то матрица Н (х*) неположительно определена, т.е. р Rn выполняется неравенство (Н (х* ) р,р) ≤0.
Пусть функция f ( x) дважды дифференцируема в точке х* Rn и
gradf ( x* ) = 0. Тогда
а) если матрица Н (х* ) положительно определена, т.е. р Rn , р ≠0, (Н (х* ) р,р) >0, то х* - точка строгого локального минимума функции f ( x) на Rn ;
б) если матрица Н (х* ) отрицательно определена, т.е. р R , р ≠0, (Н (х* ) р,р) <0, то х* - точка строгого локального максимума функции f ( x) на Rn .
Если gradf ( x* ) = 0, то х* называется стационарной точкой. Для выпуклой (вогнутой) на Rn функции стационарные точки являются точками ее глобального минимума (максимума). Строго выпуклые (вогнутые) функции имеют единственный глобальный минимум (максимум).
Критерий выпуклости функции. Дважды непрерывно дифференцируемая на выпуклом множестве Х с непустой внутренностью функция является выпуклой (вогнутой) на этом множестве в том и только том случае, когда матрица Гессе Н (х* ) неотрицательно (не положительно) определена для всех х Х .
При исследовании на знакоопределенность матрицы вторых производных функции рекомендуется применять критерий Сильвестра или анализ собственных значений матрицы.
Схема поиска безусловных экстремумов функции:
Составить и решить систему алгебраических уравнений (2).
В стационарных точках (точках, являющихся решением системы (2)) исследовать на знакоопределенность матрицу вторых производных; точки, в которых Н (х) > 0, являются точками глобального минимума; стационарные точки, в которых Н (х) < 0, являются точками глобального максимума.
Исходя из вида исследуемой функции, проанализировать стационарные точки, в которых матрица вторых производных не является строго знакоопределенной.
Найденные точки локального экстремума исследуются на глобальный экстремум (если это возможно). В частности, если матрица Гессе неотрицательно (не положительно) определена на всем пространстве Е n , то все стационарные точки функции являются точками глобального минимума (максимума).
1.2 Численные методы минимизации функции
Численное решение задачи минимизации (1), как правило, связано с построением минимизирующей последовательности точек x0 , x1 , x2 ,…, xn ,…, обладающих свойством
f ( xk ) < f ( xk -1 ), k =0,1,… (3)
Общее правило построения минимизирующей последовательности имеет вид
x k+1 = x k + t k d k , k =0,1,…,
где х0 - начальная точка поиска; dk - приемлемое направление перехода из точки xk в точку xk +1 , которое обеспечивает выполнение условий (3) и называется направлением спуска; tk - величина шага. Начальная точка поиска задается исходя из физического содержания решаемой задачи и априорных данных о существовании и положении точек экстремума.
При решении вопроса о выборе численного метода рекомендуется оценить поведение линий уровня целевой функции в окрестностях предполагаемой точки экстремума. Число m = L/l , где L и l - максимальное и минимальное собственные значения гессиана функции f в предполагаемой точке экстремума x0 ( характеризующее разброс собственных значений оператора f (x)) , называется числом обусловленности гессиана функции f в точке x0 . Если m >> 1, то функция f называется плохо обусловленн ой или овражн ой . Овражность , то есть вытянутость линий уровня вдоль одного направления, приводит к тому, что градиентные методы поиска экстремума функции сходятся медленно.
В зависимости от наивысшего порядка частных производных функции f ( x), используемых для формирования dk и tk , численные методы принято делить на три группы:
Методы нулевого порядка, использующие информацию только о значениях функции f ( x) ( методы деформируемого многогранника, конфигураций). Эти методы могут применяться в тех случаях, когда функция задана неявно или не задана аналитически, но известен ряд значений функции или эти значения вычисляются непосредственно в ходе реализации алгоритма. Они также могут быть полезны в случаях, когда производные функции могут быть заданы аналитически, но их выражения очень громоздки.
Методы первого порядка, использующие информацию о значениях самой функции f ( x) и ее первых производных (методы наискорейшего градиентного спуска, дробления шага, Гаусса-Зейделя, Флетчера-Ривса).
Методы второго порядка, использующие, кроме того, и информацию о вторых производных функции f (x) ( метод Ньютона и его модификации).
Метод конфигураций (Хука - Дживса)
Следует выделить два этапа метода конфигураций: