Алгоритм и программа решения задачи поиска экстремума функции градиентным методом

 

 

 

 

 

 

 

ОТЧЕТ

по дисциплине

Исследование операций

Курсовая работа по теме

«Алгоритм и программа решения задачи поиска экстремума функции градиентным методом»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Санкт-Петербург, 2012г.

Содержание

 

 

1. Описание метода...……...…………...………………………………3

     1.1. Алгоритм………….……………………..................……...…..3

     1.2.Формализация………………….................................…..…….4

2. Общая идея градиентного метода  ……..…….…………………...5

3. Методы поиска экстремума функции……………………………...7

    3.1. Метод координатного спуска……………...…………….……8

    3.2. Метод градиента.........................................…................….....9

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                               1. Описание метода

 

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

           Наиболее простой в реализации из всех методов локальной оптимизации. Имеет довольно слабые условия сходимости, но при этом скорость сходимости достаточно мала (линейна). Шаг градиентного метода часто используется как часть других методов оптимизации, например, метод Флетчера - Ривса.

 

                                   1.1 Алгоритм

 

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

Иллюстрация выбора промежуточных точек метода золотого сечения.

, где   — пропорция золотого сечения.

Таким образом:

То есть точка   делит отрезок   в отношении золотого сечения. Аналогично   делит отрезок   в той же пропорции. Это свойство и используется для построения итеративного процесса.

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

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

3) На следующей итерации  в силу показанного выше свойства  золотого сечения уже надо  искать всего одну новую точку.

4) Процедура продолжается  до тех пор, пока не будет  достигнута заданная точность.

 

 

               1.2 Формализация

 

1. Шаг 1. Задаются начальные границы отрезка   и точность  .
2. Шаг 2. Рассчитывают начальные точки деления:   и значения в них целевой функции:  .

Если   (для поиска max изменить неравенство на  ), то 

Иначе  .

3. Шаг 3.

Если  , то   и останов.

Иначе возврат к шагу 2.

 

       2. Общая идея градиентного метода

 

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

 

  Градиент всегда  перпендикулярен линии уровня, проходящей через ту точку, в которой вычислен градиент.

 

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

 

Показано, что значение a можно определять по некоторым характеристикам функции f(x). Например, если существует такая константа R, что для любых точек

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

Однако, значения R и M обычно заранее неизвестны.

Разработаны различные  методы, относящиеся к группе градиентного спуска. Среди них: с постоянным шагом, с дробным шагом и наискорейшего спуска.

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

 

 

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

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

Все градиентные методы плохо работают в овражных функциях.

Условия окончания итерационного  поиска в градиентных методах  связывают обычно с величиной градиента (критерий с номером 3).

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

 

Метод сопряженных градиентов является попыткой объединить достоинства методов первого и второго порядков с исключением их недостатков.

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

 

                                 3. Методы поиска экстремума функции

 

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

 

 

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

программирование

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

min f (х1, х2,..., хn) методом координатного спуска:

1) выбор начального  приближения ;

2) выбор направления  поиска, т.е. номера i?(1,2,...,n) компоненты  вектора

(x1,x2...,xn), которая подлежит  изменению;

3) вычисление значения  частной производной целевой  функции по выбран-ному аргументу , если f ?i ? 0 , то с ростом xi значение функции f (х1, х2,..., хn) увеличивается, а если f ?i ? 0, то уменьшается;

4) изменение значений  х1, х2,..., хn в соответствии с  выражением :

(2.3)

до тех пор, пока f (х1(k+1), х2(k+1),..., хn(k+1)) < f (х1(k), х2(k),..., хn(k)); в  противном случае производится возврат  на п. 2) и выбор следующего направления  поиска, при этом x i (0) = x i(k), i = 1,2,...n (h - шаг поиска, sign(z) - знак выражения z);

5) если движение с  шагом h в любом из n возможных  направлений приво-

дит к ситуации f (х1(k+1), х2(k+1),..., хn(k+1)) ? f (х1(k), х2(k),..., хn(k)) , то осуществляется дробление шага: h = h/p (p > 1) и вновь выполняется п. 4);

6) поиск считается  законченным, когда значение h становится  меньше за-данной точности

 

