Правила за въвеждане на функция
IN метод на най-стръмно спусканекато посока на търсене се избира вектор, чиято посока е противоположна на посоката на градиентния вектор на функцията ▽f(x). от математически анализизвестно е, че векторът grad f(x)=▽f(x) характеризира посоката на най-бързо нарастване на функцията (вижте градиента на функцията). Следователно векторът - grad f (X) = -▽f(X) се нарича анти-градиенти е посоката на най-бързото му намаляване. Рекурентната връзка, с която се прилага методът на най-стръмното спускане, има формата X k +1 =X k - λ k ▽f(x k), k = 0,1,...,
където λ k >0 е размерът на стъпката. В зависимост от избора на размер на стъпката, можете да получите различни опцииградиентен метод. Ако по време на процеса на оптимизация размерът на стъпката λ е фиксиран, тогава методът се нарича градиентен метод с дискретна стъпка. Процесът на оптимизация в първите итерации може да бъде значително ускорен, ако λ k се избере от условието λ k =min f(X k + λS k) .
За определяне на λ k се използва всеки едномерен метод за оптимизация. В този случай методът се нарича метод на най-стръмното спускане. Като правило, в общ случайЕдна стъпка не е достатъчна за постигане на минимума на функцията; процесът се повтаря, докато следващите изчисления позволят резултатът да бъде подобрен.
Ако пространството е много удължено в някои променливи, тогава се образува "дере". Търсенето може да се забави и да се движи на зигзаг по дъното на „дерето“. Понякога решение не може да бъде получено в приемлив срок.
Друг недостатък на метода може да бъде критерият за спиране ||▽f(X k)||<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.
Пример. Започвайки от точката x k =(-2, 3), определете точката x k +1, като използвате метода на най-стръмното спускане, за да минимизирате функцията.
Като посока на търсене изберете градиентния вектор в текущата точка 
Нека проверим критерия за спиране. Имаме 
Нека изчислим стойността на функцията в началната точка f(X 1) = 35. Нека направим
стъпка по антиградиентната посока
Нека изчислим стойността на функцията в нова точка
f(X 2) = 3(-2 + 19λ 1) 2 + (3-8λ 1) 2 - (-2 + 19λ 1)(3-8λ 1) - 4(-2 + 19λ 1)
Нека намерим такава стъпка, че целевата функция да достигне минимум по тази посока. От необходимото условие за съществуване на екстремум на функцията
f’(X 2) = 6(-2 + 19λ 1) 19 + 2(3-8λ 1)(-8) – (73 - 304 λ 1) – 4*19
или f’(X 2) = 2598 λ 1 – 425 = 0.
Получаваме стъпката λ 1 = 0,164
Завършването на тази стъпка ще доведе до точката 
в която стойността на градиента 
, стойност на функцията f(X 2) = 0,23. Не се постига точност, от точката правим крачка по посока на антиградиента.
f(X 2) = 3(1,116 – 1,008λ 1) 2 + (1,688-2,26λ 1) 2 - (1,116 – 1,008λ 1)(1,688-2,26λ 1) - 4(1,116 – 1,008λ 1)
f’(X 2) = 11,76 – 6,12λ 1 = 0
Получаваме λ 1 = 0,52 
Постановка на проблема
Нека функцията е дадена f(x) Rn
Задължително f(x) X = Rn
Стратегия за търсене
x k
} , k = 0,1,...,
такова, че 
, k = 0,1,...
. Точки на последователност ( x k
) се изчисляват по правилото
къде е смисълът х 0 дефиниран от потребителя; размер на стъпката т.к определени за всяка стойност к от условието
Проблем (3) може да бъде решен с помощта на необходимото минимално условие, последвано от проверка на достатъчното минимално условие. Този път може да се използва или с достатъчно проста функция, която да бъде минимизирана, или с достатъчно предварително приближение сложна функция 
полином P(t k)
(обикновено от втора или трета степен), след което условието се заменя с условието, а условието с условието 
Секвениране (xk)
завършва на точка x k
, за което , къде ε
- дадено малко положително число, или k ≥ M
, Къде М
- ограничаващия брой повторения или с две едновременно изпълнение на две неравенства 
, 
Къде ε 2
- малко положително число. Въпросът е може ли точка x k
се счита за намерено приближение на желаната локална минимална точка х*
, се разрешава чрез допълнителни изследвания.
Геометрична интерпретация на метода за n=2 на фиг. 4.
Метод на координатно спускане
Постановка на проблема
Нека функцията е дадена f(x) , ограничена отдолу на множеството Rn и има непрекъснати частни производни във всички свои точки.
f(x) върху множеството от възможни решения X = Rn , т.е. намерете такава точка, че
Стратегия за търсене
Стратегията за решаване на проблема е да се конструира последователност от точки ( x k
} , k = 0,1,...,
такова, че , k = 0,1,...
. Точки на последователност ( x k
) се изчисляват за цикли в съответствие с правилото
(4)
Къде й - номер на изчислителен цикъл; j = 0,1,2,...; к - номер на итерация вътре в цикъла, k = 0,1,...,n - 1; e k +1 , k = 0,l,...,n - 1 -единичен вектор, (k+1) -та проекция на което е равно на 1; точка х 00 дефиниран от потребителя, размер на стъпката т.к се избира от условието
или 
.
Ако избраното условие при ток т.к
не е изпълнена, стъпката се преполовява и точка 
се изчислява отново. Лесно е да се види, че за фиксирано j, в една итерация с число к
променя се само една проекция на точката x jk
, като има номер k+1
, и през целия цикъл с номер й
, т.е. започвайки от k = 0
и край k = n -1
, всички n проекции на точката се променят x j0
. След тази точка x j n
е присвоен номер x j + 1,0
, и се приема като отправна точка за изчисленията в j+1
цикъл. Изчислението приключва в точката x jk
когато е изпълнен поне един от трите критерия за край на преброяването: 
, или , или двойно изпълнение на неравенства.
Точките, получени в резултат на изчисленията, могат да бъдат записани като елементи на редица (xl), Къде l=n*j+k - пореден номер на точката,
Геометричната интерпретация на метода за n = 2 е показана на фиг. 5.
4. Метод на Франк-Улф .
Да предположим, че трябва да намерим максималната стойност на вдлъбната функция
При условия
Характерна особеност на тази задача е, че нейната система от ограничения съдържа само линейни неравенства. Тази характеристика е в основата на замяната на нелинейната в околностите на изследваната точка целева функциялинеен, поради което решението на първоначалната задача се свежда до последователно решаване на задачи за линейно програмиране.
Процесът на намиране на решение на проблема започва с идентифициране на точка, принадлежаща към областта на възможните решения на проблема.
270
дачи Нека това е смисълът X(k)
тогава в тази точка се изчислява градиентът на функция (57).
И конструиране на линейна функция
След това намерете максималната стойност на тази функция при ограничения (58) и (59). Нека решението на този проблем се определя от точката Z(k)
. След това координатите на точката се приемат като ново възможно решение на първоначалния проблем X(k+1)
:
Къде λ k - определено число, наречено стъпка на изчисление и оградено между нула и едно (0<λ k < 1). Это число λ k взети произволно или определени
така че стойността на функцията в точката X (k +1) f(X (k +1)) , в зависимост от λ k , беше максимумът. За да направите това, трябва да намерите решение на уравнението и да изберете най-малкия му корен. Ако стойността му е по-голяма от единица, тогава трябва да поставим λ k=1 . След определяне на броя λ k намерете координатите на точка X(k+1) изчислете стойността на целевата функция в него и определете необходимостта от преминаване към нова точка X(k+2) . Ако има такава необходимост, изчислете в точката X(k+1) градиент на целевата функция, отидете на съответната задача за линейно програмиране и намерете нейното решение. Определете координатите на точката и X(k+2) и проучете необходимостта от допълнителни изчисления. След краен брой стъпки се получава решение на първоначалната задача с необходимата точност.
И така, процесът на намиране на решение на задача (57) - (59) с помощта на метода на Франк-Волф включва следните етапи:
1. Определете първоначалното възможно решение на проблема.
2. Намерете градиента на функция (57) в точката на допустимо решение.
3. Построете функция (60) и намерете нейната максимална стойност при условия (58) и (59).
4. Определете стъпката на изчисление.
5. С помощта на формули (61) се намират компонентите на ново допустимо решение.
6. Проверете необходимостта от преминаване към следващото възможно решение. Ако е необходимо, преминете към етап 2, в противен случай се намира приемливо решение на първоначалния проблем.
Метод на наказателните функции.
Разгледайте проблема за определяне на максималната стойност на вдлъбнатата функция
f (x 1, x 2, .... x n)при условия g i (x 1, x 2, .... x n) ≤ b i (i=l, m) , x j ≥ 0 (j=1, n) , Къде g i (x 1, x 2, .... x n) - изпъкнали функции.
Вместо да решавате този проблем директно, намерете максималната стойност на функцията F(x 1, x 2, ...., x n)= f(x 1, x 2, ...., x n) +H(x 1, x 2, ...., x n) което е сумата от целевата функция на проблема и някаква функция
H(x 1, x 2, ...., x n), определени от система от ограничения и нар наказателна функция. Наказателната функция може да бъде конструирана по различни начини. Най-често обаче изглежда така
А a i > 0
- някои постоянни числа, представляващи тегловни коефициенти.
Използвайки наказателната функция, те последователно се придвижват от една точка към друга, докато получат приемливо решение. В този случай координатите на следващата точка се намират по формулата
От последното съотношение следва, че ако предишната точка е в областта на възможните решения на първоначалния проблем, тогава вторият член в квадратни скоби е равен на нула и преходът към следващата точка се определя само от градиента на целта функция. Ако посочената точка не принадлежи към областта на допустимите решения, тогава поради този член в следващите итерации се постига връщане в областта на допустимите решения
решения. В същото време толкова по-малко a i
, толкова по-бързо се намира приемливо решение, но точността на определянето му намалява. Следователно итеративният процес обикновено започва при относително малки стойности a i
и, продължавайки го, тези стойности постепенно се увеличават.
И така, процесът на намиране на решение на проблем с изпъкнало програмиране с помощта на метода на наказателната функция включва следните стъпки:
1. Определете първоначалното осъществимо решение.
2. Изберете стъпката на изчисление.
3. Намерете за всички променливи частните производни на целевата функция и функциите, които определят диапазона от възможни решения на проблема.
4. По формула (72) се намират координатите на точката, която определя евентуално ново решение на задачата.
5. Проверете дали координатите на намерената точка удовлетворяват системата от ограничения на задачата. Ако не, тогава преминете към следващия етап. Ако координатите на намерената точка определят допустимо решение на задачата, тогава се изследва необходимостта от преминаване към следващото допустимо решение. Ако е необходимо, преминете към етап 2, в противен случай е намерено приемливо решение на първоначалния проблем.
6. Задайте стойностите на тегловните коефициенти и преминете към стъпка 4.
Метод на Arrow-Hurwitz.
Когато намираме решения на проблеми с нелинейното програмиране с помощта на метода на наказателната функция, ние избрахме стойностите a i , произволно, което доведе до значителни колебания в отдалечеността на определените точки от района на допустимите решения. Този недостатък се елиминира при решаването на проблема по метода на Arrow-Hurwitz, според който на следващата стъпка числата a i (k) изчислено по формулата
Като първоначални стойности a i (0) вземете произволни неотрицателни числа.
ПРИМЕРНО РЕШЕНИЕ
Пример 1.
Намерете локалния минимум на функция
Определяне на точка x k
1. Да настроим .
2. Да сложим k = 0 .
3 0 . Нека изчислим
4 0 . Нека изчислим 
. Да преминем към стъпка 5.
5 0 . Да проверим състоянието 
. Да преминем към стъпка 6.
6 0 . Да поставим t0 = 0,5 .
7 0 . Нека изчислим
8 0 . Нека сравним 
. Имаме 
. Заключение: условие за k = 0
не се изпълнява. Да поставим t0 = 0,25
, продължете към повтаряне на стъпки 7, 8.
7 01. Нека изчислим.
8 01. Нека сравним f (x 1) и f (x 0) . Заключение: f (x 1)< f (x 0) . Да преминем към стъпка 9.
9 0 . Нека изчислим
Заключение: вярваме k =1 и отидете на стъпка 3.
3 1. Нека изчислим
4 1. Нека изчислим 
. Да преминем към стъпка 5.
5 1. Да проверим състоянието k ≥ M: k = 1< 10 = M . Да преминем към стъпка 6.
6 1. Да поставим t 1 = 0,25.
7 1. Нека изчислим
8 1. Нека сравним f (x 2) с f (x 1) . Заключение: f (x 2)< f (х 1). Да преминем към стъпка 9.
9 1. Нека изчислим
Заключение: вярваме k = 2 и отидете на стъпка 3.
3 2. Нека изчислим
4 2. Нека изчислим. Да преминем към стъпка 5.
5 2. Да проверим състоянието k ≥ M : k = 2< 10 = М , отидете на стъпка 6.
6 2. Да поставим t 2 =0,25 .
7 2. Нека изчислим
8 2. Нека сравним f (x 3) И f (x 2) . Заключение: f (x 3)< f (х 2) .Преминете към стъпка 9.
9 2. Нека изчислим 
Заключение: вярваме k = 3 и отидете на стъпка 3.
3 3 . Нека изчислим
4 3 . Нека изчислим. Да преминем към стъпка 5.
5 3. Да проверим състоянието k ≥ M : k = 3<10 = М , отидете на стъпка 6.
6 3. Да поставим t3 = 0,25.
7 3. Нека изчислим
8 3. Нека сравним f (x 4) И f (x 3) : f (x 4)< f (х 3) .
9 3. Нека изчислим 
Условията са изпълнени, когато k = 2,3 . Изчисляване
завършен. Намерена точка
На фиг. Получените 3 точки са свързани с пунктирана линия.
II. Точков анализ х 4 .
функция 
е два пъти диференцируема, така че ще проверим достатъчните условия за минимума в точката х 4
. За да направим това, нека анализираме матрицата на Хесиан.
Матрицата е постоянна и положително определена (т.е. . H > 0
), тъй като и двата му ъглови минора са положителни. Следователно точката 
е намереното приближение на локалната минимална точка и стойността 
е намереното приближение на стойността f (x *) =0
. Имайте предвид, че условието H > 0
, същевременно има условие за строга изпъкналост на функцията 
. Следователно има намерени приближения на глобалната минимална точка f(x)
и минималната му стойност при R 2
. ■
Пример 2
Намерете локалния минимум на функция
I. Дефиниция на точка x k, при които е изпълнен поне един от критериите за извършване на изчисления.
1. Да настроим .
Нека намерим градиента на функцията в произволна точка
2. Да сложим k = 0 .
3 0 . Нека изчислим
4 0 . Нека изчислим . Да преминем към стъпка 5.
5 0 . Да проверим състоянието 
. Да преминем към стъпка 6.
6° Следващата точка се намира по формулата
Нека заместим получените изрази за координати в
Нека намерим минимума на функцията f(t 0) от t 0 използвайки необходимите условия за безусловен екстремум:
Оттук t 0 =0,24
. защото 
, намерената стойност на стъпката осигурява минимума на функцията f(t 0)
от t 0
.
Да дефинираме 
7 0 . Ще намерим
8°. Нека изчислим
Заключение: вярваме k = 1 и отидете на стъпка 3.
3 1. Нека изчислим
4 1. Нека изчислим 
5 1. Да проверим състоянието k ≥ 1: k = 1< 10 = М.
6 1. Да дефинираме
7 1. Ще намерим 
:
8 1. Нека изчислим
Ние вярваме k = 2 и отидете на стъпка 3.
3 2. Нека изчислим
4 2. Нека изчислим
5 2. Да проверим състоянието k ≥ M: k = 2< 10 = M .
6 2. Да дефинираме
7 2. Ще намерим 
8 2. Нека изчислим
Ние вярваме k =3 и отидете на стъпка 3.
3 3 . Нека изчислим
4 3 . Нека изчислим.
Изчислението е завършено. Намерена точка
II. Точков анализ х 3 .
В пример 1.1 (Глава 2 §1) беше показано, че функцията f(x) е строго изпъкнал и следователно в точки 3 е намереното приближение на глобалната минимална точка X* .
Пример 3.
Намерете локалния минимум на функция
I. Дефиниция на точка xjk , при които е изпълнен поне един от критериите за извършване на изчисления.
1. Да настроим
Нека намерим градиента на функцията в произволна точка 
2. Да настроим j = 0.
3 0 . Да проверим дали условието е изпълнено
4 0 . Да поставим k = 0.
5 0 . Да проверим дали условието е изпълнено
6 0 . Нека изчислим
7 0 . Да проверим състоянието 
8 0 . Да поставим
9 0 . Нека изчислим 
, Къде
10 0 . Да проверим състоянието
Заключение: приемаме и преминаваме към стъпка 9.
9 01. Нека изчислим x 01 на стъпки
10 01. Да проверим състоянието 
11 0 . Да проверим условията
Ние вярваме k =1 и отидете на стъпка 5.
5 1. Да проверим състоянието
6 1. Нека изчислим
7 1. Да проверим състоянието
8 1. Да поставим
9 1. Нека изчислим
10 1. Да проверим състоянието 
:
11 1. Да проверим условията
Ние вярваме k = 2 , отидете на стъпка 5.
5 2. Да проверим състоянието. Да зададем, отидете на стъпка 3.
3 1. Да проверим състоянието
4 1. Да поставим k = 0.
5 2. Да проверим състоянието
6 2. Нека изчислим
7 2. Да проверим състоянието
8 2. Да поставим
9 2. Нека изчислим
10 2. Да проверим състоянието 
11 2. Да проверим условията
Ние вярваме k =1 и отидете на стъпка 5.
5 3. Да проверим състоянието
6 3. Нека изчислим
7 3. Да проверим условията
8 3. Да поставим
9 3. Нека изчислим
10 3. Да проверим състоянието 
11 3. Да проверим условията
Да поставим k = 2 и отидете на стъпка 5.
5 4. Да проверим състоянието 
Ние вярваме j = 2, x 20 = x 12 и отидете на стъпка 3.
3 2. Да проверим състоянието
4 2. Да поставим k =0 .
5 4. Да проверим състоянието
6 4. Нека изчислим
7 4. Да проверим състоянието
8 4 . Да поставим
9 4. Нека изчислим
10 4. Нека проверим условието и преминем към стъпка 11.
11 4. Да проверим условията
Условията се изпълняват в два последователни цикъла с числа j=2 И j -1= 1 . Изчислението е завършено, точката е намерена
На фиг. Получените 6 точки са свързани с пунктирана линия.
При метода на координатно спускане се спускаме по прекъсната линия, състояща се от прави сегменти, успоредни на координатните оси.
II. Анализ на точка х21.
В пример 1.1 беше показано, че функцията f(x)
е строго изпъкнал, има единствен минимум и следователно точка 
е намереното приближение на глобалната минимална точка.
Във всички градиентни методи, обсъдени по-горе, последователността от точки (xk) се събира в стационарната точка на функцията f(x) с доста общи предложения относно свойствата на тази функция. По-специално теоремата е вярна:
Теорема. Ако функция f(x) е ограничена отдолу, нейният градиент удовлетворява условието на Липшиц () и избора на стойност тн произведени по един от методите, описани по-горе, след което независимо от началната точка х 0 :
при .
При практическо изпълнение на схемата
k =1, 2, … n.
итерациите спират ако за всички i, i = 1, 2, ..., n , условия като
,
където е определено число, характеризиращо точността на намиране на минимума.
При условията на теоремата градиентният метод осигурява сходимост във функцията или до точната долна граница (ако функцията f(x) няма минимум; ориз. 7), или до стойността на функцията в някаква стационарна точка, която е границата на редицата (x k). Не е трудно да се измислят примери, когато в този момент се реализира седло, а не минимум. На практика методите за градиентно спускане уверено заобикалят седловините и намират минимуми на целевата функция (в общия случай локални).
ЗАКЛЮЧЕНИЕ
Примери за градиентни неограничени методи за оптимизация бяха обсъдени по-горе. В резултат на извършената работа могат да се направят следните изводи:
1. Повече или по-малко сложни проблеми за намиране на екстремум при наличие на ограничения изискват специални подходи и методи.
2. Много алгоритми за решаване на ограничени проблеми включват неограничено минимизиране като някаква стъпка.
3. Различни методиспусканията се различават едно от друго по начина, по който избират посоката на спускане и дължината на стъпката по тази посока.
4. Все още няма теория, която да отчита характеристиките на функциите, които описват формулирането на проблема. Предпочитание трябва да се дава на методи, които са по-лесни за управление в процеса на решаване на проблем.
Реалните приложни оптимизационни проблеми са много сложни. Съвременни методиоптимизациите не винаги се справят с решаването на реални проблеми без човешка помощ.
ЛИТЕРАТУРА
1. Косоруков О.А. Изследване на операциите: учебник. 2003 г
2. Пантлеев А.В. Методи за оптимизация в примери и задачи: учебник. полза. 2005 г
3. Шишкин Е.В. Изследване на операциите: учебник. 2006 г
4. Акулич И.Л. Математическо програмиране в примери и задачи. 1986 г
5. Вентцел Е.С. Изследване на операциите. 1980 г
6. Венцел Е.С., Овчаров Л.А. Теория на вероятностите и нейните инженерни приложения. 1988 г
©2015-2019 сайт
Всички права принадлежат на техните автори. Този сайт не претендира за авторство, но предоставя безплатно ползване.
Дата на създаване на страницата: 2017-07-02
Анотация: Тази лекция обхваща широко такива многопараметрични методи за оптимизация като метода на най-стръмното спускане и метода на Дейвидън-Флетчър-Пауъл. Освен това се извършва сравнителен анализ на горните методи, за да се определи най-ефективният, идентифицират се техните предимства и недостатъци; и също така разглежда проблеми с многомерна оптимизация, като метода на дерето и многоекстремалния метод.
1. Метод на най-стръмното спускане
Същността този методе, че с помощта на споменатото по-горе метод на координатно спусканеиздирването се извършва от дадена точкав посока, успоредна на една от осите, до минимална точка в тази посока. След това търсенето се извършва в посока, успоредна на другата ос и т.н. Посоките, разбира се, са фиксирани. Изглежда разумно да се опитаме да модифицираме този метод, така че на всеки етап търсенето на минималната точка да се извършва по "най-добрата" посока. Не е ясно коя посока е "най-добра", но се знае, че посока на градиентае посоката на най-бързо нарастване на функцията. Следователно обратната посока е посоката на най-бързото намаляване на функцията. Това свойство може да се обоснове по следния начин.
Да приемем, че се движим от точка x към следващата точка x + hd, където d е определена посока и h е стъпка с определена дължина. Следователно движението се извършва от точка (x 1, x 2, ..., x n) до точка (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), Къде
Промяната в стойностите на функцията се определя от отношенията
| (1.3) |
До първи ред zx i, като частните производни се изчисляват в точка x. Как трябва да бъдат избрани посоките d i, които да удовлетворяват уравнение (1.2), за да се получи най-голямата стойност на промяната във функцията df? Тук възниква проблем с максимизиране с ограничение. Нека приложим метода на множителите на Лагранж, с помощта на който определяме функцията
Стойността df, удовлетворяваща ограничението (1.2), достига своя максимум, когато функцията
Достига максимума. Негова производна
следователно
 |
