Методи за градиентна оптимизация
Градиентните методи са най-често срещаните алгоритми за минимизиране, основната причина за използването им е, че близо до стационарна точка посоката на градиента показва най-високата скорост на промяна на целевата функция. Смята се, че компонентите на градиента и матрицата на Хесиан могат да бъдат записани в аналитична форма или изчислени с достатъчна точност чрез числени методи. Градиентните методи се основават на итеративна процедура, която се изпълнява като
, (4.1)
където е текущото приближение на решението; е параметърът на стъпката, е посоката на търсене в -мерното пространство на всяка стъпка.
Разновидностите на градиентните методи се различават по начина, по който се изчисляват и при всяка итерация. Обикновено изборът се прави чрез решаване на задачата за минимизиране на целевата функция в посока , т.е. решение на задачата за едномерна оптимизация.
Метод за най-бавно спускане
Този метод се нарича още оптимален градиентен метод, метод на Коши и е най-простият градиентен метод и се основава на определяне на минимума на функцията в посоката на градиента. Това е вариант на градиентно спускане спроменливистъпки и има формата
Стойността на стъпката се изчислява при всяка итерация чрез решаване на проблема с едномерното минимизиране
.
Това условие означава, че движението по протежение на антиградиента се извършва, докато той намалява. Критерий за спиране на итеративния процес
Предимството на метода е неговата стабилност, тоест за достатъчно малка стойност, условието
.
Недостатъкът на метода е, че скоростта на конвергенция намалява при приближаване. Методът е в основата на градиентните методи и се използва в началните етапи на търсене на екстремум.
Метод на Нютон
За разлика от най-стръмния метод на спускане, той използване само градиента, но и хесиана на функцията. Използва се квадратична апроксимация на целевата функция в точката, итерациите се извършват по формулата
,
където е матрицата на Хесиан; е градиентът на функцията.
Предимства на метода на Нютон:
– за квадратична минимизирана функция, методът позволява намиране на минимума в една стъпка;
– ако минимизираната функция принадлежи към класа на повърхностите на въртене (т.е. има симетрия), тогава методът осигурява и сходимост в една стъпка (тъй като аргументите на минимизираната функция и нейното квадратично приближение съвпадат в минималната точка);
– ако функцията е асиметрична, то методът не осигурява сходимост в краен брой стъпки. Но за много функции (дори много сложни, например за функцията на Розенброк) се постига по-висока степен на конвергенция, отколкото при използване на други модификации на метода за най-стръмно спускане.
Основните недостатъци на метода на Нютон са:
- необходимостта от изчисляване и обръщане на матрицата на Хесиан при всяка итерация; в допълнение към загубата на компютърно време, тези операции могат да доведат до значителни изчислителни грешки, ако матрицата на Хесиан се окаже лошо обусловена (т.е. стойността на детерминантата на тази матрица ще бъде близка до нула);
- зависимост на сходимостта от началното приближение за неизпъкнали функции.