Та мөн градиентийн чиглэлийн хамгийн сайн цэгийг хайж олохгүй, харин одоогийнхоос илүү сайн цэгийг хайж болно.
Орон нутгийн оновчлолын бүх аргуудыг хэрэгжүүлэхэд хамгийн хялбар. Маш их байна сул нөхцөлнийлэх, гэхдээ нэгдэх хурд нь нэлээд бага (шугаман). Градиент аргын алхамыг ихэвчлэн Флетчер-Ривэсийн арга гэх мэт бусад оновчлолын аргуудын нэг хэсэг болгон ашигладаг.
Тодорхойлолт [ | ]
Сайжруулалт[ | ]
Градиент буух арга нь жалгын дагуу хөдөлж, хувьсагчийн тоо нэмэгдэхэд маш удаан байдаг. зорилгын функцаргын энэ зан байдал нь ердийн зүйл болж хувирдаг. Энэ үзэгдэлтэй тэмцэхийн тулд үүнийг ашигладаг бөгөөд түүний мөн чанар нь маш энгийн байдаг. Градиент уруулын хоёр алхмыг хийж, гурван цэгийг авсны дараа гуу жалгын ёроолын дагуу эхний ба гуравдугаар цэгийг холбосон векторын чиглэлд гурав дахь алхамыг хийх хэрэгтэй.
Квадраттай ойролцоо функцүүдийн хувьд коньюгат градиент арга нь үр дүнтэй байдаг.
Хиймэл мэдрэлийн сүлжээнд хэрэглэх[ | ]
Градиент десантын арга нь зарим өөрчлөлттэй, перцептроныг сургахад өргөн хэрэглэгддэг бөгөөд хиймэл мэдрэлийн сүлжээний онолд буцах тархалтын арга гэж нэрлэгддэг. Перцептрон төрлийн мэдрэлийн сүлжээг сургахдаа сүлжээний жингийн коэффициентийг өөрчлөх шаардлагатай. дундаж алдаасургалтын оролтын өгөгдлийн дарааллыг оролтод нийлүүлэх үед мэдрэлийн сүлжээний гаралт дээр. Албан ёсоор, градиент буурах аргыг ашиглан нэг алхам хийх (сүлжээний параметрүүдэд зөвхөн нэг өөрчлөлт хийх) тулд сургалтын өгөгдлийг бүхэлд нь сүлжээний оролтод дараалан оруулах, объект бүрийн алдааг тооцоолох шаардлагатай. сургалтын өгөгдлийг боловсруулж, сүлжээний коэффициентүүдийн шаардлагатай засварыг тооцоолно (гэхдээ энэ залруулга хийхгүй), бүх өгөгдлийг оруулсны дараа сүлжээний коэффициент тус бүрийн (градиентийн нийлбэр) тохируулгын хэмжээг тооцоолж, "нэг алхам" коэффициентийг залруулна. . Мэдээжийн хэрэг, их хэмжээний сургалтын өгөгдөлтэй бол алгоритм нь маш удаан ажиллах болно, тиймээс практик дээр сүлжээний коэффициентийг сургалтын элемент бүрийн дараа ихэвчлэн тохируулдаг бөгөөд градиент утгыг зөвхөн нэг сургалтаар тооцоолсон зардлын функцын градиентаар ойртуулдаг. бүрэлдэхүүн. Энэ аргыг нэрлэдэг стохастик градиент уналт эсвэл үйл ажиллагааны градиент уналт . Стохастик градиентийн уналт нь стохастик ойртох хэлбэр юм. Стохастик ойртолтын онол нь стохастик градиент удмын аргын нэгдэх нөхцлийг бүрдүүлдэг.
Холбоосууд [ | ]
- Ж.Матьюс.Хамгийн эгц уруудах эсвэл градиент аргын модуль. (боломжгүй холбоос)
Уран зохиол [ | ]
- Акулич I. L.Жишээ, бодлого дахь математикийн програмчлал. - М.: Дээд сургууль, 1986. - P. 298-310.
- Гилл Ф., Мюррей В., Райт М.Практик оновчлол = Практик оновчлол. - М.: Мир, 1985.
- Коршунов Ю.М., Коршунов Ю.М.Кибернетикийн математик үндэс. - М .: Energoatomizdat, 1972.
- Максимов Ю.А., Филлиповская Е.А.Шугаман бус програмчлалын асуудлыг шийдвэрлэх алгоритмууд. - М.: MEPhI, 1982.
- Максимов Ю.А.Шугаман болон дискрет програмчлалын алгоритмууд. - М.: MEPhI, 1980.
- Корн Г., Корн Т.Эрдэмтэн, инженерүүдэд зориулсан математикийн гарын авлага. - М.: Наука, 1970. - P. 575-576.
- С.Ю.Городецкий, В.А.Гришагин.Шугаман бус програмчлал ба олон талт оновчлол. - Нижний Новгород: Нижний Новгородын их сургуулийн хэвлэлийн газар, 2007. - хуудас 357-363.
Хамгийн эгц буух арга нь хувьсах алхамтай градиент арга юм. Давталт бүрт f(x) функцийн хамгийн бага нөхцлөөс буух чиглэлд k алхамын хэмжээг сонгоно, өөрөөр хэлбэл.
Энэ нөхцөл нь f (x) функцийн утга буурах үед эсрэг градиентийн дагуух хөдөлгөөн явагдана гэсэн үг юм. Математикийн үүднээс авч үзвэл давталт бүрт функцээр нэг хэмжээст багасгах асуудлыг шийдэх шаардлагатай байдаг.
()=f (x (k) -f (x (k))))
Үүний тулд алтан харьцааны аргыг ашиглая.
Хамгийн эгц буух аргын алгоритм нь дараах байдалтай байна.
Х (0) эхлэлийн цэгийн координатыг зааж өгсөн болно.
x (k) , k = 0, 1, 2, ... цэг дээр f (x (k)) градиентийн утгыг тооцоолно.
Алхамны хэмжээ k нь функцийг ашиглан нэг хэмжээст багасгах замаар тодорхойлогддог
()=f (x (k) -f (x (k)))).
x (k) цэгийн координатыг дараах байдлаар тодорхойлно.
x i (k+1) = x i (k) - k f i (x (k)), i=1, …, n.
Давтагдах үйл явцыг зогсоох нөхцөлийг шалгана:
||f (x (k +1))|| .
Хэрэв энэ нь биелсэн бол тооцоолол зогсох болно. Үгүй бол бид 1-р алхам руу шилжинэ. Хамгийн эгц буух аргын геометрийн тайлбарыг Зураг дээр үзүүлэв. 1.
Цагаан будаа. 2.1. Хамгийн эгц буух аргын блок диаграмм.
Програм дахь аргыг хэрэгжүүлэх:
Хамгийн огцом буух арга.
Цагаан будаа. 2.2. Хамгийн эгц буух аргыг хэрэгжүүлэх.
Дүгнэлт: Манай тохиолдолд арга нь 7 давталтаар нийлдэг. А7 цэг (0.6641; -1.3313) нь экстремум цэг юм. Холболтын чиглэлийн арга. Квадрат функцүүдийн хувьд та нийлэх хугацаа нь хязгаарлагдмал байх ба n хувьсагчийн тоотой тэнцүү байх градиент аргыг үүсгэж болно.
Дараах тохиолдолд тодорхой чиглэлийг дуудаж, зарим эерэг тодорхой Hess матрицын H-тэй холбоноё.
Тэгэхээр H нэгжийн хувьд коньюгат чиглэл нь тэдгээрийн перпендикуляр гэсэн үг юм. Ерөнхий тохиолдолд H нь ач холбогдолгүй юм. IN ерөнхий тохиолдолконьюгаци гэдэг нь Гесс матрицыг векторт хэрэглэхийг хэлнэ - энэ нь энэ векторыг ямар нэг өнцгөөр эргүүлэх, сунгах эсвэл шахах гэсэн үг юм.
Одоо вектор нь ортогональ, өөрөөр хэлбэл коньюгаци гэдэг нь векторын ортогональ байдал биш, харин эргүүлсэн векторын ортогональ байдал юм.e.i.
Цагаан будаа. 2.3. Коньюгат чиглэлийн аргын блок диаграмм.
Хөтөлбөрт аргын хэрэгжилт: Хамтарсан чиглэлийн арга.
Цагаан будаа. 2.4. Коньюгат чиглэлийн аргын хэрэгжилт.
Цагаан будаа. 2.5. Коньюгат чиглэлийн аргын график.
Дүгнэлт: А3 цэг (0.6666; -1.3333) нь 3 давталтаар олдсон ба экстремум цэг юм.
3. Хязгаарлалт байгаа үед функцийн хамгийн бага ба хамгийн их утгыг тодорхойлох аргуудын шинжилгээ
Үүнийг сануулъя нийтлэг даалгаварнөхцөлт оновчлол нь иймэрхүү харагдаж байна
f(x) ® мин, x О W,
Энд W нь R m-ийн зохих дэд олонлог юм. Тэгш байдлын төрлийн хязгаарлалттай асуудлын дэд анги нь олонлог нь хэлбэрийн хязгаарлалтаар тодорхойлогддогоороо ялгагдана.
f i (x) = 0, энд f i: R m ®R (i = 1, …, k).
ТиймээсW = (x О R m: f i (x) = 0, i = 1, …, k).
f функцийн хувьд "0" индекс бичих нь бидэнд тохиромжтой байх болно. Тиймээс тэгш байдлын төрлийн хязгаарлалттай оновчлолын бодлогыг дараах байдлаар бичнэ
f 0 (x) ® мин, (3.1)
f i (x) = 0, i = 1, …, k. (3.2)
Хэрэв бид одоо f(x) = (f 1 (x), ..., f k (x)) хэлбэртэй координатын тэмдэглэгээ нь R k утгууд бүхий R m дээрх функцийг f гэж тэмдэглэвэл ( 3.1)–(3.2) бид мөн хэлбэрээр бичиж болно
f 0 (x) ® min, f(x) = Q.
Геометрийн хувьд тэгш байдлын төрлийн хязгаарлалттай асуудал нь олон талт дээрх f 0 функцийн графикийн хамгийн доод цэгийг олох бодлого юм (3.1-р зургийг үз).
Бүх хязгаарлалтыг хангасан оноог (жишээ нь багц дахь оноо) ихэвчлэн зөвшөөрөгдөх гэж нэрлэдэг. Зөвшөөрөгдөх x* цэгийг f i (x) = 0, i = 1, ..., k (эсвэл (3.1)–(3.2) асуудлын шийдэл) хязгаарлалтын дор f 0 функцийн нөхцөлт минимум гэж нэрлэдэг. бүх зөвшөөрөгдөх цэгийн хувьд x f 0 (x *) f 0 (x). (3.3)
Хэрэв (3.3) нь зөвхөн x* цэгийн V x * зарим хөршид байрлах зөвшөөрөгдөх х-д хангагдсан бол бид орон нутгийн нөхцөлт минимумыг ярьж байна. Нөхцөлтэй хатуу орон нутгийн болон дэлхийн минимумуудын ойлголтыг байгалийн жамаар тодорхойлдог.
Градиент аргын энэ хувилбарт багасгах дарааллыг (X k) мөн дүрмийн (2.22) дагуу байгуулна. Харин алхамын хэмжээ a k нь туслах нэг хэмжээст багасгах асуудлыг шийдсэний үр дүнд олддог.
мин(j k (a) | a>0 ), (2.27)
Энд j k (a)=f(X k - a· (X k)). Тиймээс давталт бүрт эсрэг градиентийн чиглэлд 
бүрэн буулт хийж байна. Асуудлыг (2.27) шийдвэрлэхийн тулд та 1-р хэсэгт тайлбарласан нэг хэмжээст хайлтын аргуудын аль нэгийг, жишээлбэл, битийн хайлтын арга эсвэл алтан хэсгийн аргыг ашиглаж болно.
Хамгийн эгц буух аргын алгоритмыг тайлбарлая.
Алхам 0.Нарийвчлалын параметрийг e>0, X 0 ОE n -ийг сонгоод k=0 гэж тохируулна.
1-р алхам.(X k) -ийг олж, заасан нарийвчлалд хүрэх нөхцөлийг шалгана уу || (x k) ||£ e. Хэрэв энэ нь сэтгэл хангалуун байвал 3-р алхам, үгүй бол 2-р алхам руу орно.
Алхам 2.Асуудлыг шийдвэрлэх (2.27), i.e. к олох. Дараагийн цэгийг олоод k=k+1 гэж тавиад 1-р алхам руу орно.
Алхам 3 X * = X k, f * = f(X k) гэж тавьж тооцооллыг гүйцээнэ үү.
Функцийг багасгах
f(x)=x 1 2 +4x 2 2 -6x 1 -8x 2 +13; (2.28)
Эхлээд асуудлаа шийдье сонгодогарга. Төлөөлөх тэгшитгэлийн системийг бичье шаардлагатай нөхцөлболзолгүй экстремум
Үүнийг шийдсэний дараа бид хөдөлгөөнгүй X*=(3;1) цэгийг олж авна. Дараа нь гүйцэтгэлийг шалгацгаая хангалттай нөхцөл, үүний тулд бид хоёр дахь деривативын матрицыг олдог
Сильвестерийн шалгуурын дагуу энэ матриц нь " эерэг тодорхойлогдсон тул олсон X * цэг нь f(X) функцийн хамгийн бага цэг юм. Хамгийн бага утга f *=f(X*)=0. Энэ бол асуудлын яг шийдэл юм (11).
Аргын нэг давталт хийцгээе градиент уналттөлөө (2.28). Х 0 =(1;0) эхлэлийн цэгийг сонгон, эхний алхамыг a=1, l=0.5 параметрийг тохируулъя. f(X 0)=8 гэж бодъё.
X 0 цэг дээрх f(X) функцийн градиентийг олъё
(X 0)= = (2.29)
X=X 0 -a· (X 0) шинэ цэгийг координатыг нь тооцож тодорхойлъё.
x 1 = 
x 2 = 
(2.30)
f(X)= f(X 0 -a· (X 0))=200 гэж бодъё. f(X)>f(X 0) тул a=a·l=1·0.5=0.5 гэж үзээд алхамыг хуваана. Бид (2.30) x 1 =1+4a=3 томъёог ашиглан дахин тооцоолно; x 2 =8a=4 ба f(X)=39 утгыг ол. f(X)>f(X 0) дахин тул бид алхамын хэмжээг улам багасгаж a=a·l=0.5·0.5=0.25 гэж тохируулна. Бид x 1 =1+4·0.25=2 координаттай шинэ цэгийг тооцоолно; x 2 =8·0.25=2 ба энэ цэг дэх функцын утга f(X)=5. f(X)-ийг багасгах нөхцөлөөс хойш. Аргыг ашиглан нэг давталт хийцгээе хамгийн эгц буултхувьд (2.28) ижил анхны цэгтэй X 0 =(1;0). Аль хэдийн олдсон градиент (2.29) ашиглан бид олдог X= X 0 -a· (X 0) j 0 (a)=f(X 0 -a· (X 0))=(4a-2) 2 +4(8a-1) 2 функцийг байгуул. Шаардлагатай нөхцөлийг ашиглан үүнийг багасгах замаар j 0 ¢(a)=8·(4a - 2)+64·(8a - 1)=0 Бид алхамын хэмжээ a 0 =5/34 оновчтой утгыг олно. Багасгах дарааллын цэгийг тодорхойлох X 1 = X 0 -a 0 · (X 0) Цэг дэх дифференциал болох 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[ k+ 1] = x[к]-a k f"(x[к] )
,
болон к > 0; к=0, 1, 2, ... Координатын хэлбэрээр энэ процессыг дараах байдлаар бичнэ. x би [ к+1]=x i[к] - a kf(x[к] )
/x i i = 1, ..., n; к= 0, 1, 2,... Давталтын процессыг зогсоох шалгуур болгон аргументыг бага хэмжээгээр нэмэгдүүлэх нөхцөлийн биелэлтийг || x[к+l] -х[к] || <= e
,
либо выполнение условия малости градиента || f'(x[к+l] )
|| <= g
, Энд e ба g-г бага хэмжээгээр өгөв. Заасан нөхцлийг нэгэн зэрэг биелүүлэхээс бүрдэх хосолсон шалгуурыг бас хийх боломжтой. Градиент аргууд нь алхамын хэмжээг сонгохдоо өөр хоорондоо ялгаатай байдаг болон к. Тогтмол алхамтай аргад бүх давталтуудад тодорхой тогтмол алхамын утгыг сонгоно. Нэлээд жижиг алхам болон кфункц буурах, өөрөөр хэлбэл тэгш бус байдлыг хангах болно f(x[ к+1])
= f(x[k] - a k f’(x[к] ))
< f(x[к] )
. Гэсэн хэдий ч энэ нь хамгийн бага цэгт хүрэхийн тулд хүлээн зөвшөөрөгдөөгүй олон тооны давталт хийх шаардлагатай болж магадгүй юм. Нөгөөтэйгүүр, хэт том алхам нь функцийг гэнэтийн өсөлтөд хүргэж эсвэл хамгийн бага цэгийн эргэн тойронд хэлбэлзэл үүсгэдэг (дугуй). Шатны хэмжээг сонгоход шаардлагатай мэдээллийг олж авахад хүндрэлтэй байдаг тул практикт тогтмол алхамтай аргыг бараг ашигладаггүй. Градиент нь давталтын тоо, найдвартай байдлын хувьд илүү хэмнэлттэй байдаг хувьсах алхамын аргууд,Тооцооллын үр дүнгээс хамааран алхамын хэмжээ ямар нэгэн байдлаар өөрчлөгдөх үед. Практикт ашигладаг ийм аргуудын хувилбаруудыг авч үзье. Давталт бүрт хамгийн эгц буух аргыг хэрэглэх үед алхамын хэмжээ болон кфункцийн хамгийн бага нөхцлөөс сонгогдоно f(x)уруудах чиглэлд, өөрөөр хэлбэл. Энэ нөхцөл нь функцийн утга хүртэл антиградиентийн дагуух хөдөлгөөн явагдана гэсэн үг юм f(x)буурдаг. Математикийн үүднээс авч үзвэл давталт бүрт нэг хэмжээст багасгах асуудлыг шийдэх шаардлагатай байдаг. Афункцууд Хамгийн эгц буух аргын алгоритм нь дараах байдалтай байна. 1. Эхлэх цэгийн координатыг тогтооно X.
2. цэг дээр X[к],
k = 0, 1, 2, ... градиентийн утгыг тооцоолно f'(x[к])
. 3. Алхам хэмжээ нь тодорхойлогддог а k, нэг хэмжээст багасгах замаар Афункцууд j (а) = f(x[к]-af"(x[к])).
4. Цэгийн координатыг тодорхойлно X[k+ 1]: x би [ k+ 1]= x i[к]– a k f’ i (x[к]), i = 1,..., х. 5. Стерацийн процессыг зогсоох нөхцөлийг шалгана. Хэрэв тэдгээр нь биелсэн бол тооцоолол зогсох болно. Үгүй бол 1-р алхам руу очно уу. Харгалзан үзэж буй аргад цэгээс хөдөлгөөний чиглэл X[к] цэг дээрх түвшний шугамд хүрнэ x[k+ 1] (Зураг 2.9). Буух зам нь зигзаг бөгөөд зэргэлдээ зигзаг холбоосууд хоорондоо ортогональ байдаг. Үнэхээр алхам а k-ийг багасгах замаар сонгоно Афункцууд? (а) = f(x[к] -af"(x[к]))
. Функцийн хамгийн бага байх шаардлагатай нөхцөл г j (a)/da = 0.Нарийн төвөгтэй функцийн деривативыг тооцоолсны дараа бид зэргэлдээх цэгүүд дэх буурах чиглэлийн векторуудын ортогональ байдлын нөхцөлийг олж авна. dj (a)/da = -f’(x[k+ 1]f'(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[ к] = -f'(x[к])
+b k-1 х[к-l], к>= 1; p = - е’(х)
. b утгууд к-1 чиглэлийг сонгосон байхаар х[к], Р[к-1] байсан Х-холбоо :
(х[к], HP[к- 1])= 0.
Үүний үр дүнд квадрат функцийн хувьд давталттай багасгах үйл явц нь хэлбэртэй байна x[ к+l] =x[к]+a k p[к], Хаана Р[к] -
уруудах чиглэл к-м алхам; ба к -алхамын хэмжээ. Сүүлийнх нь функцийн хамгийн бага нөхцлөөс сонгогдоно f(x) By Ахөдөлгөөний чиглэлд, өөрөөр хэлбэл нэг хэмжээст багасгах асуудлыг шийдсэний үр дүнд: f(x[ к] + a k r[к])
= f(x[к] + ар [к])
. Квадрат функцийн хувьд Fletcher-Reeves коньюгат градиент аргын алгоритм нь дараах байдалтай байна. 1. Цэг дээр Xтооцоолсон х = -f'(x)
. 2. Асаалттай к- m алхам, дээрх томъёог ашиглан алхамыг тодорхойлно Ак .
ба хугацаа X[k+ 1]. 3. Утга тооцоолсон f(x[к+1])
Тэгээд f'(x[к+1])
. 4. Хэрэв f'(x)
= 0, дараа нь цэг X[к+1] нь функцийн хамгийн бага цэг юм f(x).Үгүй бол шинэ чиглэл тодорхойлогддог х[к+l] харилцаанаас дараагийн давталт руу шилжих шилжилтийг хийж байна. Энэ процедур нь квадрат функцийн хамгийн бага утгыг олох болно Палхам. Квадрат бус функцийг багасгах үед Флетчер-Ривзийн арга нь төгсгөлөөс давтагдах шинж чанартай болдог. Энэ тохиолдолд дараа нь (p+ 1) 1-4-р процедурын давталт нь солих замаар мөчлөгөөр давтагдана Xдээр X[П+1] ба тооцоолол нь өгөгдсөн тоо хаана байна. Энэ тохиолдолд аргын дараах өөрчлөлтийг ашиглана. x[ к+l] = x[к]+a k p[к],
p[ к] = -f’(x[к])+
б к- 1 х[к-l], к>= 1; p = -f’( x); f(x[ к] + a k p[к])
= f(x[к] +ap[к];
Энд I- олон индексүүд: I= (0, n, 2 p, цалин, ...), өөрөөр хэлбэл арга бүр шинэчлэгддэг Палхам. Геометрийн утгаКоньюгат градиент арга нь дараах байдалтай байна (Зураг 2.11). Өгөгдсөн эхлэлийн цэгээс Xчиглэлд буух ажлыг гүйцэтгэдэг Р = -f"(x). Яг цэг дээр Xградиент векторыг тодорхойлно f"(x). Учир нь Xчиглэл дэх функцын хамгийн бага цэг юм Р,
Тэр f'(x)
вектор руу ортогональ Р. Дараа нь вектор олдоно Р , Х-тай нийлэх Р. Дараа нь чигийн дагуу функцийн хамгийн бага утгыг олно Ргэх мэт. Коньюгат чиглэлийн аргууд нь багасгах асуудлыг шийдвэрлэхэд хамгийн үр дүнтэй байдаг. Гэсэн хэдий ч тэд тоолох явцад гарсан алдаануудад мэдрэмтгий байдаг гэдгийг тэмдэглэх нь зүйтэй. Олон тооны хувьсагчтай бол алдаа маш их нэмэгдэж, квадрат функцийн хувьд ч процессыг давтах шаардлагатай болно, өөрөөр хэлбэл түүний процесс нь үргэлж тохирохгүй байна. Палхам. Хамгийн эгц буух арга (Англи хэл дээрх "хамгийн эгц буух арга") нь оновчлолын асуудлыг шийдвэрлэх давталтын тоон арга (эхний дараалал) бөгөөд энэ нь зорилгын функцийн экстремумыг (хамгийн бага ба хамгийн их) тодорхойлох боломжийг олгодог. Харгалзан үзэж буй аргын дагуу зорилгын функцийн экстремум (хамгийн их эсвэл хамгийн бага) нь функцийн хамгийн хурдан өсөлт (бууралт) чиглэлд тодорхойлогддог. функцийн градиент (эсрэг градиент) чиглэлд. Нэг цэг дэх градиент функц Энд i, j,…, n нь координатын тэнхлэгүүдтэй параллель нэгж векторууд юм. Суурь цэг дээрх градиент Хамгийн эгц буух арга бол Цаашдын хөгжилградиент буурах арга. Ерөнхийдөө функцийн экстремумыг олох үйл явц нь давтагдах процедур бөгөөд үүнийг дараах байдлаар бичнэ. Энд "+" тэмдэг нь функцийн хамгийн ихийг олоход, "-" тэмдэг нь функцийн хамгийн бага утгыг олоход хэрэглэгддэг; Нэгж чиглэлийн векторыг томъёогоор тодорхойлно. Алхам хэмжээг тодорхойлдог тогтмол бөгөөд бүх i-р чиглэлд ижил байна. Алхам хэмжээ нь хөдөлгөөний чиглэлд, өөрөөр хэлбэл градиент эсвэл эсрэг градиентийн чиглэлд нэг хэмжээст оновчлолын асуудлыг шийдсэний үр дүнд зорилгын функцын f(x)-ийн хамгийн бага нөхцлөөс сонгогдоно. Өөрөөр хэлбэл, алхамын хэмжээг энэ тэгшитгэлийг шийдэх замаар тодорхойлно. Тиймээс тооцооллын үе шатыг сонгосон бөгөөд ингэснээр функц сайжиртал хөдөлгөөнийг хийж, улмаар хэзээ нэгэн цагт туйлын цэгт хүрнэ. Энэ үед хайлтын чиглэлийг дахин тодорхойлж (градиент ашиглан) зорилгын функцийн шинэ оновчтой цэгийг эрэлхийлэх гэх мэт. Тиймээс энэ аргын хувьд хайлт нь илүү том алхмуудаар явагддаг бөгөөд функцийн градиентийг цөөн тооны цэгүүдэд тооцдог. Хоёр хувьсагчийн функцийн хувьд энэ аргадараах геометрийн тайлбартай: цэгээс хөдөлгөөний чиглэл нь цэг дээрх түвшний шугамд хүрдэг. Буух зам нь зигзаг бөгөөд зэргэлдээ зигзаг холбоосууд хоорондоо ортогональ байдаг. Хөрш зэргэлдээх цэгүүд дээр буух чиглэлийн векторуудын ортогональ байх нөхцөлийг дараах илэрхийллээр бичнэ. f(x) функцийн тэнцүү түвшний шугамын график дээр хамгийн эгц буух аргыг ашиглан туйлын цэг хүртэлх хөдөлгөөний траекторийг үзүүлэв. Оновчтой шийдлийн эрэл хайгуул нь давталтын тооцооллын үе шатанд (хэд хэдэн шалгуур) дуусна. Хайлтын зам нь одоогийн хайлтын цэгийн жижиг хэсэгт хэвээр байна: Зорилгын функцийн өсөлт өөрчлөгдөхгүй: Орон нутгийн хамгийн бага цэг дэх зорилгын функцийн градиент тэг болно. Градиент уруудах арга нь жалга даган явахад маш удаан байдаг бөгөөд зорилгын функц дэх хувьсагчдын тоо нэмэгдэх тусам аргын энэ зан үйл нь ердийн шинж чанартай болдог гэдгийг тэмдэглэх нь зүйтэй. Жалга нь хотгор бөгөөд түүний түвшний шугамууд нь хагас тэнхлэг бүхий эллипс хэлбэртэй байдаг бөгөөд олон дахин ялгаатай байдаг. Жалга байгаа тохиолдолд уруудах зам нь жижиг алхам бүхий зигзаг шугам хэлбэртэй байдаг бөгөөд үүний үр дүнд буух хурд хамгийн бага хэмжээнд хүртэл удааширдаг. Энэ нь эдгээр функцүүдийн эсрэг градиентийн чиглэл нь чиглэлээс хамгийн бага цэг хүртэл ихээхэн хазайж байгаа нь тооцооллын нэмэлт сааталд хүргэдэгтэй холбон тайлбарлаж байна. Үүний үр дүнд алгоритм нь тооцооллын үр ашгийг алддаг. Жалга функц Градиент арга нь олон өөрчлөлтийн хамт өргөн тархсан бөгөөд үр дүнтэй аргасудалж буй объектуудын оновчтой байдлыг хайх. Градиент хайлтын сул тал (мөн дээр дурдсан аргууд) нь үүнийг ашиглах үед зөвхөн функцийн орон нутгийн экстремумыг илрүүлэх боломжтой юм. Бусдыг олохын тулд орон нутгийн эрс тэсбусад эхлэлийн цэгүүдээс хайх шаардлагатай. Мөн нэгдэх хурд градиент аргуудмөн градиентийн тооцооны нарийвчлалаас ихээхэн хамаардаг. Ихэвчлэн хамгийн бага цэгүүдийн ойролцоо эсвэл гуу жалганд тохиолддог нарийвчлал алдагдах нь градиент уруудах үйл явцын нэгдлийг тасалдуулж болзошгүй юм. Тооцооллын арга 1-р алхам:Функцийн градиентийг тооцоолох аналитик илэрхийллийн тодорхойлолт (бэлгэдэл хэлбэрээр) Алхам 2: Анхны ойролцоо утгыг тохируулна уу Алхам 3:Сүүлийн хайлтын чиглэлийг дахин тохируулахын тулд алгоритмын процедурыг дахин эхлүүлэх хэрэгцээ тодорхойлогддог. Дахин эхлүүлсний үр дүнд хайлтыг хамгийн хурдан буух чиглэлд дахин хийж байна.
.
f(x[к]–a k f’(x[к]))
= f(x[к] – af"(x[к]))
.
j (а) = f(x[к]-af"(x[к]))
.
,
.
нь бодит домэйн дээрх функцийн аргументын утгууд (хяналттай параметрүүд) юм.нь координатын тэнхлэгүүд дээрх проекцууд нь координаттай холбоотой функцийн хэсэгчилсэн деривативууд болох вектор юм.
нь гадаргуу дээр хатуу ортогональ байх ба түүний чиглэл нь функцийн хамгийн хурдан өсөлтийн чиглэлийг, харин эсрэг чиглэл (антиградиент) нь функцийн хамгийн хурдан буурах чиглэлийг харуулдаг.
- градиент модуль нь градиент эсвэл эсрэг градиентийн чиглэлд функцийн өсөлт, бууралтын хурдыг тодорхойлдог.
