Градиентный метод

Пусть функция непрерывно дифференцируема на , а Î

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

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

Пусть выбрано. Тогда градиентный метод заключается в построении последовательности { } по правилу , , .

- длина шага или просто шаг градиентного метода.

Если , то шаг можно выбрать так, чтобы . Если , то - точка минимума функции . В этом случае итерационный процесс прекращается.

Существуют различные способы выбора величины в градиентном методе. В зависимости от способа выбора можно получить различные варианты градиентного метода.

На луче, направленном по антиградиенту, введем функцию одной переменной , и определим из условий .

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

, или , или , где - заданные числа.

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

Точка M (x, y) является точкой максимума (минимума) функ-

ции z = f (x, y), если найдется такая окрестность точки M, что для

всех точек M (x, y) из этой окрестности выполняется неравенство

f o (x, y) > f (x, y) (или fo (x, y) < f (x, y)).

Точки максимума и минимума называются точками экстремума

(рис. 6).

Рис. 6

Сформулируем необходимое условие экстремума: если в точке

экстремума существует первая частная производная (по какому-либо

аргументу), то она равна нулю.

Точки экстремума дифференцируемой функции (то есть функции,

имеющей непрерывные частные производные во всех точках некоторой

области) надо искать только среди тех точек, в которых все первые ча-

стные производные равны нулю.

Там, где выполняется необходимое условие, экстремума может и не

быть (здесь полная аналогия с функцией одной переменной).

Для ответа на вопрос, является ли точка области определения

функции точкой экстремума, нужно использовать достаточное условие

экстремума: Пусть (,) 0 x z   x y   и (,) 0 y z   x y  , а вторые частные произ-

водные функции z непрерывны в некоторой окрестности точки (x 0, y 0).

Введем обозначения:

0 0 (,) xx A   z    x y;

0 0 (,) xy B   z    x y;

0 0 (,) yy C   z    x y;

2 D   AC   B.

Тогда, если D   0, то в точке (x 0, y 0) экстремума нет; если D   0, то

в точке (x 0, y 0) экстремум функции z, причем если A   0, то минимум, а

если A   0, то максимум; если D   0, то экстремум может быть, а мо-

жет и не быть, в данном случае требуются дополнительные исследова-

ния.

Аналитическое исследование функции двух переменных на экс-

тремум сводится к следующему: сначала выписываются необходимые

условия экстремума

(,) 0 x z   x y  ;

(,) 0 y z   x y 

которые рассматриваются как система уравнений. Ее решением является

некоторое множество точек. В каждой из этих точек вычисляются значения

D и проверяется выполнение достаточных условий экстремума.

Метод градиента. Будем считать, что все функции непрерывно

дифференцируемы, и заданное уравнение задает гладкую кривую S на

плоскости (x, y). Тогда задача сводится к нахождению экстремума

функции f на кривой S. Будем также считать, что S не проходит через

точки, в которых градиент f обращается в 0.

Напомним, что градиентом функции f называется вектор

  f /  x,  f /  y , где значения частных производных берутся в рассмат-

риваемой точке.

2 2

  





  









   



 







  

y

f

x

f

f. (6.1)

Необходимым условием экстремума будет условие, которое выра-

жается в следующей форме:

(0, 0) (0, 0) | | x y x y  f      . (6.2)

где   – некоторое число, отличное от нуля, и являющееся множителем

Лагранжа.

Рассмотрим теперь функцию Лагранжа, зависящую от x, y и 

L (x, y, )   f (x, y)     (x, y).

Необходимым условием ее экстремума является равенство нулю

градиента 0 0 0  L (x, y,  )   0

. В соответствии с правилами дифференци-

рования, оно записывается в виде

0 0 0 0

0 0 0 0

0 0

(,) (,)

0,

(,) (,)

0,

(,) 0.

f x y f x y

x x

f x y f x y

y y

x y







   

        



   

    

    

   

 

Мы получили систему, первые два уравнения которой эквивалент-

ны необходимому условию локального экстремума (6.2), а третье –

уравнению   (x, y)   0. Из нее можно найти 0 0 0 (x, y,  ). При этом

0     0, поскольку в противном случае градиент функции f обращается в

нуль в точке 0 0 (x, y), что противоречит нашим предположениям. Сле-

дует заметить, что найденные таким образом точки 0 0 (x, y)могут и не

являться искомыми точками условного экстремума – рассмотренное

условие носит необходимый, но не достаточный характер.

На практике метод градиента реализуется следующим образом.

1. Выбираем некоторое начальное значение     (,) 0 0

0 x   x y.

2. Задаем шаг h и точность     0.

3. Вычисляем x h f x k        /  , y h f y k        /   в точке (,) k  1 k  1 x y.

4. k k k x   x    x  1, k k k y   y    y  1.

5. Вычисляем    () k  f x и () (k)  f x по формуле (6.1).

6. Если () (k)  f x меньше точности     0, то (,) ()

min k k

k x   x   x y.

7. Если () (k)  f x больше точности     0, то делим шаг пополам

h   h / 2 и идем к шагу 3.

Метод сопряженных градиентов это модификация метода гради-

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

ции, а второй и последующие – в направлении векторной суммы анти-

градиента в текущей точке и предыдущего направления. Для преодоле-

ния «застревания в овраге» через n шагов осуществляется обновление

направления: делается шаг в направлении антиградиента целевой функ-

ции. Основные соотношения метода:

(k 1) (k) (k) x x h p        , i  1, 2,..., n, (6.3)

где

2 2

(0) 0 0 0 0 0 0

f (x, y) f (x, y) f (x, y)

p

x x y

    

    

      

          

      

,

2 2

(0) 0 0 0 0 0 0

f (x, y) f (x, y) f (x, y)

p

y x y

    

    

      

          

      

,

2 2

() (1)

1 1 2 2 2 2

1 1 1 1

(,) (,) (,)

(,) (,) (,) (,)

k k k k

k k

k k

k k k k k k k k

f x y f x y f x y

x x y p p

f x y f x y f x y f x y

x y x y

    

    

      

      



      

      

        

      

    

              

                  

              

2 2

() (1)

2 1 2 2 2 2

1 1 1 1

(,) (,) (,)

(,) (,) (,) (,)

k k k k k k

k k

k k k k k k k k

f x y f x y f x y

y x y

p p

f x y f x y f x y f x y

x y x y

    

    

      

      



      

      

        

      

    

              

                  

              

k   0, 1, 2,....

При обновлении направления второе слагаемое в последней фор-

муле зануляется. Дробление шага и остановка осуществляется анало-

гично методу градиента с постоянным шагом.

I. Анализ методов определения минимального и максимального значения функции многих переменных без ограничений. 5
Методы прямого поиска 6
Метод поиска по симплексу 6
Градиентные методы 7
Простейший градиентный метод 8
Метод наискорейшего спуска 8
Метод сопряженных направлений 8
Методы второго порядка 9
Метод Ньютона 9
II. Нахождение экстремума функции без ограничения 9
Метод наискорейшего спуска 11
Реализация метода в программе: 14
Метод сопряженных направлений 15
Реализация метода в программе: 17
III. Анализ методов определения минимального, максимального значения функции при наличии ограничений. 19
Правило множителей Лагранжа 20
Методы решения задач с ограничениями типа равенств 21
Методы возможных направлений 24
Методы проекции градиента 24
Методы линеаризации 25
Методы штрафов 25
Симплекс - метод 26
IV. Нахождение экстремума функции при наличии ограничений. 28
Метод симплексных процедур