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

       СОДЕРЖАНИЕ 
 

1. Понятие градиент – 2 стр.
2. Постановка задачи решения системы уравнения – 4 стр.
3. Градиентные методы – 4 стр.
4. Градиентный спуск – 4 стр.
5. Метод наискорейшего спуска (метод градиента) – 6 стр.
6. Метод сопряженных градиентов – 6 стр.
7. Пример градиентного метода (минимизировать функцию) – 9 стр.
8. Литература – 14 стр.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

       ПОНЯТИЕ   ГРАДИЕНТ 
 

       Градиент (от лат. gradiens, род. падеж gradientis — шагающий, растущий) — вектор, показывающий направление наискорейшего возрастания некоторой величины, значение которой меняется от одной точки пространства к другой (скалярного поля). Например, если взять в качестве  высоту поверхности Земли над уровнем моря, то её градиент в каждой точке поверхности будет показывать «направление самого крутого подъёма». Величина (модуль) вектора градиента равна скорости роста  в этом направлении. 

Термин  впервые появился в метеорологии, а в математику был введен Максвеллом в 1873 г. Обозначение grad тоже предложил  Максвелл. 

 

 
 
 

 

 

 
 

 

 
 
 
 
 

 
 
 

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Пример 1.  Минимизировать функцию

при ограничениях:

Решение. Возьмем в допустимой области  произвольную точку, например Она действительно принадлежит заданной области, так как и

 В этой точке

Вычислим  координаты антиградиента функции  в точке  

Поскольку не является точкой экстремума.

Переместимся  из вдоль антиградиента по прямой в новую точку Для определения координат точки нужно выбрать значение параметра . и Используем условие найдем:

откуда  Так как то при = 0,5 изменение значения функции достигает наибольшей величины. Получающаяся при этом точка принадлежит допустимой области

                   В точке антиградиент . Значит, никакими перемещениями из точки функцию уменьшить нельзя и — искомая точка минимума    Итак,

На рис. 3 приведена геометрическая иллюстрация решения задачи. На рис.3а дано наглядное изображение поверхности (параболоид вращения), на рис.3б поверхность изображена линиями уровня (концентрическими  окружностями). Для большей наглядности рисунка антиградиент построен при начале координат. Траектория наискорейшего спуска минимума в точку параллельна антиградиенту.                     

               Граничными линиями допустимой области являются оси координат, прямая  и дуга окружности Для построения этой дуги уравнение окружности преобразовано к виду   откуда следует, что центр окружности находится в точке (2,5; 0), а радиус равен 3,5.

                Для построения линий уровня поверхности ее уравнение приведено к виду  Очевидно, что линиями пересечения поверхности с плоскостями, параллельными плоскости т. е. при будут окружности. При их радиусы равны соответственно: 1; 1,41; 1,73; 2; 2,24. На плоскости они имеют общий центр (3; 2).

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

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

                   Начнем с геометрической интерпретации процесса решения (рис.4). Предположим, что начальная точка расположена внутри заданной области. Мы можем двигаться из точки в направлении градиента до тех пор, пока не достигнем границы области. Вообще говоря, двигаться до границы не обязательно, так как максимум может достигаться и до встречи с ней. В нашем случае все время возрастает, поэтому остановиться следует в точке на

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

когда перемещение  осуществляется вдоль градиента, либо аналогичное уравнение

когда движение происходит по направлению 

                  Если в направлении градиента функция возрастает до самой границы, то точка окажется на граничной прямой. В таком случае двигаться в направлении градиента и дальше нельзя, ибо сразу будут нарушены некоторые из ограничений (10), (11). Определением координат точки завершается первый этап решения задачи.

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

при ограничениях

 

для тех , при которых

Здесь  

                    В результате будет найден вектор , составляющий с градиентом наименьший угол граничной прямой. Как видно из рис.4, дальше двигаться в направлении градиента нельзя, ибо мы выйдем из допустимой области. Поэтому необходимо найти вектор составляющий с вектором наименьший острый угол по сравнению с любым вектором, выходящим из точки и лежащим в допустимой области. Аналитически такой вектор находят из условия максимизации скалярного произведения (точнее, косинуса угла между указанными векторами), что равносильно минимизации острого угла между векторами и ибо чем больше косинус острого угла, тем меньше сам угол. В данном случае вектор указывающий наивыгоднейшее направление, совпадает с граничной прямой. Таким образом, на следующем шаге мы двигаемся вдоль граничной прямой до тех пор, пока функция возрастает (в нашем случае — до точки ). Из рис.4 видно, что далее следует перемещаться в направлении вектора , т. е. вдоль следующей граничной прямой, до точки . Здесь процесс заканчивается, так как, судя по чертежу, в точке функция имеет локальный максимум. В этой точке достигает также глобального максимума в рассматриваемой области. Градиент в точке максимума составляет тупой угол с любым вектором из допустимой области, проходящим через точку , поэтому косинус его, а значит, и скалярное произведение будут отрицательными, за исключением одного случая. Для вектора , направленного по граничной прямой, скалярное произведение так как взаимно перпендикулярны. Это равенство и свидетельствует о том, что в точке функция достигла максимума.

                     Обратимся к аналитическому решению задачи (9) — (11). Предположим, что в допустимой области выбрана некоторая точка причем

                      Если она расположена внутри области, то все ограничения (10), (11) выполняются как строгие неравенства и перемещаться в следующую точку целесообразно в направлении градиента , т. е. по прямой (7). Чтобы найти координаты новой точки на этой прямой, следует так определить значение параметра чтобы координаты этой точки

удовлетворяли прежде всего ограничениям (10), (11) задачи. С этой целью решается система линейных неравенств

                       Условие (17) говорит о том, что точка принадлежит границе допустимой области, а условие (16) означает, что перемещение из направлено внутрь или по границе допустимой области. Условие нормализации (18) необходимо для ограничения величины так как иначе значение функции (15) можно сделать сколь угодно большим.                    

                      Рассматриваются различные формы условий нормализации. В зависимости от этого задача (15) — (18) может быть линейной или нелинейной.

                       После определения направления аналогично описанному выше отыскивается наилучшее значение и находится следующая точка и т.д. Процесс прекращается по достижении точки в которой max