Арга хамгийн эгц буулт(Англи уран зохиолд "хамгийн эгц буух арга") нь оновчлолын асуудлыг шийдвэрлэх давталтын тоон арга (эхний дараалал) бөгөөд энэ нь зорилгын функцийн экстремумыг (хамгийн бага ба хамгийн их) тодорхойлох боломжийг олгодог.
нь бодит домэйн дээрх функцийн аргументын утгууд (хяналттай параметрүүд) юм.
Харгалзан үзэж буй аргын дагуу зорилгын функцийн экстремум (хамгийн их эсвэл хамгийн бага) нь функцийн хамгийн хурдан өсөлт (бууралт) чиглэлд тодорхойлогддог. функцийн градиент (эсрэг градиент) чиглэлд. Нэг цэг дэх градиент функц нь координатын тэнхлэгүүд дээрх проекцууд нь координаттай холбоотой функцийн хэсэгчилсэн деривативууд болох вектор юм.
Энд i, j,…, n нь координатын тэнхлэгүүдтэй параллель нэгж векторууд юм.
Суурь цэг дээрх градиент 
нь гадаргуу дээр хатуу ортогональ байх ба түүний чиглэл нь функцийн хамгийн хурдан өсөлтийн чиглэлийг, харин эсрэг чиглэл (антиградиент) нь функцийн хамгийн хурдан буурах чиглэлийг харуулдаг.
Хамгийн эгц буух арга бол Цаашдын хөгжилградиент буурах арга. IN ерөнхий тохиолдолФункцийн экстремумыг олох үйл явц нь давтагдах процедур бөгөөд үүнийг дараах байдлаар бичнэ.
Энд "+" тэмдэг нь функцийн хамгийн ихийг олоход, "-" тэмдэг нь функцийн хамгийн бага утгыг олоход хэрэглэгддэг;
Нэгж чиглэлийн векторыг томъёогоор тодорхойлно.
- градиент модуль нь градиент эсвэл эсрэг градиентийн чиглэлд функцийн өсөлт, бууралтын хурдыг тодорхойлдог.
Алхам хэмжээг тодорхойлдог тогтмол бөгөөд бүх i-р чиглэлд ижил байна.
Алхам хэмжээ нь хөдөлгөөний чиглэлд, өөрөөр хэлбэл градиент эсвэл эсрэг градиентийн чиглэлд нэг хэмжээст оновчлолын асуудлыг шийдсэний үр дүнд зорилгын функцын f(x)-ийн хамгийн бага нөхцлөөс сонгогдоно.
Өөрөөр хэлбэл, алхамын хэмжээг энэ тэгшитгэлийг шийдэх замаар тодорхойлно.
Тиймээс тооцооллын үе шатыг сонгосон бөгөөд ингэснээр функц сайжиртал хөдөлгөөнийг хийж, улмаар хэзээ нэгэн цагт туйлын цэгт хүрнэ. Энэ үед хайлтын чиглэлийг дахин тодорхойлж (градиент ашиглан) зорилгын функцийн шинэ оновчтой цэгийг эрэлхийлэх гэх мэт. Тиймээс энэ аргын хувьд хайлт нь илүү том алхмуудаар явагддаг бөгөөд функцийн градиентийг цөөн тооны цэгүүдэд тооцдог.
Хоёр хувьсагчийн функцийн хувьд энэ аргадараах геометрийн тайлбартай: цэгээс хөдөлгөөний чиглэл нь цэг дээрх түвшний шугамд хүрдэг. Буух зам нь зигзаг бөгөөд зэргэлдээ зигзаг холбоосууд хоорондоо ортогональ байдаг. Хөрш зэргэлдээх цэгүүд дээр буух чиглэлийн векторуудын ортогональ байх нөхцөлийг дараах илэрхийллээр бичнэ.
f(x) функцийн тэнцүү түвшний шугамын график дээр хамгийн эгц буух аргыг ашиглан туйлын цэг хүртэлх хөдөлгөөний траекторийг үзүүлэв.
Оновчтой шийдлийн эрэл хайгуул нь давталтын тооцооллын үе шатанд (хэд хэдэн шалгуур) дуусна.
Хайлтын зам нь одоогийн хайлтын цэгийн жижиг хэсэгт хэвээр байна:
Зорилгын функцийн өсөлт өөрчлөгдөхгүй:
Орон нутгийн хамгийн бага цэг дэх зорилгын функцийн градиент тэг болно.
Градиент уруудах арга нь жалга даган явахад маш удаан байдаг бөгөөд зорилгын функц дэх хувьсагчдын тоо нэмэгдэх тусам аргын энэ зан үйл нь ердийн шинж чанартай болдог гэдгийг тэмдэглэх нь зүйтэй. Жалга нь хотгор бөгөөд түүний түвшний шугамууд нь хагас тэнхлэг бүхий эллипс хэлбэртэй байдаг бөгөөд олон дахин ялгаатай байдаг. Жалга байгаа тохиолдолд уруудах зам нь жижиг алхам бүхий зигзаг шугам хэлбэртэй байдаг бөгөөд үүний үр дүнд буух хурд хамгийн бага хэмжээнд хүртэл удааширдаг. Энэ нь эдгээр функцүүдийн эсрэг градиентийн чиглэл нь чиглэлээс хамгийн бага цэг хүртэл ихээхэн хазайж байгаа нь тооцооллын нэмэлт сааталд хүргэдэгтэй холбон тайлбарлаж байна. Үүний үр дүнд алгоритм нь тооцооллын үр ашгийг алддаг.
Жалга функц
Градиент арга нь олон өөрчлөлтийн хамт өргөн тархсан бөгөөд үр дүнтэй аргасудалж буй объектуудын оновчтой байдлыг хайх. Градиент хайлтын сул тал (мөн дээр дурдсан аргууд) нь үүнийг ашиглах үед зөвхөн функцийн орон нутгийн экстремумыг илрүүлэх боломжтой юм. Бусдыг олохын тулд орон нутгийн эрс тэсбусад эхлэлийн цэгүүдээс хайх шаардлагатай. Мөн градиент аргуудыг нэгтгэх хурд нь градиент тооцооллын нарийвчлалаас ихээхэн хамаардаг. Ихэвчлэн хамгийн бага цэгүүдийн ойролцоо эсвэл гуу жалганд тохиолддог нарийвчлал алдагдах нь градиент уруудах үйл явцын нэгдлийг тасалдуулж болзошгүй юм.
Тооцооллын арга
1-р алхам:Функцийн градиентийг тооцоолох аналитик илэрхийллийн тодорхойлолт (бэлгэдэл хэлбэрээр)
Алхам 2: Анхны ойролцоо утгыг тохируулна уу
Алхам 3:Сүүлийн хайлтын чиглэлийг дахин тохируулахын тулд алгоритмын процедурыг дахин эхлүүлэх хэрэгцээ тодорхойлогддог. Дахин эхлүүлсний үр дүнд хайлтыг хамгийн хурдан буух чиглэлд дахин хийж байна.
Та мөн градиентийн чиглэлийн хамгийн сайн цэгийг хайж олохгүй, харин одоогийнхоос илүү сайн цэгийг хайж болно.
Орон нутгийн оновчлолын бүх аргуудыг хэрэгжүүлэхэд хамгийн хялбар. Маш их байна сул нөхцөлнийлэх, гэхдээ нэгдэх хурд нь нэлээд бага (шугаман). Алхам градиент арга Fletcher-Reeves арга гэх мэт бусад оновчлолын аргуудын нэг хэсэг болгон ихэвчлэн ашигладаг.
Тодорхойлолт [ | ]
Сайжруулалт[ | ]
Градиент уруудах арга нь жалгын дагуу хөдөлж байх үед маш удаан байдаг бөгөөд зорилгын функц дэх хувьсагчдын тоо нэмэгдэх тусам аргын энэ зан үйл нь ердийн шинж чанартай болдог. Энэ үзэгдэлтэй тэмцэхийн тулд үүнийг ашигладаг бөгөөд түүний мөн чанар нь маш энгийн байдаг. Градиент уруулын хоёр алхмыг хийж, гурван цэгийг авсны дараа гуу жалгын ёроолын дагуу эхний ба гуравдугаар цэгийг холбосон векторын чиглэлд гурав дахь алхамыг хийх хэрэгтэй.
Квадраттай ойролцоо функцүүдийн хувьд коньюгат градиент арга нь үр дүнтэй байдаг.
Хиймэл мэдрэлийн сүлжээнд хэрэглэх[ | ]
Градиент десантын арга нь зарим өөрчлөлттэй, перцептроныг сургахад өргөн хэрэглэгддэг бөгөөд хиймэл мэдрэлийн сүлжээний онолд буцах тархалтын арга гэж нэрлэгддэг. Перцептрон төрлийн мэдрэлийн сүлжээг сургахдаа сүлжээний жингийн коэффициентийг өөрчлөх шаардлагатай. дундаж алдаасургалтын оролтын өгөгдлийн дарааллыг оролтод нийлүүлэх үед мэдрэлийн сүлжээний гаралт дээр. Албан ёсоор, градиент буурах аргыг ашиглан нэг алхам хийх (сүлжээний параметрүүдэд зөвхөн нэг өөрчлөлт хийх) тулд сургалтын өгөгдлийг бүхэлд нь сүлжээний оролтод дараалан оруулах, объект бүрийн алдааг тооцоолох шаардлагатай. сургалтын өгөгдлийг боловсруулж, сүлжээний коэффициентүүдийн шаардлагатай засварыг тооцоолно (гэхдээ энэ залруулга хийхгүй), бүх өгөгдлийг оруулсны дараа сүлжээний коэффициент тус бүрийн (градиентийн нийлбэр) тохируулгын хэмжээг тооцоолж, "нэг алхам" коэффициентийг залруулна. . Мэдээжийн хэрэг, их хэмжээний сургалтын өгөгдөлтэй бол алгоритм нь маш удаан ажиллах болно, тиймээс практик дээр сүлжээний коэффициентийг сургалтын элемент бүрийн дараа ихэвчлэн тохируулдаг бөгөөд градиент утгыг зөвхөн нэг сургалтаар тооцоолсон зардлын функцын градиентаар ойртуулдаг. бүрэлдэхүүн. Энэ аргыг нэрлэдэг стохастик градиент уналт эсвэл үйл ажиллагааны градиент уналт . Стохастик градиентийн уналт нь стохастик ойртох хэлбэр юм. Стохастик ойртолтын онол нь стохастик градиент удмын аргын нэгдэх нөхцлийг бүрдүүлдэг.
Холбоосууд [ | ]
- Ж.Матьюс.Хамгийн эгц уруудах эсвэл градиент аргын модуль. (боломжгүй холбоос)
Уран зохиол [ | ]
- Акулич I. L.Жишээ, бодлого дахь математикийн програмчлал. - М.: Дээд сургууль, 1986. - P. 298-310.
- Гилл Ф., Мюррей В., Райт М.Практик оновчлол = Практик оновчлол. - М.: Мир, 1985.
- Коршунов Ю.М., Коршунов Ю.М.Кибернетикийн математик үндэс. - М .: Energoatomizdat, 1972.
- Максимов Ю.А., Филлиповская Е.А.Шугаман бус програмчлалын асуудлыг шийдвэрлэх алгоритмууд. - М.: MEPhI, 1982.
- Максимов Ю.А.Шугаман болон дискрет програмчлалын алгоритмууд. - М.: MEPhI, 1980.
- Корн Г., Корн Т.Эрдэмтэн, инженерүүдэд зориулсан математикийн гарын авлага. - М.: Наука, 1970. - P. 575-576.
- С.Ю.Городецкий, В.А.Гришагин.Шугаман бус програмчлал ба олон талт оновчлол. - Нижний Новгород: Нижний Новгородын их сургуулийн хэвлэлийн газар, 2007. - хуудас 357-363.
Функцийг оруулах дүрэм
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 болно 
Тэмдэглэл: Энэхүү лекц нь хамгийн эгц буух арга, Давидон-Флетчер-Пауэллийн арга зэрэг олон параметрийн оновчлолын аргуудыг өргөнөөр тусгасан болно. Нэмж дурдахад хамгийн үр дүнтэйг тодорхойлохын тулд дээрх аргуудын харьцуулсан шинжилгээг хийж, тэдгээрийн давуу болон сул талуудыг тодорхойлсон; мөн түүнчлэн жалгын арга, олон талт арга зэрэг олон хэмжээст оновчлолын асуудлыг авч үздэг.
1. Хамгийн огцом буух арга
Энэ аргын мөн чанар нь өмнө дурдсан аргыг ашиглах явдал юм координат буух аргаөгөгдсөн цэгээс тэнхлэгүүдийн аль нэгтэй параллель чиглэлд энэ чиглэлийн хамгийн бага цэг хүртэл хайлт хийнэ. Дараа нь хайлтыг нөгөө тэнхлэгтэй параллель чиглэлд хийх гэх мэт. Мэдээжийн хэрэг, чиглэлүүд нь тодорхой байна. Үе шат бүрт хамгийн бага цэгийг хайх нь "хамгийн сайн" чиглэлийн дагуу явагдахын тулд энэ аргыг өөрчлөхийг оролдох нь үндэслэлтэй юм шиг санагдаж байна. Аль чиглэл нь "хамгийн сайн" болох нь тодорхойгүй, гэхдээ энэ нь мэдэгдэж байна градиент чиглэлфункцийн хамгийн хурдан өсөлтийн чиглэл юм. Тиймээс эсрэг чиглэл нь функцийн хамгийн хурдан буурах чиглэл юм. Энэ өмчийг дараах байдлаар зөвтгөж болно.
Бид x цэгээс дараагийн x + hd цэг рүү шилжиж байна гэж бодъё, энд d нь тодорхой чиглэл, h нь тодорхой урттай алхам юм. Үүний үр дүнд (x 1, x 2, ..., x n) цэгээс цэг хүртэл хөдөлгөөнийг хийдэг. (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), Хаана
Функцийн утгын өөрчлөлтийг харилцаа холбоогоор тодорхойлно
| (1.3) |
Нэгдүгээр эрэмбийн zx i хүртэл, хэсэгчилсэн деривативыг x цэг дээр тооцдог. df функцийн өөрчлөлтийн хамгийн их утгыг олж авахын тулд (1.2) тэгшитгэлийг хангах d i чиглэлийг хэрхэн сонгох вэ? Энд хязгаарлалттай хамгийн их болгох асуудал үүсдэг. Лагранжийн үржүүлэгчийн аргыг хэрэглэж, түүний тусламжтайгаар функцийг тодорхойлно
Хязгаарлагдмал (1.2) хангадаг df утга нь функц ажиллах үед дээд цэгтээ хүрдэг
Дээд талдаа хүрдэг. Түүний дериватив
Тиймээс,
 |
(1.6) |
Дараа нь di ~ df/dx i ба d чиглэл нь x цэгийн V/(x) чиглэлтэй параллель байна.
Тиймээс, орон нутгийн хамгийн том өсөлтӨгөгдсөн жижиг алхамын h функц нь d нь Vf(x) эсвэл g(x) -ийн чиглэл байх үед үүсдэг. Тиймээс хамгийн огцом уруудах чиглэл нь чиглэл юм
Энгийн хэлбэрээр (1.3) тэгшитгэлийг дараах байдлаар бичиж болно.
Vf(x) ба dx векторуудын хоорондох өнцөг хаана байна. Өгөгдсөн dx утгын хувьд dx-ийн чиглэл нь -Vf(x) -ийн чиглэлтэй давхцахыг сонгож df-ийг багасгана.
Сэтгэгдэл. Градиент чиглэлтогтмол түвшний шугамын аль ч цэгт перпендикуляр, учир нь энэ шугамын дагуу функц тогтмол байна. Тиймээс хэрэв (d 1, d 2, ..., d n) нь түвшний шугамын дагуух жижиг алхам бол
Тиймээс
 |
(1.8) |
