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

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

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

необходимо выбирать h не очень малым, однако в этом случае есть

опасность «проскочить» точку экстремума. Поэтому значительно  более

эффективно применение градиентных методов с переменным шагом.

Рассмотрим случай нахождения min функций z =f(x ,x ,…,x ).

    Пусть  x уже вычислено, тогда координаты следующей точки M

можно рассматривать  как функцию шага h , т.е. 

                                   x = x - h f (x ).                           (2.1) 

Для нахождения max формула будет иметь вид 

                                  x = x + h f (x ).                         (2.2) 

Подставив эти  координаты в исходную функцию, получим

f(x ,x ,…,x )=f(x - h f(x ),x - h f(x ),…,x - h f(x )=Ф (h),

т.е. мы получили функцию одного переменного  h .

Для нахождения min этой функций воспользуемся необходимым условием

экстремума функций  одной переменной, а именно 

                                        

Найденное значение h из этого уравнения (в сложном случае приближенно,

например методом  Ньютона, причем, здесь большой точности не требуется)

подставим в (2.1).

Таким образом, мы получили координаты новой точки  и т.п.

Метод нахождения локального экстремума с нахождением  шага h из

уравнения 

                                         

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

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

1. Находим градиент заданной функций .
2. Задаем точку M (x ) .
3. Вычисляем  f (M ).
4. x =x -h f(x ).
5. Подставив координаты x в исходную функцию, получаем

    Ф (h)=f(x - h f(x )).

6. Решая   уравнение   , находим h, при котором функция Ф (h)

   имеет  min .

7.Найденное значение h подставим  в формулу п. 4.

8. Сравним  значение f (M ).и f(М ) – необходимо, чтобы f(М )< f (M ).

9. Составим  x = x -h f(x ) и повторяем п. 5-8. 

Задача1. Используя метод наискорейшего спуска, найти максимум

                 функций z = 6x +32 x - x -4 x . 

Решение:  1. Составим градиент заданной функций  z(M)= .

2. Выберем  начальную точку M (0;0), в этой точке функция имеет

    значения  z(M ) = 0.

3. Вычислим  градиент в выбранной точке  M  

                         z(M ) =  

4. Используя  формулу (2.2), запишем :   x = x +h =6h; 

                                                                         x =x +h =32h. 
 

5.Полученные  в зависимости от шага h координаты точка М подставим

   в заданную  функцию, тогда

                   z(h) = 1060h – 4132h .  

6. Из уравнения x (h) – 1060 – 8264h =0 найдем h .
7. С учетом найденного значения h координаты точки: x =6 = ;

 
 

              x = 32 =4,    т.е. М (0,75;4) и z(М ) = 68. 

8. Мы видим, что z(М ) = 68 > z(M )=0.   Далее весь этот цикл с п. 3

повторяем для  точки  М (0,75; 4).

Вычисляем   x(М ) = и запишем          x = 0,75+4,5h; 

    x = 4,  тогда z(h) = + h - h . 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение 
 

Математическое  программирование принадлежит к  числу наиболее

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

в последнее  время все чаще возникают задачи, сводящиеся к схеме

нелинейного программирования.

Нелинейное программирование, охватывая весьма широкий круг

задач, является одним из основных разделов в теорий оптимальных решений.

Задачи нелинейного  программирования возникают в естественных

и физических науках, технике, экономике, в сфере деловых отношений

и в науке  управления государством. В экономике  рассматриваются задачи

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

зировать эффективность. Целевая функция здесь может  отражать эффек –

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

В физике целевой  функцией может быть потенциальная  энергия , а

ограничениями – различные уравнения движения. При этом минимизация

целевой функций  определит устойчивое состояние системы. Изменяя

целевую функцию, можно определить состояние с  наибольшей тепловой

энергией, кинетической энергией и т.д.

Преобразование  реальной задачи в задачу нелинейного  программирования

в значительной мере является искусством, направляемым теорией.

Теория точно  указывает, какая из многих возможных  формулировок задачи

решается наиболее эффективно, а какая не может быть решена вовсе.

Чтобы задачу можно  было решить, следует опознать (найти) оптимальную

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

максимизирует целевую заданную функцию и удовлетворяет  требованиям

ограничений.

Для этой цели разработан ряд специальных методов, позволяющих 

отправляться  от некоторого начального решения и получать последовательно значения, которые все более и более приближают

к искомой экстремальной  точке.

Методы, основанные на вычислений и сравнений значений функций в ряде точек перед  следующим шагом, называются – поисковыми методами

оптимизации.

Среди них особо важное значение имеют так называемые –  градиентные

методы, использующие градиент и его свойства.

Значительность  роли вектора – градиента для  нелинейного программиро –

вания не вызывает сомнения, поскольку, если дана некоторая неоптимальная

точка, то с помощью градиента можно найти «лучшую» точку.

Пусть мы имеем  функцию z = f(x ,x ,…,x ) или z = f(M), непрерывно

дифференцируемую  по своим переменным  x ,x ,…,x .

Градиентом  f(M) в точке M(x) называется вектор, направленный по

нормали к поверхности  уровня функций z = f(M) в сторону ее экстре –

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

      z(M)= f(M)= . 

Антиградиентом  называется вектор -  - f(M).

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

функций, а антиградиент – наискорейшего убывания функций. Мы будем

рассматривать только функций с непрерывным  градиентом.

В данном пособии  рассматриваются численные методы решения задач безусловной минимизаций (максимизации) функций. Эти типы задач

являются простейшими  в нелинейном программирования. В  ряде случаев

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

к рассматриваемому типу задач.