· медленная сходимость к точке минимума ввиду малости f(x^k ) в окрестности этой точки.

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

Свободен от первого недостатка простейшего градиентного метода, т.к. a^k вычисляется путем решения задачи минимизации Ñf(x^k ) вдоль направления Ñf(x^k ) с помощью одного из методов одномерной оптимизации x^k+1 = x^k - a^k Ñf(x^k ).

Данный метод иногда называют методом Коши.

Алгоритм характеризуется низкой скоростью сходимости при решении практических задач. Это объясняется тем, что изменения переменных непосредственно зависит от величины градиента, которая стремится к нулю в окрестности точки минимума и отсутствует механизм ускорения на последних итерациях. Поэтому, учитывая устойчивость алгоритма, метод наискорейшего спуска часто используется как начальная процедура поиска решения (из точек, расположенных на значительных расстояниях от точки минимума).

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

Общая задача нелинейного программирования без ограничений сводится к следующему: минимизировать f(x), xÎEⁿ , где f(x) является целевой функцией. При решении этой задачи мы используем методы минимизации, которые приводят к стационарной точке f(x), определяемой уравнением Ñf(x^* )=0. Метод сопряженных направлений относится к методам минимизации без ограничений, использующим производные. Задача: минимизировать f(x), xÎEⁿ , где f(x) является целевой функцией nнезависимых переменных. Важной особенностью является быстрая сходимость за счет того, что при выборе направления используется матрица Гессе, которая описывает область топологии поверхности отклика. В частности, если целевая функция квадратичная, то можно получить точку минимума не более чем за количество шагов, равное размерности задачи.

Для применения метода на практике его необходимо дополнить процедурами проверки сходимости и линейной независимости системы направлений. Методы второго порядка

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

Последовательное применение схемы квадратичной аппроксимации приводит к реализации оптимизационного метода Ньютона по формуле

x^{k +1} = x^k - Ѳ f(x^{k -1} ) Ñf(x^k ).

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

x^{k +1} = x^k - a^k Ѳ f(x^{k -1} ) Ñf(x^k ), где

a^k - параметр, выбираемый таким образом, чтобы f(x^k+1 ) ® min.

2. Нахождение экстремума функции без ограничения

Дана некоторая функция f(х) на открытом интервале (а, в) изменения аргумента х. Предполагаем, что exst внутри этого интервала существует (нужно сказать, что в общем случае математически заранее это утверждать не могут; однако в технических приложениях очень часто наличие exst внутри некоторого интервала изменения интервала изменения аргумента может быть предсказано из физических соображений).

Определение exst. Функция f(x) заданная на интервале (а, в) имеет в точке x^* max(min), если эту точку можно окружить таким интервалом (x^* -ε, x^* +ε), содержащимся в интервале (а, в), что для всех ее точек х, принадлежащих интервалу (x^* -ε, x^* +ε), выполняется неравенство:

f(x) ≤ f(x^* ) → для max

f(x) ≥ f(x^* ) → для min

Это определение не накладывает никаких ограничений на класс функций f(x), что, конечно, очень ценно.

Если ограничится для функций f(x), достаточно распространенным, но все же более узким классом гладких функций (под гладкими функциями мы будем понимать такие функции, которые непрерывны вместе со своими производными на интервале изменения аргумента), то можно воспользоваться теоремой Ферма, которая дает необходимые условия существования exst.

Теорема Ферма. Пусть функция f(x) определена в некотором интервале (а, в) и в точке "с" этого интервала принимает наибольшее (наименьшее) значение. Если существует в этой точке двухсторонняя конечная производная , то существования необходимо exst.

Примечание. Двухсторонняя производная характеризуется свойством иными словами, речь идет о том, что в точке "с" производная в пределе одна и та же при подходе к точке "с" слева и справа, т.е. f(x) – гладкая функция.

^* В случае имеет место min, а при → max. Наконец, если при х=х₀ , то использование 2-ой производной не помогает и нужно воспользоваться, например, определением exst.

При решении задачи Iнеобходимые условия exst(т.е. теорема Ферма) используется очень часто.

Если уравнение exst имеет вещественные корни, то точки, соответствующие этим корням, являются подозрительными на exst(но не обязательно самыми экстремумами, ибо имеем дело с необходимыми, а не с необходимыми и достаточными условиями). Так, например, в точке перегиба Х_п имеет место , однако, как известно, это не экстремум.

Заметим ещё, что:

· из необходимых условий нельзя сказать, какой вид экстремума найден maxили min: для определения этого нужны дополнительные исследования;

· из необходимых условий нельзя определить, глобальный это экстремум или локальный.

Поэтому, когда находят точки подозрительные на exst, их дополнительно исследуют, например, на основе определения exstили 2-ой производной.

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

Метод наискорейшего спуска является градиентным методом с переменным шагом. На каждой итерации величина шага a_k выбирается из условия минимума функции f(x) в направлении спуска, т.е.

.