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

Решается задача минимизации функции j (x) на всём пространстве En. Методы спуска состоят в следующей процедуре построения последовательности {xk}. Â качестве начального приближения выбирается любая точка x0Î En. Последовательные приближения x1, x2, … строятся по следующей схеме:

в точке xk выбирают направление спуска - Sk;

находят (k+1)-е приближение по формуле xk+1=xk-pkSk.

Направление Sk выбирают таким образом, чтобы обеспечить неравенство j (xk+1)<j (xk) по крайней мере для малых значений величины pk. На вопрос, какому из способов выбора направления спуска следует отдать предпочтение при решении конкретной задачи, однозначного ответа нет.

Число pk определяет расстояние от точки xk до точки хk+1. Это число называется длиной шага или просто шагом. Основная задача при выборе величины b k - это обеспечить выполнение неравенства j (xk+1)<j (xk). Одним из элементарных способов выбора шага является способ удвоения шага.

Выбирают b k=b k-1. Если при этом j (xk+1)<j (xk), то либо переходят к следующей (k+2)-й итерации, либо выбирают b k=2b k-1. Если значение j (х) меньше его предыдущего значения, то процесс удвоения можно продолжать до тех пор, пока убывание не прекратится. Если j (xk+1)³ j (xk), то выбирают b k=0.5b k-1. Если j (xk-0.5b k-1Sk)<j (xk), то полагают xk+1=xk-0.5b k-1Sk и переходят к следующей (k+2)-й итерации. Если же j (xk-0.5b k-1Sk)³ j (xk), то выбирают b k=0.25b k-1 и т.д.

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

Метод спуска, в котором Sk=j ’(xk), называется методом градиентного спуска.

Величина b k в методе градиентного спуска традиционно вычисляется путём применения одного из методов одномерной минимизации функции y (b )=j (xk-b j ’(xk)), что не исключает применение и других способов отыскания b k.

Если в качестве b k выбирают точку одномерного минимума функции y (b )=j (xk-b Sk) релаксационный процесс называется методом наискорейшего спуска: xk+1=xk-b kj ’(xk), b k=arg min )=j.

Одним из наиболее простых способов определения направления спуска является выбор в качестве Sk одного из координатных векторов ± e1, ± e2, …, ± en, вследствие чего у xk на каждой итерации изменяется лишь одна из компонент.

Существуют многочисленные варианты покоординатного спуска. Но в любом из этих методов выбирают в качестве -Sk то из двух направлений, +ej, -ej, которому соответствует неравенство

[j ’(xk), Sk] > 0.

В случае, если =0, полагают xk+1=xk и переходят к следующей итерации.

Опишем первый цикл метода, состоящий из n итераций. В произвольной точке x0 выбирают S0=± e, и определяет величину b 0 способом удвоения так, чтобы было j (x1)=j (x0-b 0S0)<j (x0). Затем выбирают S1=± e2 и, полагая b =b 0, удвоением вычисляют b 1 и так далее. При этом на каждой итерации стремятся определение величины шага методом удвоения осуществлять с наименьшим числом вычислений значений функции j (х). Цикл заканчивается при k=n-1, после чего начинают следующий цикл, полагая Sn=± e1 и т.д.

На практике нам нужно было найти минимум функции z(x)=x2+y2-xy-3y c точностью e , используя описанные выше методы.

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

Поделитесь этой записью или добавьте в закладки