Хамгийн эгц буух аргыг ашиглан функцийн суурин цэгийг ол. хамгийн эгц буух арга

Функцийг оруулах дүрэм

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.118 – 1.010)
f’(X 2) = 11.76 – 6.12λ 1 = 0
Бид λ 1 = 0.52 болно

Жишээ 6.8.3-1. GDS аргыг ашиглан Q(x,y) функцийн минимумыг ол.

Q(x,y) = x 2 +2y 2; x 0 = 2;y 0 = 1.

Доод тал нь байх хангалттай нөхцлийг шалгаж үзье:

Алгоритмын дагуу нэг давталт хийцгээе.

1. Q(x 0 ,y 0) = 6.

2. x = x 0 ба y = y 0-ийн хувьд,

3. Алхам l k = l 0 = 0.5

Тиймээс 4< 8, следовательно, условие сходимости не выполняется и требуется, уменьшив шаг (l=l /2), повторять п.п.3-4 до выполнения условия сходимости. То есть, полученный шаг используется для нахождения следующей точки траектории спуска.

Аргын мөн чанар нь дараах байдалтай байна. Сонгосон цэгээс (x 0 ,y 0) эсрэг градиентийн чиглэлд цацрагийн дагуух Q(x, y) зорилтын функцийн хамгийн бага утгад хүрэх хүртэл бууралтыг гүйцэтгэнэ (Зураг 6.8.4-1). . Олдсон цэг дээр цацраг нь түвшний шугамд хүрдэг. Дараа нь энэ цэгээс буух нь эсрэг градиентийн чиглэлд (түвшингийн шугамд перпендикуляр) харгалзах туяа шинэ цэгээр дамжин өнгөрөх түвшний шугамд хүрэх хүртэл явагдана.

Зорилго Q(x, y) функцийг l алхамаар илэрхийлье. Энэ тохиолдолд бид зорилтот функцийг тодорхой алхамд нэг хувьсагчийн функц болгон танилцуулж байна. алхамын хэмжээ

Давталт бүрийн алхамын хэмжээг хамгийн бага нөхцлөөр тодорхойлно.

Min( (l)) l k = l*(x k , y k), l >0.

Тиймээс, давталт бүрт l k алхамыг сонгохдоо нэг хэмжээст оновчлолын асуудлыг шийдвэрлэх шаардлагатай. Энэ асуудлыг шийдэх аргын дагуу тэдгээрийг дараахь байдлаар ялгадаг.

· аналитик арга (NAA);

· тоон арга (NMS).

NSA аргад шатлалын утгыг нөхцлөөс гаргаж авдаг ба NSF аргад нэг хэмжээст оновчлолын аргуудын аль нэгийг ашиглан өгөгдсөн нарийвчлалтай сегмент дээр l k утгыг олно.

Жишээ 6.8.4-1. Q(x,y)=x 2 + 2y 2 функцийн хамгийн бага утгыг e=0.1 нарийвчлалтайгаар ол: x 0 =2; y 0 =1.

Аргыг ашиглан нэг давталт хийцгээе NSA.

=(x-2lx) 2 +2(y-4ly) 2 = x 2 -4lx 2 +4l 2 x 2 +2y 2 -16ly 2 +32l 2 y 2 .

¢(l)=0 нөхцөлөөс l*-ийн утгыг олно.

Үүссэн l=l(x,y) функц нь l-ийн утгыг олох боломжийг олгоно. x=2 ба y=1-ийн хувьд l=0.3333 байна.

Дараагийн цэгийн координатыг тооцоолъё.

k=1 үед давталтыг дуусгах шалгуурын биелэлтийг шалгая:

|2*0.6666|>0.1 ба |-0.3333*4|>0.1 тул давталтын процессыг дуусгах нөхцөл хангагдаагүй, өөрөөр хэлбэл. доод тал нь олдсонгүй. Иймд x=x 1 ба y=y 1-ийн l-ийн шинэ утгыг тооцоод дараагийн буух цэгийн координатыг олж авна. Тооцооллыг буух дуусгавар болох нөхцөлийг хангах хүртэл үргэлжилнэ.

