Методы спуска

Методы спускаОбщая схема.Все методы спуска решения задачи безусловнойминимизации различаются либо выбором направления спуска, либо способом движениявдоль направления спуска. Это позволяет написать общую схему методов спуска.Решается задача минимизации функции j x на вс м пространстве En. Методы спуска состоят в следующей процедурепостроения последовательности xk . качестве начального

приближения выбирается любая точкаx0 En. Последовательные приближения x1, x2, строятся по следующей схеме 1 в точке xk выбираютнаправление спуска - Sk 2 находят k 1 -еприближение по формуле xk 1 xk-pkSk.Направление Sk выбирают таким образом, чтобы обеспечить неравенство j xk 1 lt j xk по крайней мере для малых значений величины pk. На вопрос, какому из способоввыбора направления спуска следует отдать предпочтение при решении конкретнойзадачи, однозначного ответа нет.

Число pkопределяет расстояние от точки xk доточки хk 1. Это число называется длиной шага или просто шагом.Основная задача при выборе величины bk - это обеспечить выполнение неравенства j xk 1 lt j xk . Одним из элементарных способов выбора шага является способудвоения шага.Выбирают bk bk-1. Если при этом j xk 1 lt j xk , то либо переходят к следующей k 2 -й итерации, либо выбирают bk 2bk-1. Если значение j х меньше его предыдущего значения, то процессудвоения можно

продолжать до тех пор, пока убывание не прекратится. Если j xk 1 sup3 j xk , то выбирают bk 0.5bk-1. Если j xk-0.5bk-1Sk lt j xk , то полагают xk 1 xk-0.5bk-1Sk и переходят к следующей k 2 -й итерации. Если же j xk-0.5bk-1Sk sup3 j xk , то выбирают bk 0.25bk-1 и т.д.Метод градиентного спуска.Одним из самых распростран нных методов минимизации,связанных с вычислением градиента, является метод спуска по направлениюантиградиента минимизируемой функции.

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

минимизации функции y b j xk-bj xk , что не исключает применение и других способов отысканияbk.Если в качестве bk выбирают точку одномерного минимума функции y b j xk-bSk релаксационный процесс называется методомнаискорейшего спуска xk 1 xk-bkj xk , bk arg min y b j xk-bSk b sup3 0 .Метод покоординатного спуска.Одним из наиболее простых способов определениянаправления спуска является выбор в качестве Sk одного из координатных векторов e1, e2, , en, вследствие чего у xk на каждой итерации

изменяется лишь одна из компонент.Существуют многочисленные варианты покоординатногоспуска. Но в любом из этих методов выбирают в качестве -Sk то из двух направлений, ej, -ej,которому соответствует неравенство j xk , Sk gt 0.В случае, если 0, полагают xk 1 xkи переходят к следующей итерации.Опишем первый цикл метода, состоящий из n итераций. В произвольной точке x0 выбирают S0 e, и определяет величину b0 способомудвоения так, чтобы было j

x1 j x0-b0S0 lt j x0 . Затем выбирают S1 e2 и, полагая b b0,удвоением вычисляют b1 и такдалее. При этом на каждой итерации стремятся определение величины шага методомудвоения осуществлять с наименьшим числом вычислений значений функции j х . Цикл заканчивается при k n-1, после чего начинают следующий цикл, полагая Sn e1 и т.д.Практическое заданиеНа практике нам нужно было найти минимум функции z x x2 y2-xy-3yc точностью e, используя описанные выше методы.

Нахождение минимума моей функции с помощью методапокоординатного спуска.Для нахождения минимума моей функции с помощью методапокоординатного спуска я использовал программу, представленную ниже. Входнымипараметрами этой программы являются координаты начальной точки я взял х 10, y 10 , начальный шаг по х и по y я взял Dх 0.5 и Dy 0.5 , а так же точность e 10-5 большую точность брать не имеетсмысла, поскольку во время выполнения

программы накапливается ошибка и искажаетданные такой точности . Итак, взяв в качестве начальных условий эти значения яполучил координаты точки минимума х 1,0977y 1,931z -3,0142Для получения результата программой было выполнено 24итерации. Нахождение минимума с помощью метода градиентногоспуска.Программа, использованная мной для выполнения этойзадачи представлена ниже.

Поскольку входные параметры этой программы совпадаютсо входными параметрами задачи 1, то я взял их такие же, что и для первойзадачи, чтобы, сравнив полученные результаты и количество итераций, необходимыхдля поиска минимума, я смог сделать какие-либо выводы о преимуществах инедостатках обеих задач из практики.Итак, взяв те же начальные условия я получил следующиерезультаты x 1,0234y 2,0119z -3,094Количество итераций, которое потребовалось длянахождения точки минимума равно 20.

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

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

время и погрешностьизмерений .