Анализ методов определения минимального, максимального значения функции при наличии ограничений (стр. 2 из 7)

Способ определения a^k и s(x^k) на каждой итерации связан с особенностями применяемого метода. Обычно выбор a^k осуществляется путем решения задачи минимизации f(x) в направлении s(x^k). Поэтому при реализации градиентных методов необходимо использовать эффективные алгоритмы одномерной минимизации.

Простейший градиентный метод

В основе метода лежит следующая итерационная модификация формулы

x^k+1 = x^k + a^ks(x^k),

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

a - заданный положительный коэффициент;

Ñf(x^k) - градиент целевой функции первого порядка.

Недостатки:

· необходимость выбора подходящего значения ;

· медленная сходимость к точке минимума ввиду малости 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) в направлении спуска, т.е.

.

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

j (a)=f (x^(k)-aÑf (x^(k)))

Воспользуемся для этого методом золотого сечения.

Алгоритм метода наискорейшего спуска состоит в следующем.

1. Задаются координаты начальной точки x⁽⁰⁾.

2. В точке x^(k), k = 0, 1, 2, …, вычисляется значение градиентаÑf (x^(k)).

3. Определяется величина шага a_k путем одномерной минимизации по a функции

j (a)=f (x^(k)-aÑf (x^(k))).

4. Определяются координаты точки x^(k):

x_i^(k+1)= x_i^(k)-a_kÑf_i (x^(k)), i=1, …, n.

5. Проверяется условие останова итерационного процесса:

||Ñf (x^(k+1))||£e .

Если оно выполняется, то вычисления прекращаются. В противном случае осуществляется переход к п. 1. Геометрическая интерпретация метода наискорейшего спуска представлена на рис. 1.

Рис. 2.1. Блок схема метода наискорейшего спуска.

Реализация метода в программе:

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

Рис. 2.2. Реализация метода наискорейшего спуска.

Вывод: В нашем случае метод сошёлся за 7 итераций. Точка А7 (0,6641; -1,3313) является точкой экстремума.Метод сопряженных направлений. Для квадратичных функций можно создать градиентный метод, при котором время сходимости будет конечным и равно числу переменных n.

Назовем некоторое направление

и сопряженными по отношению к некоторой положительно определенной матрице Гесса H, если выполняется:

Если ,

Тогда

т.е. . Значит при единичной H, сопряженное направление означает их перпендикуляр. В общем же случае Hнеединичная. В общем случае сопряженность - это применение матрицы Гесса к вектору - означает поворот этого вектора на некоторый угол и его растяжение или сжатие.