Тоон NN арга ба аналитик арга хоёрын ялгаа нь давталт бүрт l-ийн утгыг хайх нь нэг хэмжээст оновчлолын тоон аргуудын аль нэгийг (жишээлбэл, дихотомийн арга эсвэл алтан зүсэлтийн арга) ашиглан хийдэгт оршино. Энэ тохиолдолд зөвшөөрөгдөх утгын хүрээ l - тодорхойгүй байдлын интервал болж үйлчилнэ.

Цэг дэх дифференциал болох f(x) функцийн градиент Xдуудсан n- хэмжээст вектор f(x) , түүний бүрэлдэхүүн хэсгүүд нь функцийн хэсэгчилсэн деривативууд юм f(x),цэг дээр тооцоолно X, өөрөөр хэлбэл

f"(x ) = (df(x)/dh 1 , …, df(x)/dx n) T .

Энэ вектор нь цэгээр дамжин өнгөрөх хавтгайд перпендикуляр байна X, ба функцийн түвшний гадаргуутай шүргэгч f(x),цэгээр дамжин өнгөрөх X.Ийм гадаргуугийн цэг бүрт функц f(x)ижил утгыг авдаг. Функцийг янз бүрийн тогтмол утгатай C 0 , C 1 , ... адилтгаснаар бид түүний топологийг тодорхойлсон хэд хэдэн гадаргууг олж авдаг (Зураг 2.8).

Градиент вектор нь тухайн цэг дэх функцийг хамгийн хурдан өсгөх чиглэлд чиглэнэ. Градиентийн эсрэг талын вектор (-f'(x)) , дуудсан эсрэг градиентфункцийг хамгийн хурдан бууруулахад чиглэнэ. Хамгийн бага цэг дээр функцийн градиент тэг байна. Нэгдүгээр эрэмбийн аргуудыг градиент ба багасгах аргууд гэж нэрлэдэг нь градиентийн шинж чанарт суурилдаг. Эдгээр аргуудыг ерөнхий тохиолдолд ашиглах нь функцийн локал хамгийн бага цэгийг тодорхойлох боломжийг танд олгоно.

Мэдээжийн хэрэг, хэрэв нэмэлт мэдээлэл байхгүй бол эхлэх цэгээс Xгол зүйл рүүгээ орох нь ухаалаг хэрэг юм X, эсрэгтөрөгчийн чиглэлд хэвтэх - функцийн хамгийн хурдан бууралт. Буух чиглэл болгон сонгох[Рк ] эсрэг градиент - f'(x ) [к] X[Рцэг дээр

], бид маягтын давтагдах процессыг олж авдаг X[ 1] = k+[Р]-x f'(x ) , a k f"(x > 0; Р=0, 1, 2, ...

болон к

