Реферат: Решение задач - методы спуска

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

Общая схема.

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

Решается задача минимизациифункции j

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

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

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

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

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

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

Метод спуска, в котором Sk=j

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

Величина b

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

Если в качестве b

kвыбирают точку одномерногоминимума функции y(b)=j(xk-bSk)релаксационный процесс называется методом наискорейшего спуска: xk+1=xk-bkj’(xk), bk=arg min {y(b)=j(xk-bSk) | b³0}.

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

Одним из наиболее простыхспособов определения направления спуска является выбор в качестве Skодного из координатных векторов ±

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

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

[j

’(xk), Sk] > 0.

В случае, если <img src="/cache/referats/492/image002.gif" v:shapes="_x0000_i1025">xk+1=xkи переходят кследующей итерации.

Опишем первый цикл метода,состоящий из nитераций. В произвольной точке x0выбирают S0=±

e, иопределяет величину b0способом удвоения так,чтобы было j(x1)=j(x0-b0S0)<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,00000977

y= 1,99999931

z=-3,00000142

Для получения результатапрограммой было выполнено 24 итерации.

Нахождение минимума с помощью метода градиентногоспуска.

Программа, использованнаямной для выполнения этой задачи представлена ниже.

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

Итак, взяв те же начальныеусловия я получил следующие результаты:

x= 1,00000234

y= 2,00000119

z=-3,00000094

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

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

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

еще рефераты

Еще работы по математике

Реферат по математике

Основы математики

20 Июня 2015

Реферат по математике

Призма

29 Августа 2013

Реферат по математике

Цилиндр

3 Августа 2015

Реферат по математике

Сфера

29 Августа 2013