(1.6) |
Тогава di ~ df/dx i и посоката d е успоредна на посоката V/(x) в точка x.
по този начин най-голямото местно увеличениефункция за дадена малка стъпка h възниква, когато d е посоката на Vf(x) или g(x) . Следователно посоката на най-стръмното спускане е посоката
В повече в проста формауравнение (1.3) може да се запише по следния начин:
Къде е ъгълът между векторите Vf(x) и dx. За дадена стойност dx минимизираме df, като изберем посоката на dx да съвпада с посоката на -Vf(x).
Коментирайте. Посока на градиентаперпендикулярна на всяка точка на линия с постоянно ниво, тъй като по тази линия функцията е постоянна. Така, ако (d 1, d 2, ..., d n) е малка стъпка по линията на нивото, тогава
И следователно
 |
(1.8) |
Можете също така да търсите не най-добрата точка в посоката на градиента, а някоя по-добра от текущата.
Най-лесният за внедряване от всички локални методи за оптимизация. Има доста слаби условияконвергенция, но скоростта на конвергенция е доста ниска (линейна). Стъпката на градиентния метод често се използва като част от други методи за оптимизация, като например метода на Флетчър-Рийвс.
Описание [ | ]
Подобрения[ | ]
Методът на градиентно спускане се оказва много бавен при движение по дере и с увеличаването на броя на променливите в целевата функция това поведение на метода става типично. За борба с това явление се използва, чиято същност е много проста. След като направи две стъпки на градиентно спускане и получи три точки, третата стъпка трябва да се направи в посока на вектора, свързващ първата и третата точка, по дъното на дерето.
За функции, близки до квадратичните, методът на спрегнатия градиент е ефективен.
Приложение в изкуствени невронни мрежи[ | ]
Методът на градиентно спускане, с известна модификация, се използва широко за обучение на перцептрони и е известен в теорията на изкуствените невронни мрежи като метод на обратно разпространение. При обучение на невронна мрежа от тип персептрон е необходимо да се променят тегловните коефициенти на мрежата, така че да се минимизират средна грешкана изхода на невронната мрежа, когато на входа се подава последователност от входни данни за обучение. Формално, за да се направи само една стъпка с помощта на метода на градиентно спускане (направете само една промяна в мрежовите параметри), е необходимо последователно да се подаде абсолютно целият набор от тренировъчни данни към мрежовия вход, да се изчисли грешката за всеки обект на данните за обучение и изчислете необходимата корекция на мрежовите коефициенти (но не правете тази корекция) и след като изпратите всички данни, изчислете сумата в корекцията на всеки мрежов коефициент (сума от градиенти) и коригирайте коефициентите „една стъпка“ . Очевидно при голям набор от тренировъчни данни алгоритъмът ще работи изключително бавно, така че на практика мрежовите коефициенти често се коригират след всеки тренировъчен елемент, където стойността на градиента се апроксимира от градиента на функцията на разходите, изчислена само за едно обучение елемент. Този метод се нарича стохастичен градиент на спускане или оперативно градиентно спускане . Стохастичен градиентно спусканее една от формите на стохастично приближение. Теорията на стохастичните приближения осигурява условия за конвергенцията на метода на стохастично градиентно спускане.
Връзки [ | ]
- Дж. Матюс.Модул за най-стръмно спускане или метод на градиент. (недостъпна връзка)
Литература [ | ]
- Акулич И. Л.Математическо програмиране в примери и задачи. - М.: Висше училище, 1986. - С. 298-310.
- Гил Ф., Мъри У., Райт М.Практическа оптимизация = Практическа оптимизация. - М.: Мир, 1985.
- Коршунов Ю., Коршунов Ю.Математически основи на кибернетиката. - М.: Енергоатомиздат, 1972.
- Максимов Ю. А., Филиповская Е. А.Алгоритми за решаване на задачи от нелинейното програмиране. - М.: МИФИ, 1982.
- Максимов Ю.Алгоритми за линейно и дискретно програмиране. - М.: МИФИ, 1980.
- Корн Г., Корн Т.Наръчник по математика за учени и инженери. - М.: Наука, 1970. - С. 575-576.
- С. Ю. Городецки, В. А. Гришагин.Нелинейно програмиране и многоекстремална оптимизация. - Нижни Новгород: Издателство на университета в Нижни Новгород, 2007. - стр. 357-363.
Когато използвате метода на най-стръмното спускане при всяка итерация, размерът на стъпката А к се избира от минималното условие на функцията f(x)по посока на спускане, т.е.
f(x[к] -а к f"(x[к])) = f(x[k] -af"(x[к])) .
Това условие означава, че движението по антиградиента се извършва толкова дълго, колкото е стойността на функцията f(x)намалява. От математическа гледна точка, при всяка итерация е необходимо да се реши проблемът с едномерната минимизация според Афункции
й (а) = f(x[к]-af"(x[к])) .
Алгоритъмът на метода за най-стръмно спускане е както следва.
- 1. Задайте координатите на началната точка X.
- 2. В точката X[к], k = 0, 1, 2, ... изчислява стойността на градиента f"(x[к]) .
- 3. Определя се размерът на стъпката а k, чрез едномерно минимизиране над Афункции j (а) = f(x[к]-af"(x[к])).
- 4. Определят се координатите на точката X[k+ 1]:
X аз [k+ 1]= х аз [к] -А к е" аз (X[к]), i = 1,..., p.
5. Проверяват се условията за спиране на стерационния процес. Ако те са изпълнени, изчисленията спират. В противен случай преминете към стъпка 1.
При разглеждания метод посоката на движение от точката X[к] докосва линията на нивото в точката х[k+ 1] (фиг. 2.9). Траекторията на спускане е зигзагообразна, като съседните зигзагообразни връзки са перпендикулярни една на друга. Наистина, стъпка а k се избира чрез минимизиране с Афункции? (а) = f(x[k] -af"(x[к])) . Предпоставкаминимална функция dй (a)/da = 0.След като изчислим производната на сложна функция, получаваме условието за ортогоналност на векторите на посоките на спускане в съседни точки:
dй (a)/da = -f"(x[k+ 1]f"(x[к]) = 0.
ориз. 2.9.
Градиентните методи се сближават до минимум с висока скорост(на скорост геометрична прогресия) за гладки изпъкнали функции. Такива функции имат най-големи Ми най-малко мсобствени стойности на матрицата на вторите производни (матрица на Хесен)
се различават малко един от друг, т.е. матрицата N(x)добре кондициониран. Нека си припомним това собствени стойностиаз аз, аз =1, …, п, матриците са корените на характеристичното уравнение
Въпреки това, на практика, като правило, функциите, които се минимизират, имат лошо обусловени матрици на втори производни (т/м<< 1). Стойностите на такива функции в някои посоки се променят много по-бързо (понякога с няколко порядъка), отколкото в други посоки. Нивелираните им повърхнини в най-простия случай са силно удължени (фиг. 2.10), а в по-сложните случаи се огъват и приличат на дерета. Функции с такива свойства се наричат дере.Посоката на антиградиента на тези функции (виж фиг. 2.10) значително се отклонява от посоката към минималната точка, което води до забавяне на скоростта на конвергенция.
ориз. 2.10.
Скоростта на конвергенция на градиентните методи също зависи значително от точността на градиентните изчисления. Загубата на точност, която обикновено се случва в близост до минимални точки или в ситуация на дере, обикновено може да наруши конвергенцията на процеса на градиентно спускане. Поради горните причини градиентните методи често се използват в комбинация с други, по-ефективни методи в началния етап на решаване на проблем. В този случай точката Xе далеч от минималната точка, а стъпките в посока на антиградиента позволяват да се постигне значително намаляване на функцията.