Координатын хэлбэрээр энэ процессыг дараах байдлаар бичнэ. Р+1]=x би [[Р] - x if(x f'(x ) a k

/x i n; Р= 0, 1, 2,...

i = 1, ..., k+[РДавталтын процессыг зогсоох шалгуур болгон аргументыг бага хэмжээгээр нэмэгдүүлэх нөхцөлийн биелэлтийг || +l][Р] || <= e , либо выполнение условия малости градиента

|| - x[Р f'(x ) || <= g ,

+l]

Заасан нөхцлийг нэгэн зэрэг биелүүлэхээс бүрдэх хосолсон шалгуурыг бас хийх боломжтой. Градиент аргууд нь алхамын хэмжээг сонгохдоо өөр хоорондоо ялгаатай байдаг a k f"(x.

Тогтмол алхамтай аргад бүх давталтуудад тодорхой тогтмол алхамын утгыг сонгоно. Нэлээд жижиг алхам a k f"(xфункц буурах, өөрөөр хэлбэл тэгш бус байдлыг хангах болно

f(x[ Р+1]) = f(x[k] - a k f’(x f'(x )) < f(x f'(x ) .

Гэсэн хэдий ч энэ нь хамгийн бага цэгт хүрэхийн тулд хүлээн зөвшөөрөгдөөгүй олон тооны давталт хийх шаардлагатай болж магадгүй юм. Нөгөөтэйгүүр, хэт том алхам нь функцийг гэнэтийн өсөлтөд хүргэж эсвэл хамгийн бага цэгийн эргэн тойронд хэлбэлзэл үүсгэдэг (дугуй). Шатны хэмжээг сонгоход шаардлагатай мэдээллийг олж авахад хүндрэлтэй байдаг тул практикт тогтмол алхамтай аргыг бараг ашигладаггүй.

Градиент нь давталтын тоо, найдвартай байдлын хувьд илүү хэмнэлттэй байдаг хувьсах алхамын аргууд,Тооцооллын үр дүнгээс хамааран алхамын хэмжээ ямар нэгэн байдлаар өөрчлөгдөх үед. Практикт ашигладаг ийм аргуудын хувилбаруудыг авч үзье.

Давталт бүрт хамгийн эгц буух аргыг хэрэглэх үед алхамын хэмжээ a k f"(xфункцийн хамгийн бага нөхцлөөс сонгогдоно f(x)уруудах чиглэлд, өөрөөр хэлбэл.
f(x[Р]–a k f’(x[Р])) = f(x f'(x – af"(x[Р])) .

Энэ нөхцөл нь функцийн утга хүртэл антиградиентийн дагуух хөдөлгөөн явагдана гэсэн үг юм f(x)буурдаг. Математикийн үүднээс авч үзвэл давталт бүрт нэг хэмжээст багасгах асуудлыг шийдэх шаардлагатай байдаг. Афункцууд
j (а) = f(x[Р]-af"(x[Р])) .

Хамгийн эгц буух аргын алгоритм нь дараах байдалтай байна.

1. Эхлэх цэгийн координатыг тогтооно X.

2. цэг дээр X[Р], k = 0, 1, 2, ... градиентийн утгыг тооцоолно - x[Р]) .

3. Алхам хэмжээ нь тодорхойлогддог а k, нэг хэмжээст багасгах замаар Афункцууд j (а) = f(x[Р]-af"(x[Р])).

4. Цэгийн координатыг тодорхойлно X[X[ 1]:

x би [ X[ 1]= x i[Р]– a k f’ i (x[Р]), i = 1,..., х.

5. Стерацийн процессыг зогсоох нөхцөлийг шалгана. Хэрэв тэдгээр нь биелсэн бол тооцоолол зогсох болно. Үгүй бол 1-р алхам руу очно уу.

Харж байгаа аргад цэгээс хөдөлгөөний чиглэл X[Р] цэг дээрх түвшний шугамд хүрнэ k+[X[ 1] (Зураг 2.9). Буух зам нь зигзаг хэлбэртэй, зэргэлдээ зигзаг холбоосууд хоорондоо ортогональ байдаг. Үнэхээр алхам а k-г багасгах замаар сонгоно Афункцууд? (а) = f(x f'(x -af"(x[Р])) . Функцийн хамгийн бага байх шаардлагатай нөхцөл j г(a)/da = 0.

Нарийн төвөгтэй функцийн деривативыг тооцоолсны дараа бид зэргэлдээх цэгүүд дэх буурах чиглэлийн векторуудын ортогональ байдлын нөхцөлийг олж авна. dj[X[ 1]- x[Р]) = 0.

Градиент аргууд нь гөлгөр гүдгэр функцүүдийн хувьд өндөр хурдтай (геометрийн прогрессийн хурд) хамгийн бага хэмжээнд нийлдэг. Ийм функцууд хамгийн их байдаг Мба хамгийн бага мХоёрдахь деривативын матрицын хувийн утга (Гессийн матриц)

бие биенээсээ бага зэрэг ялгаатай, өөрөөр хэлбэл матриц N(x)сайн нөхцөлтэй. Хувийн утгууд l i гэдгийг санаарай. би =1, …, n, матрицууд нь шинж чанарын тэгшитгэлийн үндэс юм

Гэсэн хэдий ч практикт, дүрмээр бол багасгаж буй функцууд нь хоёр дахь деривативын тохиромжгүй матрицтай байдаг. (т/м<< 1). Зарим чиглэлийн дагуух ийм функцүүдийн утга нь бусад чиглэлээс хамаагүй хурдан (заримдаа хэд хэдэн дарааллаар) өөрчлөгддөг. Тэдний түвшний гадаргуу нь хамгийн энгийн тохиолдолд хүчтэй уртассан (Зураг 2.10), илүү төвөгтэй тохиолдолд нугалж, жалга мэт харагдана. Ийм шинж чанартай функцуудыг нэрлэдэг гуу жалга.Эдгээр функцүүдийн эсрэг градиентийн чиглэл (2.10-р зургийг үз) чиглэлээс хамгийн бага цэг хүртэл ихээхэн хазайдаг бөгөөд энэ нь нэгдэх хурдыг удаашруулахад хүргэдэг.

Градиент аргуудын нэгдэх хурд нь градиент тооцооллын нарийвчлалаас ихээхэн хамаардаг. Ихэвчлэн хамгийн бага цэгүүдийн ойролцоо эсвэл гуу жалганд тохиолддог нарийвчлал алдагдах нь градиент уруудах үйл явцын нэгдлийг тасалдуулж болзошгүй юм. XДээрх шалтгааны улмаас градиент аргуудыг асуудлыг шийдвэрлэх эхний шатанд бусад илүү үр дүнтэй аргуудтай хослуулан ашигладаг. Энэ тохиолдолд гол зүйл

хамгийн бага цэгээс хол байгаа бөгөөд антиградиентийн чиглэлийн алхамууд нь функцийг мэдэгдэхүйц бууруулах боломжийг олгодог.

Дээр авч үзсэн градиент аргууд нь ерөнхий тохиолдолд функцын хамгийн бага цэгийг зөвхөн хязгааргүй тооны давталтаар олдог. Коньюгат градиент арга нь багасгаж буй функцийн геометртэй илүү нийцсэн хайлтын чиглэлийг үүсгэдэг. Энэ нь тэдгээрийн нэгдэх хурдыг ихээхэн нэмэгдүүлж, жишээ нь квадрат функцийг багасгах боломжийг олгодог.

f(x) = (x, Hx) + (b, x) + a тэгш хэмт эерэг тодорхой матрицтайН хязгаарлагдмал тооны алхмаарП,

функцын хувьсагчийн тоотой тэнцүү байна. nМинимум цэгийн ойролцоо байгаа аливаа гөлгөр функцийг квадрат функцээр сайн ойртуулж болох тул квадрат бус функцийг багасгахын тулд коньюгат градиент аргуудыг амжилттай ашигладаг. Энэ тохиолдолд тэдгээр нь хязгаарлагдмал байхаа больж, давтагдах болно. XТодорхойлолтоор бол хоёр - хэмжээст векторТэгээд цагтматрицтай харьцангуй Х(эсвэл Х-коньюгат), хэрэв скаляр үржвэр бол (х, За) = 0.Энд N -хэмжээтэй тэгш хэмтэй эерэг тодорхой матриц П X П.

Коньюгат градиент аргын хамгийн чухал асуудлуудын нэг бол чиглэлийг үр дүнтэй барих асуудал юм. Флетчер-Ривзийн арга нь алхам бүрт антиградиентийг хувиргах замаар энэ асуудлыг шийддэг -f(x[Р]) чиглэлд х[Р], Х-Өмнө нь олдсон чиглэлтэй хослуулах Буух чиглэл болгон сонгох, Буух чиглэл болгон сонгох, ..., Буух чиглэл болгон сонгох[Р-1]. Эхлээд энэ аргыг квадрат функцийг багасгах асуудалтай холбон авч үзье.

Чиглэл Буух чиглэл болгон сонгох[Р]-ийг дараах томъёогоор тооцоолно.

p[ Р] = -- x[Р]) +b k-1 х[Р-l], Р>= 1;

p = - е’(х) .

b утгууд Р-1 чиглэлийг сонгосон байхаар х[Р], Буух чиглэл болгон сонгох[Р-1] байсан Х-холбоо :

(х[Р], HP[к- 1])= 0.

Үүний үр дүнд квадрат функцийн хувьд

,

давталттай багасгах үйл явц нь хэлбэртэй байна

x[ Р f'(x =x[Р]+a k p[Р],

Хаана Буух чиглэл болгон сонгох[Р] - уруудах чиглэл к-м алхам; ба к -алхамын хэмжээ. Сүүлийнх нь функцийн хамгийн бага нөхцлөөс сонгогдоно f(x) А By

f(x[ Р] + хөдөлгөөний чиглэлд, өөрөөр хэлбэл нэг хэмжээст багасгах асуудлыг шийдсэний үр дүнд:[Р]) = f(x[Р] + a k r [Р]) .

ар

Квадрат функцийн хувьд

Fletcher-Reeves коньюгат градиент аргын алгоритм нь дараах байдалтай байна. X 1. Цэг дээр х = -- x) .

тооцоолсон к- 2. Асаалттай А m алхам, дээрх томъёог ашиглан алхамыг тодорхойлно . к X[X[ 1].

ба хугацаа f(x[Р+1]) 3. Утга тооцоолсон - x[Р+1]) .

Тэгээд - x) 4. Хэрэв X[Р= 0, дараа нь цэг +1] нь функцийн хамгийн бага цэг юм f(x). х[РҮгүй бол шинэ чиглэл тодорхойлогддог

+l] харилцаанаас Пдараагийн давталт руу шилжих шилжилтийг хийж байна. Энэ процедур нь квадрат функцийн хамгийн бага утгыг олох болно алхам.Квадрат бус функцийг багасгах үед Флетчер-Ривзийн арга нь төгсгөлөөс давтагдах шинж чанартай болдог. Энэ тохиолдолд дараа нь X(p+ X[П 1) 1-4-р процедурын давталт нь солих замаар мөчлөгөөр давтагдана

x[ Р f'(x дээр[Р]+a k p[Р],

p[ Р] +1] ба тооцоолол нь өгөгдсөн тоо хаана байна. Энэ тохиолдолд аргын дараах өөрчлөлтийг ашиглана.[Р])+ = x к- 1 х[Р-l], Р>= 1;

= -f’(x k+);

f(x[ Р] + б[Р]) = f(x[Р] p = -f’([Р];

.

a k p +apЭнд +ap I - олон индексүүд:= (0, n, 2 П p, цалин, ...)

, өөрөөр хэлбэл арга бүр шинэчлэгддэг Xалхам. Буух чиглэл болгон сонгох = Коньюгат градиент аргын геометрийн утга нь дараах байдалтай байна (Зураг 2.11). Өгөгдсөн эхлэлийн цэгээсчиглэлд буух ажлыг гүйцэтгэдэг X-f"(x ).Яг цэг дээр Xградиент векторыг тодорхойлно Буух чиглэл болгон сонгох, f"(x ] эсрэг градиент -) ). Учир нь Буух чиглэл болгон сонгохчиглэл дэх функцын хамгийн бага цэг юм Буух чиглэл болгон сонгох , ХТэр Буух чиглэл болгон сонгохвектор руу ортогональ Буух чиглэл болгон сонгох. Дараа нь вектор олдоно

Коньюгат чиглэлийн аргууд нь багасгах асуудлыг шийдвэрлэхэд хамгийн үр дүнтэй байдаг. Гэсэн хэдий ч тэд тоолох явцад гарсан алдаануудад мэдрэмтгий байдаг гэдгийг тэмдэглэх нь зүйтэй. Олон тооны хувьсагчтай бол алдаа маш их нэмэгдэж, квадрат функцийн хувьд ч процессыг давтах шаардлагатай болно, өөрөөр хэлбэл түүний процесс нь үргэлж тохирохгүй байна. П p, цалин, ...)

Давталт бүрт хамгийн эгц буух аргыг хэрэглэх үед алхамын хэмжээ А Р функцийн хамгийн бага нөхцлөөс сонгогдоно f(x)уруудах чиглэлд, өөрөөр хэлбэл.

f(x[Р] -а Р ).[Р])) = f(x f'(x -af"(x[Р])) .

Энэ нөхцөл нь функцийн утга хүртэл антиградиентийн дагуух хөдөлгөөн явагдана гэсэн үг юм f(x)буурдаг. Математикийн үүднээс авч үзвэл давталт бүрт нэг хэмжээст багасгах асуудлыг шийдэх шаардлагатай байдаг. Афункцууд

j (а) = f(x[Р]-af"(x[Р])) .

Хамгийн эгц буух аргын алгоритм нь дараах байдалтай байна.

• 1. Эхлэх цэгийн координатыг тогтооно X.
• 2. цэг дээр X[Р], k = 0, 1, 2, ... градиентийн утгыг тооцоолно ).[Р]) .
• 3. Алхам хэмжээ нь тодорхойлогддог а k, нэг хэмжээст багасгах замаар Афункцууд j (а) = f(x[Р]-af"(x[Р])).
• 4. Цэгийн координатыг тодорхойлно X[X[ 1]:

X би [X[ 1]дээр би [Р] -А Р f" би (X[Р]), i = 1,..., х.

5. Стерацийн процессыг зогсоох нөхцөлийг шалгана. Хэрэв тэдгээр нь биелсэн бол тооцоолол зогсох болно. Үгүй бол 1-р алхам руу очно уу.

Харгалзан үзэж буй аргад цэгээс хөдөлгөөний чиглэл X[Р] цэг дээрх түвшний шугамд хүрнэ k+[X[ 1] (Зураг 2.9). Буух зам нь зигзаг бөгөөд зэргэлдээ зигзаг холбоосууд хоорондоо ортогональ байдаг. Үнэхээр алхам а k-г багасгах замаар сонгоно Афункцууд? (а) = f(x f'(x -af"(x[Р])) . Функцийн хамгийн бага байх шаардлагатай нөхцөл Функцийн хамгийн бага байх шаардлагатай нөхцөл j гНарийн төвөгтэй функцийн деривативыг тооцоолсны дараа бид зэргэлдээх цэгүүд дэх буурах чиглэлийн векторуудын ортогональ байдлын нөхцөлийг олж авна.

Функцийн хамгийн бага байх шаардлагатай нөхцөл j (a)/da = -f"(x[X[ 1]).[Р]) = 0.

Цагаан будаа. 2.9.

Градиент аргууд нь гөлгөр гүдгэр функцүүдийн хувьд өндөр хурдтай (геометрийн прогрессийн хурд) хамгийн бага хэмжээнд нийлдэг. Ийм функцууд хамгийн их байдаг Мба хамгийн бага мХоёрдахь деривативын матрицын хувийн утга (Гессийн матриц)

бие биенээсээ бага зэрэг ялгаатай, өөрөөр хэлбэл матриц N(x)сайн нөхцөлтэй. Хувийн утгууд l i гэдгийг санаарай. би =1, …, n, матрицууд нь шинж чанарын тэгшитгэлийн үндэс юм

Гэсэн хэдий ч практикт, дүрмээр бол багасгаж буй функцууд нь хоёр дахь деривативын тохиромжгүй матрицтай байдаг. (т/м<< 1). Зарим чиглэлийн дагуух ийм функцүүдийн утга нь бусад чиглэлээс хамаагүй хурдан (заримдаа хэд хэдэн дарааллаар) өөрчлөгддөг. Тэдний түвшний гадаргуу нь хамгийн энгийн тохиолдолд хүчтэй уртассан (Зураг 2.10), илүү төвөгтэй тохиолдолд нугалж, жалга мэт харагдана. Ийм шинж чанартай функцуудыг нэрлэдэг гуу жалга.Эдгээр функцүүдийн эсрэг градиентийн чиглэл (2.10-р зургийг үз) чиглэлээс хамгийн бага цэг хүртэл ихээхэн хазайдаг бөгөөд энэ нь нэгдэх хурдыг удаашруулахад хүргэдэг.

Цагаан будаа. 2.10.

Градиент аргуудын нэгдэх хурд нь градиент тооцооллын нарийвчлалаас ихээхэн хамаардаг. Ихэвчлэн хамгийн бага цэгүүдийн ойролцоо эсвэл гуу жалганд тохиолддог нарийвчлал алдагдах нь градиент уруудах үйл явцын нэгдлийг тасалдуулж болзошгүй юм. Дээрх шалтгааны улмаас градиент аргуудыг асуудлыг шийдвэрлэх эхний шатанд бусад илүү үр дүнтэй аргуудтай хослуулан ашигладаг. Энэ тохиолдолд гол зүйл Xхамгийн бага цэгээс хол байгаа бөгөөд антиградиентийн чиглэлийн алхамууд нь функцийг мэдэгдэхүйц бууруулах боломжийг олгодог.

Хамгийн эгц буух арга (Англи хэл дээрх "хамгийн эгц буух арга") нь оновчлолын асуудлыг шийдвэрлэх давталтын тоон арга (эхний дараалал) бөгөөд энэ нь зорилгын функцийн экстремумыг (хамгийн бага ба хамгийн их) тодорхойлох боломжийг олгодог.

нь бодит домэйн дээрх функцийн аргументын утгууд (хяналттай параметрүүд) юм.

Харгалзан үзэж буй аргын дагуу зорилгын функцийн экстремум (хамгийн их эсвэл хамгийн бага) нь функцийн хамгийн хурдан өсөлт (бууралт) чиглэлд тодорхойлогддог. функцийн градиент (эсрэг градиент) чиглэлд. Нэг цэг дэх градиент функц нь координатын тэнхлэгүүд дээрх проекцууд нь координаттай холбоотой функцийн хэсэгчилсэн деривативууд болох вектор юм.

Энд i, j,…, n нь координатын тэнхлэгтэй параллель нэгж векторууд юм.

Суурь цэг дээрх градиент нь гадаргуу дээр хатуу ортогональ байх ба түүний чиглэл нь функцийн хамгийн хурдан өсөлтийн чиглэлийг, харин эсрэг чиглэл (антиградиент) нь функцийн хамгийн хурдан буурах чиглэлийг харуулдаг.

Хамгийн эгц буух арга бол градиент буух аргын цаашдын хөгжил юм. Ерөнхийдөө функцийн экстремумыг олох үйл явц нь давтагдах процедур бөгөөд үүнийг дараах байдлаар бичнэ.

Энд "+" тэмдэг нь функцийн хамгийн ихийг олоход, "-" тэмдэг нь функцийн хамгийн бага утгыг олоход хэрэглэгддэг;

Нэгж чиглэлийн векторыг томъёогоор тодорхойлно.

- градиент модуль нь градиент эсвэл эсрэг градиентийн чиглэлд функцийн өсөлт, бууралтын хурдыг тодорхойлдог.

Алхам хэмжээг тодорхойлдог тогтмол бөгөөд бүх i-р чиглэлд ижил байна.

Алхам хэмжээ нь хөдөлгөөний чиглэлд, өөрөөр хэлбэл градиент эсвэл эсрэг градиентийн чиглэлд нэг хэмжээст оновчлолын асуудлыг шийдсэний үр дүнд зорилгын функцын f(x)-ийн хамгийн бага нөхцлөөс сонгогдоно.

Өөрөөр хэлбэл, алхамын хэмжээг энэ тэгшитгэлийг шийдэх замаар тодорхойлно.

Тиймээс тооцооллын үе шатыг сонгосон бөгөөд ингэснээр функц сайжиртал хөдөлгөөнийг хийж, улмаар хэзээ нэгэн цагт туйлын цэгт хүрнэ. Энэ үед хайлтын чиглэлийг дахин тодорхойлж (градиент ашиглан) зорилгын функцийн шинэ оновчтой цэгийг эрэлхийлэх гэх мэт. Тиймээс энэ аргын хувьд хайлт нь илүү том алхмуудаар явагддаг бөгөөд функцийн градиентийг цөөн тооны цэгүүдэд тооцдог.

Хоёр хувьсагчийн функцийн хувьд энэ арга нь дараах геометрийн тайлбартай байна: цэгээс хөдөлгөөний чиглэл нь цэг дээрх түвшний шугамд хүрдэг. Буух зам нь зигзаг бөгөөд зэргэлдээ зигзаг холбоосууд хоорондоо ортогональ байдаг. Хөрш зэргэлдээх цэгүүд дээр буух чиглэлийн векторуудын ортогональ байх нөхцөлийг дараах илэрхийллээр бичнэ.

f(x) функцийн тэнцүү түвшний шугамын график дээр хамгийн эгц буух аргыг ашиглан туйлын цэг хүртэлх хөдөлгөөний траекторийг үзүүлэв.

Оновчтой шийдлийн эрэл хайгуул нь давталтын тооцооллын үе шатанд (хэд хэдэн шалгуур) дуусна.

Хайлтын зам нь одоогийн хайлтын цэгийн жижиг хэсэгт хэвээр байна:

Зорилгын функцийн өсөлт өөрчлөгдөхгүй:

Орон нутгийн хамгийн бага цэг дэх зорилгын функцийн градиент тэг болно.

Градиент уруудах арга нь жалга даган явахад маш удаан байдаг бөгөөд зорилгын функц дэх хувьсагчдын тоо нэмэгдэх тусам аргын энэ зан үйл нь ердийн шинж чанартай болдог гэдгийг тэмдэглэх нь зүйтэй. Жалга нь хотгор бөгөөд түүний түвшний шугамууд нь хагас тэнхлэг бүхий эллипс хэлбэртэй байдаг бөгөөд олон дахин ялгаатай байдаг. Жалга байгаа тохиолдолд уруудах зам нь жижиг алхам бүхий зигзаг шугам хэлбэртэй байдаг бөгөөд үүний үр дүнд буух хурд хамгийн бага хэмжээнд хүртэл удааширдаг. Энэ нь эдгээр функцүүдийн эсрэг градиентийн чиглэл нь чиглэлээс хамгийн бага цэг хүртэл ихээхэн хазайж байгаа нь тооцооллын нэмэлт сааталд хүргэдэгтэй холбон тайлбарлаж байна. Үүний үр дүнд алгоритм нь тооцооллын үр ашгийг алддаг.

Жалганы функц

Градиент арга нь олон тооны өөрчлөлтүүдийн хамт судалж буй объектын оновчтой байдлыг хайх нийтлэг бөгөөд үр дүнтэй арга юм. Градиент хайлтын сул тал (мөн дээр дурдсан аргууд) нь үүнийг ашиглах үед зөвхөн функцийн орон нутгийн экстремумыг илрүүлэх боломжтой юм. Орон нутгийн бусад экстремумуудыг олохын тулд бусад эхлэлийн цэгүүдээс хайх шаардлагатай. Мөн градиент аргуудыг нэгтгэх хурд нь градиент тооцооллын нарийвчлалаас ихээхэн хамаардаг. Ихэвчлэн хамгийн бага цэгүүдийн ойролцоо эсвэл гуу жалганд тохиолддог нарийвчлал алдагдах нь градиент уруудах үйл явцын нэгдлийг тасалдуулж болзошгүй юм.

Тооцооллын арга

1-р алхам:Функцийн градиентийг тооцоолох аналитик илэрхийллийн тодорхойлолт (бэлгэдэл хэлбэрээр)

Алхам 2: Анхны ойролцоо утгыг тохируулна уу

Алхам 3:Сүүлийн хайлтын чиглэлийг дахин тохируулахын тулд алгоритмын процедурыг дахин эхлүүлэх хэрэгцээ тодорхойлогддог. Дахин эхлүүлсний үр дүнд хайлтыг хамгийн хурдан буух чиглэлд дахин хийж байна.