3.2 Метод градиента

 

Определение: градиент функции f (x1,x2,...,xn) в точке (x1(0),x2(0),...,xn(0)) ? это  вектор, длина которого (2.4)

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

Идея методов: каждая следующая точка поиска min f (x1,x2,...,xn) (каждый новый член минимизирующей последовательности) получается в результате пере-мещения из предыдущей точки по направлению антиградиента целевой функции. Если в результате этого перемещения наблюдается увеличение значения целевой функции, то значение рабочего шага поиска h уменьшается. Поиск прекращается, когда выполняется необходимое условие ext f (x1,x2,...,xn), например длина гради-ента становится меньше требуемой точности: , (2.5)

либо меньше требуемой  точности становится величина шага поиска: h ? ? . (2.6)

Различают методы градиента  с переменным шагом и с постоянным шагом. При использовании метода градиента с переменным шагом  изменение значений x1,x2,...,xn производится согласно выражению:

, i=1,2,...,n , k=0,1,2…, (2.7)

а останов поиска - при  выполнении неравенства (2.5). При возникновении  ситуа-ции f (х1(k+1), х2(k+1),..., хn(k+1)) ? f (х1(k), х2(k),..., хn(k)) значение h уменьшается, напри-мер  делится на число р > 1. Характер изменения значений x1,x2,...,xn согласно (2.7) зависит от величины и знака соответствующих частных производных целевой функции. По мере приближения к точке min f (x1,x2,...,xn) абсолютные величины частных производных уменьшаются, следовательно и шаг поиска является пере-менным - уменьшается по мере приближения к искомой точке.

Такой характер поиска требует  иногда значительных за-трат времени. Применение метода градиента с постоянным шагом позволяет со-кратить затраты  времени, но требует несколько большего объема вычислений при изменении  значений аргументов целевой функции. Его основное соотношение:

, i=1,2,...,n; k=0,1,2,... , (2.8)

т.е. расстояние между  точками (x1(k),x2(k),...,xn(k)) и (x1(k+1),x2(k+1),...,xn(k+1)) равно

,

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

ному значению h. Если изменение аргументов целевой функции  в соответствии с (2.8) приводит к увеличению ее значения, шаг поиска уменьшается. Останов по-иска min f (x1,x2,...,xn) по методу градиента с постоянным шагом  осуществляется при выполнении неравенства (2.6).

 

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

Это модификация метода градиента с постоянным шагом, позволяющая  со-кратить общий объем вычислений при некотором увеличении числа  членов минимизирующей последовательности за счет меньшего количества вычислений частных производных целевой функции. При использовании этого метода аргументы целевой функции изменяются в соответствии с выражением (2.8), но значения ее частных производных и длины градиента не пересчитываются до тех пор, пока не сложится ситуация f (х1(k+1), х2(k+1),..., хn(k+1)) ? f (х1(k), х2(k),..., хn(k)). Дробление шага поиска производится, когда во вновь выбранном направлении (после пересчета значений частных производных) не удается сделать ни одного результативного шага, останов поиска - при выполнении неравенства (2.6).

Основные этапы поиска min f (x1,x2,...,xn) методом наискорейшего  спуска:

1) выбор начального  приближения (x1(0), x2 (0), ... , xn (0));

2) определение значений  частных производных f (x1,x2,...,xn) в  этой точке;

3) изменение значений xi, i=1,2,...,n в соответствии с выражением (2.8) без пересчета частных производных до начала возрастания целевой функции;

4) если ситуация f (х1(k+1), х2(k+1),..., хn(k+1)) ? f (х1(k), х2(k),..., хn(k)) возникает  при

k ? 0, то начальным приближением становится предыдущая точка: xi (0) = xi (k),

i=1,2,...,n и вновь выполняются  п.п. 2), 3);

5) если f (х1(k+1), х2(k+1),..., хn(k+1)) ? f (х1(k), х2(k),..., хn(k)) уже при k=0, то  осуще-ствляется дробление шага h=h?p ( p > 1); при h ? ? (заданная точность) выполня-ется п. 3), иначе поиск заканчивается: xi ?? xi (k ), i=1,2,...,n .

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

1) Нахождение локального

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

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