Функцийг оруулах дүрэм
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-ийг тодорхойлохын тулд нэг хэмжээст оновчлолын дурын аргыг ашигладаг. Энэ тохиолдолд энэ аргыг хамгийн эгц буух арга гэж нэрлэдэг. Дүрмээр бол, in ерөнхий тохиолдолФункцийн хамгийн бага хэмжээнд хүрэхийн тулд нэг алхам хангалттай биш бөгөөд дараагийн тооцоолол нь үр дүнг сайжруулах боломжийг олгох хүртэл процесс давтагдана.
Хэрэв орон зай зарим хувьсагчид маш урт байвал "жалга" үүсдэг. Хайлтын ажил удааширч, "жалга"-ны ёроолд зигзаг болж магадгүй юм. Заримдаа шийдлийг хүлээн зөвшөөрөгдсөн хугацаанд олж авах боломжгүй байдаг.
Аргын өөр нэг сул тал нь зогсоох шалгуур байж болно ||▽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 болно 
Асуудлын томъёолол
Функцийг өгье f(x) Rn
Шаардлагатай f(x) X = Rn
Хайлтын стратеги
х к
} , k = 0.1,...,
тиймэрхүү 
, k = 0.1,...
. Дараалсан цэгүүд ( х к
) дүрмийн дагуу тооцоолно
цэг хаана байна x 0 Хэрэглэгчийн тодорхойлсон; алхамын хэмжээ tk утга тус бүрээр тодорхойлно к нөхцөл байдлаас
Асуудлыг (3) шаардлагатай хамгийн бага нөхцөлийг ашиглан шийдэж, дараа нь хангалттай хамгийн бага нөхцлийг шалгана. Энэ замыг багасгахад хангалттай энгийн функцээр эсвэл хангалттай урьдчилсан байдлаар ашиглаж болно. нарийн төвөгтэй функц 
олон гишүүнт P(t k)
(ихэвчлэн хоёр, гурав дахь зэрэг), дараа нь нөхцөлийг нөхцөлөөр, нөхцөлийг нөхцөлөөр сольдог 
Дараалал (хк)
цэг дээр дуусна х к
, үүний төлөө, хаана ε
- өгөгдсөн жижиг эерэг тоо, эсвэл k ≥ М
, Хаана М
- давталтын хязгаарлагдмал тоо, эсвэл хоёр тэгш бус байдлыг хоёр зэрэг гүйцэтгэх; 
, 
Хаана ε 2
- жижиг эерэг тоо. Асуулт бол оноо чадах эсэх юм х к
хүссэн орон нутгийн хамгийн бага цэгийн олсон ойролцоо гэж үзнэ x*
, нэмэлт судалгаагаар шийдвэрлэгддэг.
Аргын геометрийн тайлбар n=2 Зураг дээр. 4.
Координатын буух арга
Асуудлын томъёолол
Функцийг өгье f(x) , багц дээр доороос хязгаарлагдсан Rn мөн түүний бүх цэгүүдэд тасралтгүй хэсэгчилсэн деривативтай байх.
f(x) боломжтой шийдлүүдийн багц дээр X = Rn , өөрөөр хэлбэл ийм цэгийг олоорой
Хайлтын стратеги
Асуудлыг шийдвэрлэх стратеги нь цэгүүдийн дарааллыг бий болгох явдал юм ( х к
} , k = 0.1,...,
тиймэрхүү , k = 0.1,...
. Дараалсан цэгүүд ( х к
) дүрмийн дагуу циклээр тооцно
(4)
Хаана j - тооцооллын мөчлөгийн дугаар; j = 0,1,2,...; к - гогцоон доторх давталтын дугаар, k = 0,1,... ,n - 1; e k +1 , k = 0,l,...,n - 1 -нэгж вектор, (k+1) -дахь проекц нь 1-тэй тэнцүү; цэг x 00 хэрэглэгчийн тодорхойлсон, алхамын хэмжээ tk нөхцөлөөс сонгогдоно
эсвэл 
.
Хэрэв одоогийн үед сонгосон нөхцөл tk
биелэгдээгүй бол алхам нь хагас болон хугацаатай 
дахин тооцоолно. Тогтмол j-ийн хувьд тоотой нэг давталтаар үүнийг харахад хялбар байдаг к
цэгийн зөвхөн нэг проекц өөрчлөгдөнө x jk
, дугаартай k+1
, мөн бүх мөчлөгийн туршид тоогоор j
, өөрөөр хэлбэл -ээс эхэлдэг k = 0
ба төгсгөл k = n -1
, цэгийн бүх n проекц өөрчлөгдөнө x j0
. Энэ цэгийн дараа x j n
дугаарыг өгсөн x j + 1.0
, мөн үүнийг тооцооллын эхлэлийн цэг болгон авдаг j+1
мөчлөг. Тооцоолол нь тухайн цэг дээр дуусна x jk
Тооцооллын эцсийн гурван шалгуурын дор хаяж нэг нь хангагдсан тохиолдолд: 
, эсвэл , эсвэл тэгш бус байдлын давхар гүйцэтгэл.
Тооцооллын үр дүнд олж авсан оноог дарааллын элемент болгон бичиж болно (xl), Хаана l=n*j+k - цэгийн серийн дугаар,
n = 2-ын аргын геометрийн тайлбарыг Зураг дээр үзүүлэв. 5.
4. Фрэнк-Вольфийн арга .
Бид хотгор функцийн хамгийн их утгыг олох хэрэгтэй гэж бодъё
Нөхцөлөөр
Энэ асуудлын онцлог шинж чанар нь түүний хязгаарлалтын систем нь зөвхөн шугаман тэгш бус байдлыг агуулдаг явдал юм. Энэ шинж чанар нь судалж буй цэгийн ойролцоо шугаман бусыг солих үндэс суурь болно зорилгын функцшугаман, үүний улмаас анхны асуудлын шийдэл нь шугаман програмчлалын асуудлуудын дараалсан шийдэлд буурдаг.
Асуудлын шийдлийг олох үйл явц нь асуудлыг шийдвэрлэх боломжтой шийдлүүдийн бүсэд хамаарах цэгийг тодорхойлохоос эхэлдэг.
270
зуслангийн байшин Гол нь энэ байг X(к)
дараа нь энэ үед (57) функцийн градиентийг тооцоолно
Мөн шугаман функц байгуул
Дараа нь (58) ба (59) хязгаарлалтын дагуу энэ функцийн хамгийн их утгыг ол. Энэ асуудлын шийдлийг цэгээр тодорхойлъё Z(k)
. Дараа нь цэгийн координатыг анхны асуудлын шинэ боломжит шийдэл болгон авна X(k+1)
:
Хаана λk - тодорхой тоо нь тооцооллын алхам гэж нэрлэгддэг бөгөөд тэгээс нэг (0<λ к < 1). Это число λk дур мэдэн авсан эсвэл тодорхойлсон
ингэснээр тухайн цэг дээрх функцийн утга X (k +1) f(X (k +1)) , хамаарна λk , дээд тал нь байсан. Үүнийг хийхийн тулд тэгшитгэлийн шийдлийг олж, түүний хамгийн жижиг үндсийг сонгох хэрэгтэй. Хэрэв түүний утга нэгээс их байвал бид тавих хэрэгтэй λk=1 . Тоо тодорхойлсны дараа λk цэгийн координатыг ол X(k+1) доторх зорилгын функцийн утгыг тооцоолж, шинэ цэг рүү шилжих хэрэгцээг тодорхойлно X(k+2) . Хэрэв ийм хэрэгцээ байгаа бол цэг дээр тооцоол X(k+1) зорилгын функцийн градиент, харгалзах шугаман програмчлалын бодлого руу очиж түүний шийдлийг ол. Цэгийн координатыг тодорхойлох ба X(k+2) цаашид тооцоо хийх шаардлагатай эсэхийг судлах. Хязгаарлагдмал тооны алхмуудын дараа анхны асуудлын шийдлийг шаардлагатай нарийвчлалтайгаар олж авна.
Тиймээс Франк-Вольфын аргыг ашиглан (57) - (59) асуудлын шийдлийг олох үйл явц нь дараах үе шатуудыг агуулна.:
1. Асуудлын анхны боломжит шийдлийг тодорхойлох.
2. Зөвшөөрөгдөх шийдийн цэг дэх функцийн градиентийг (57) ол.
3. (60) функцийг байгуулж (58) ба (59) нөхцлөөр түүний хамгийн их утгыг ол.
4. Тооцооллын үе шатыг тодорхойлох.
5. Томьёог (61) ашиглан шинэ боломжит шийдлийн бүрэлдэхүүн хэсгүүдийг олно.
6. Дараагийн боломжит шийдэлд шилжих хэрэгцээг шалга. Шаардлагатай бол 2-р үе шат руу шилжинэ үү, эс тэгвээс анхны асуудлыг шийдэх боломжтой шийдлийг олно.
Торгуулийн чиг үүргийн арга.
Хонхор функцийн хамгийн их утгыг тодорхойлох асуудлыг авч үзье
f (x 1, x 2, .... x n)нөхцөлд g i (x 1, x 2, .... x n) ≤ b i (i=l, m) , x j ≥ 0 (j=1, n) , Хаана g i (x 1, x 2, .... x n) - гүдгэр функцууд.
Энэ асуудлыг шууд шийдэхийн оронд функцийн хамгийн их утгыг ол F(x 1, x 2, ...., x n)= f(x 1, x 2, ...., x n) +H(x 1, x 2, ...., x n) бодлогын зорилгын функцын нийлбэр ба зарим функц
H(x 1, x 2, ...., x n), хязгаарлалтын системээр тодорхойлогдох ба дуудагдсан торгуулийн функц. Торгуулийн функцийг янз бүрийн аргаар байгуулж болно. Гэсэн хэдий ч ихэнхдээ иймэрхүү харагддаг
А a i > 0
- жингийн коэффициентийг илэрхийлэх зарим тогтмол тоо.
Торгуулийн функцийг ашигласнаар тэд хүлээн зөвшөөрөгдсөн шийдлийг олж авах хүртэл нэг цэгээс нөгөө цэг рүү дараалан шилждэг. Энэ тохиолдолд дараагийн цэгийн координатыг томъёог ашиглан олно
Сүүлчийн хамаарлаас үзэхэд хэрэв өмнөх цэг нь анхны асуудлын боломжит шийдлүүдийн бүсэд байгаа бол дөрвөлжин хаалтанд байгаа хоёр дахь гишүүн нь тэгтэй тэнцүү бөгөөд дараагийн цэг рүү шилжих шилжилтийг зөвхөн зорилгын градиентаар тодорхойлно. функц. Хэрэв заасан цэг нь зөвшөөрөгдөх уусмалын бүсэд хамаарахгүй бол дараагийн давталтуудад энэ нэр томъёоны улмаас зөвшөөрөгдөх уусмалын бүсэд буцаж ирдэг.
шийдвэрүүд. Үүний зэрэгцээ, бага байна a i
, хүлээн зөвшөөрөгдөх шийдлийг хурдан олох боловч түүнийг тодорхойлох нарийвчлал буурдаг. Тиймээс давтагдах үйл явц нь ихэвчлэн харьцангуй бага утгуудаас эхэлдэг a i
мөн үүнийг үргэлжлүүлснээр эдгээр үнэ цэнэ аажмаар нэмэгддэг.
Тиймээс торгуулийн функцын аргыг ашиглан гүдгэр програмчлалын асуудлын шийдлийг олох үйл явц нь дараахь алхмуудыг агуулна.
1. Анхны боломжтой шийдлийг тодорхойлох.
2. Тооцооллын алхамыг сонгоно уу.
3. Бүх хувьсагчийн хувьд асуудлын боломжит шийдлүүдийн хүрээг тодорхойлдог зорилгын функц ба функцүүдийн хэсэгчилсэн деривативуудыг ол.
4. Томьёог (72) ашиглан асуудлын шинэ шийдлийг тодорхойлох цэгийн координатуудыг олно.
5. Олдсон цэгийн координатууд асуудлын хязгаарлалтын системийг хангаж байгаа эсэхийг шалга. Үгүй бол дараагийн шат руу шилжинэ үү. Хэрэв олсон цэгийн координатууд нь асуудлын зөвшөөрөгдөх шийдлийг тодорхойлсон бол дараагийн зөвшөөрөгдөх шийдэлд шилжих хэрэгцээг судална. Шаардлагатай бол 2-р үе шат руу шилжинэ үү, эс тэгвээс анхны асуудлыг шийдэх боломжтой шийдэл олдсон байна.
6. Жинлэх коэффициентийн утгыг тохируулаад 4-р алхам руу шилжинэ.
Arrow-Hurwitz арга.
Торгуулийн функцын аргыг ашиглан шугаман бус програмчлалын асуудлын шийдлийг олохдоо бид утгуудыг сонгосон a i , дур зоргоороо, энэ нь боломжит шийдлүүдийн бүсээс тодорхойлсон цэгүүдийн зайд мэдэгдэхүйц хэлбэлзэлд хүргэсэн. Асуудлыг Arrow-Hurwitz аргаар шийдвэрлэх үед энэ дутагдал арилдаг бөгөөд үүний дагуу дараагийн алхамд тоонууд гарч ирнэ. би (к) томъёогоор тооцоолно
Анхны утгууд шиг a i (0) дурын сөрөг бус тоонуудыг авна.
ШИЙДВЭРИЙН ЖИШЭЭ
Жишээ 1.
Функцийн локал минимумыг ол
Нэг цэгийг тодорхойлох х к
1. Тохируулъя.
2. Тавьцгаая k = 0 .
гучин. Тооцоод үзье
4 0 . Тооцоод үзье 
. 5-р алхам руу шилжье.
50 . Нөхцөл байдлыг шалгацгаая 
. 6-р алхам руу шилжье.
6 0 . Тогтооцгооё t0 = 0.5 .
7 0 . Тооцоод үзье
8 0 . Харьцуулъя 
. Бидэнд байгаа 
. Дүгнэлт: нөхцөл k = 0
гүйцэтгээгүй байна. Тогтооцгооё t0 = 0.25
, 7, 8-р алхмуудыг давт.
7 01. Тооцоод үзье.
8 01. Харьцуулъя f (x 1) ба f (x 0) . Дүгнэлт: f (x 1)< f (x 0) . 9-р алхам руу шилжье.
9 0 . Тооцоод үзье
Дүгнэлт: бид итгэж байна k =1 3-р алхам руу шилжинэ.
3 1. Тооцоод үзье
4 1. Тооцоод үзье 
. 5-р алхам руу шилжье.
5 1. Нөхцөл байдлыг шалгацгаая k ≥ M: k = 1< 10 = M . 6-р алхам руу шилжье.
6 1. Тогтооцгооё t 1 = 0.25.
7 1. Тооцоод үзье
8 1. Харьцуулъя f (x 2) нь f (x 1) . Дүгнэлт: f (x 2)< f (х 1). 9-р алхам руу шилжье.
9 1. Тооцоод үзье
Дүгнэлт: бид итгэж байна k = 2 3-р алхам руу шилжинэ.
3 2. Тооцоод үзье
4 2. Тооцоод үзье. 5-р алхам руу шилжье.
5 2. Нөхцөл байдлыг шалгацгаая k ≥ М : k = 2< 10 = М , 6-р алхам руу очно уу.
6 2. Тогтооцгооё t 2 =0,25 .
7 2. Тооцоод үзье
8 2. Харьцуулъя f (x 3) Тэгээд f (x 2) . Дүгнэлт: f (x 3)< f (х 2) .9-р алхам руу очно уу.
9 2. Тооцоод үзье 
Дүгнэлт: бид итгэж байна k = 3 3-р алхам руу шилжинэ.
3 3 . Тооцоод үзье
4 3 . Тооцоод үзье. 5-р алхам руу шилжье.
5 3. Нөхцөл байдлыг шалгацгаая k ≥ М : k = 3<10 = М , 6-р алхам руу очно уу.
6 3. Тогтооцгооё t 3 = 0.25.
7 3. Тооцоод үзье
8 3. Харьцуулъя f (x 4) Тэгээд f (x 3) : f (x 4)< f (х 3) .
9 3. Тооцоод үзье 
Нөхцөл нь хэзээ хангагдана k = 2.3 . Тооцоолол
дууссан. Цэг олдлоо
Зураг дээр. Үүссэн 3 цэгийг тасархай шугамаар холбосон.
II. Цэгний шинжилгээ x 4 .
Чиг үүрэг 
нь хоёр дахин ялгагдах боломжтой тул бид цэг дээр хамгийн бага байх хангалттай нөхцлийг шалгах болно x 4
. Үүнийг хийхийн тулд Hessian матрицад дүн шинжилгээ хийцгээе.
Матриц нь тогтмол бөгөөд эерэг тодорхой (жишээ нь. . H > 0
) учир нь түүний өнцгийн багачууд хоёулаа эерэг байна. Тиймээс цэг 
нь орон нутгийн хамгийн бага цэгийн олсон ойролцоо, утга юм 
утгын олсон ойролцоо утга юм f (x *) =0
. нөхцөл байгааг анхаарна уу H > 0
, нэгэн зэрэг функцийн хатуу гүдгэр байх нөхцөл бий 
. Үүний үр дүнд дэлхийн хамгийн бага цэгийн ойролцоо тооцоолол олддог f(x)
ба түүний хамгийн бага утга R 2
. ■
Жишээ 2
Функцийн локал минимумыг ол
I. Цэгийн тодорхойлолт х к, тооцооллыг дуусгах шалгуурын дор хаяж нэг нь хангагдсан байх.
1. Тохируулъя.
Дурын цэг дээрх функцийн градиентийг олъё
2. Тавьцгаая k = 0 .
гучин. Тооцоод үзье
4 0 . Тооцоод үзье . 5-р алхам руу шилжье.
50 . Нөхцөл байдлыг шалгацгаая 
. 6-р алхам руу шилжье.
6° Дараагийн цэгийг томъёогоор олно
Олж авсан илэрхийлэлүүдийг координатуудад орлуулъя
Функцийн хамгийн бага утгыг олъё f(t 0) By t 0 болзолгүй экстремумын зайлшгүй нөхцөлийг ашиглан:
Эндээс t 0 =0.24
. Учир нь 
, олсон алхамын утга нь функцийн хамгийн бага утгыг өгдөг f(t 0)
By t 0
.
Тодорхойлъё 
7 0 . Бид олох болно
8°. Тооцоод үзье
Дүгнэлт: бид итгэж байна k = 1 3-р алхам руу шилжинэ.
3 1. Тооцоод үзье
4 1. Тооцоод үзье 
5 1. Нөхцөл байдлыг шалгацгаая k ≥ 1: k = 1< 10 = М.
6 1. Тодорхойлъё
7 1. Бид олох болно 
:
8 1. Тооцоод үзье
Бид итгэж байна k = 2 3-р алхам руу шилжинэ.
3 2. Тооцоод үзье
4 2. Тооцоод үзье
5 2. Нөхцөл байдлыг шалгацгаая k ≥ M: k = 2< 10 = M .
6 2. Тодорхойлъё
7 2. Бид олох болно 
8 2. Тооцоод үзье
Бид итгэж байна k =3 3-р алхам руу шилжинэ.
3 3 . Тооцоод үзье
4 3 . Тооцоод үзье.
Тооцоолол дууссан. Цэг олдлоо
II. Цэгний шинжилгээ x 3 .
Жишээ 1.1-д (2-р бүлэг §1) функцийг харуулсан f(x) нь хатуу гүдгэр тул 3-р цэгт дэлхийн хамгийн бага цэгийн олсон ойролцоо байна. X* .
Жишээ 3.
Функцийн локал минимумыг ол
I. Цэгийн тодорхойлолт xjk , тооцооллыг дуусгах шалгуурын дор хаяж нэг нь хангагдсан байх.
1. Тохируулъя
Дурын цэг дээрх функцийн градиентийг олъё 
2. Тохируулъя j = 0.
гучин. Нөхцөл хангагдсан эсэхийг шалгацгаая
4 0 . Тогтооцгооё k = 0.
50 . Нөхцөл хангагдсан эсэхийг шалгацгаая
6 0 . Тооцоод үзье
7 0 . Нөхцөл байдлыг шалгацгаая 
8 0 . Тогтооцгооё
9 0 . Тооцоод үзье 
, Хаана
100 . Нөхцөл байдлыг шалгацгаая
Дүгнэлт: бид таамаглаж, 9-р алхам руу шилждэг.
9 01. Тооцоод үзье x 01 алхамаар
10 01. Нөхцөл байдлыг шалгацгаая 
11 0 . Нөхцөл байдлыг шалгацгаая
Бид итгэж байна k =1 5-р алхам руу очно уу.
5 1. Нөхцөл байдлыг шалгацгаая
6 1. Тооцоод үзье
7 1. Нөхцөл байдлыг шалгацгаая
8 1. Тогтооцгооё
9 1. Тооцоод үзье
10 1. Нөхцөл байдлыг шалгацгаая 
:
11 1. Нөхцөл байдлыг шалгацгаая
Бид итгэж байна k = 2 , 5-р алхам руу очно уу.
5 2. Нөхцөл байдлыг шалгацгаая. Тохируулъя, 3-р алхам руу очно уу.
3 1. Нөхцөл байдлыг шалгацгаая
4 1. Тогтооцгооё k = 0.
5 2. Нөхцөл байдлыг шалгацгаая
6 2. Тооцоод үзье
7 2. Нөхцөл байдлыг шалгацгаая
8 2. Тогтооцгооё
9 2. Тооцоод үзье
10 2. Нөхцөл байдлыг шалгацгаая 
11 2. Нөхцөл байдлыг шалгацгаая
Бид итгэж байна k =1 5-р алхам руу очно уу.
5 3. Нөхцөл байдлыг шалгацгаая
6 3. Тооцоод үзье
7 3. Нөхцөл байдлыг шалгацгаая
8 3. Тогтооцгооё
9 3. Тооцоод үзье
10 3. Нөхцөл байдлыг шалгацгаая 
11 3. Нөхцөл байдлыг шалгацгаая
Тогтооцгооё k = 2 5-р алхам руу очно уу.
5 4 . Нөхцөл байдлыг шалгацгаая 
Бид итгэж байна j = 2, x 20 = x 12 3-р алхам руу шилжинэ.
3 2. Нөхцөл байдлыг шалгацгаая
4 2. Тогтооцгооё k =0 .
5 4 . Нөхцөл байдлыг шалгацгаая
6 4. Тооцоолъё
7 4. Нөхцөл байдлыг шалгацгаая
8 4. Тогтооцгооё
9 4. Тооцоолъё
10 4. Нөхцөл байдлыг шалгаад 11-р алхам руу шилжье.
11 4. Нөхцөл байдлыг шалгацгаая
Нөхцөлүүдийг тоогоор дараалсан хоёр мөчлөгөөр хангана j = 2 Тэгээд j -1= 1 . Тооцоолол дуусч, цэг олдлоо
Зураг дээр. Үүссэн 6 цэгийг тасархай шугамаар холбосон.
Координатын уналтын аргад бид координатын тэнхлэгтэй параллель шулуун хэрчмүүдээс тогтсон тасархай шугамын дагуу бууна.
II. x21 цэгийн шинжилгээ.
Жишээ 1.1-д функц байгааг харуулсан f(x)
нь хатуу гүдгэр, өвөрмөц минимумтай, тиймээс цэгтэй 
нь дэлхийн хамгийн бага цэгийн олсон ойролцоолол юм.
Дээр дурдсан бүх градиент аргуудад цэгүүдийн дараалал (хк) функцийн суурин цэг рүү нийлдэг f(x) Энэ функцийн шинж чанарын талаархи нэлээд ерөнхий саналуудтай. Ялангуяа теорем нь үнэн юм:
Теорем. Хэрэв f(x) функц нь доор хязгаарлагдсан бол түүний градиент нь Липшицийн нөхцөл () ба утгын сонголтыг хангана. тн дээр дурдсан аргуудын аль нэгээр үйлдвэрлэсэн, дараа нь ямар ч эхлэлийн цэг x 0 :
цагт.
Схемийг практикт хэрэгжүүлэхэд
k =1, 2, … n.
Хэрэв бүх тохиолдолд давталт зогсдог i, i = 1, 2, ..., n , нөхцөл гэх мэт
,
доод хэмжээг олох нарийвчлалыг тодорхойлдог тодорхой тоо хаана байна.
Теоремын нөхцөлд градиент арга нь функцэд эсвэл яг доод хязгаарт нийлэхийг баталгаажуулдаг (хэрэв функц f(x) доод тал байхгүй; будаа. 7), эсвэл дарааллын хязгаар болох ямар нэгэн хөдөлгөөнгүй цэг дэх функцийн утга руу (x k). Энэ үед эмээл хэрэгжсэн жишээг гаргаж ирэх нь тийм ч хэцүү биш бөгөөд хамгийн багадаа биш юм. Практикт градиент буурах аргууд нь эмээлийн цэгүүдийг найдвартай тойрч, зорилгын функцийн минимумыг (ерөнхий тохиолдолд орон нутгийн) олдог.
ДҮГНЭЛТ
Градиент хязгаарлалтгүй оновчлолын аргын жишээг дээр авч үзсэн. Хийсэн ажлын үр дүнд дараахь дүгнэлтийг гаргаж болно.
1. Хязгаарлалттай үед экстремумыг олоход илүү их эсвэл бага төвөгтэй асуудлууд нь тусгай арга барил, аргыг шаарддаг.
2. Хязгаарлагдмал асуудлыг шийдвэрлэх олон алгоритмууд нь хязгаарлалтгүй багасгахыг зарим алхам болгон агуулдаг.
3. Төрөл бүрийн аргабуух чиглэл, энэ чиглэлийн дагуух алхмын уртыг сонгох арга зам нь бие биенээсээ ялгаатай.
4. Асуудлын томъёоллыг тодорхойлсон функцүүдийн онцлогийг харгалзан үзэх онол хараахан алга. Асуудлыг шийдвэрлэх явцад удирдахад хялбар аргуудыг илүүд үзэх хэрэгтэй.
Бодит хэрэглээний оновчлолын асуудлууд нь маш нарийн төвөгтэй байдаг. Орчин үеийн аргуудОновчлол нь хүний тусламжгүйгээр бодит асуудлыг шийдвэрлэхэд үргэлж тусалдаггүй.
НОМ ЗҮЙ
1. Косоруков О.А. Үйл ажиллагааны судалгаа: Сурах бичиг. 2003 он
2. Пантлеев А.В. Жишээ ба асуудлын оновчлолын аргууд: сурах бичиг. Ашиг тус. 2005 он
3. Шишкин Е.В. Үйл ажиллагааны судалгаа: сурах бичиг. 2006 он
4. Акулич И.Л. Жишээ, бодлого дахь математикийн програмчлал. 1986 он
5. Ventzel E.S. Үйл ажиллагааны судалгаа. 1980 он
6. Вентцел Е.С., Овчаров Л.А. Магадлалын онол ба түүний инженерчлэлийн хэрэглээ. 1988 он
©2015-2019 сайт
Бүх эрх нь тэдний зохиогчид хамаарна. Энэ сайт нь зохиогчийн эрхийг шаарддаггүй, гэхдээ хангадаг үнэгүй ашиглах.
Хуудас үүсгэсэн огноо: 2017-07-02
Тэмдэглэл: Энэхүү лекц нь хамгийн эгц буух арга, Давидон-Флетчер-Пауэллийн арга зэрэг олон параметрийн оновчлолын аргуудыг өргөнөөр тусгасан болно. Нэмж дурдахад хамгийн үр дүнтэйг тодорхойлохын тулд дээрх аргуудын харьцуулсан шинжилгээг хийж, тэдгээрийн давуу болон сул талуудыг тодорхойлсон; мөн түүнчлэн жалгын арга, олон талт арга зэрэг олон хэмжээст оновчлолын асуудлыг авч үздэг.
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) |
Та мөн градиентийн чиглэлийн хамгийн сайн цэгийг хайж олохгүй, харин одоогийнхоос илүү сайн цэгийг хайж болно.
Орон нутгийн оновчлолын бүх аргуудыг хэрэгжүүлэхэд хамгийн хялбар. Маш их байна сул нөхцөлнийлэх, гэхдээ нэгдэх хурд нь нэлээд бага (шугаман). Градиент аргын алхамыг ихэвчлэн Флетчер-Ривэсийн арга гэх мэт бусад оновчлолын аргуудын нэг хэсэг болгон ашигладаг.
Тодорхойлолт [ | ]
Сайжруулалт[ | ]
Градиент уруудах арга нь жалгын дагуу хөдөлж байх үед маш удаан байдаг бөгөөд зорилгын функц дэх хувьсагчдын тоо нэмэгдэх тусам аргын энэ зан үйл нь ердийн шинж чанартай болдог. Энэ үзэгдэлтэй тэмцэхийн тулд үүнийг ашигладаг бөгөөд түүний мөн чанар нь маш энгийн байдаг. Градиент уруулын хоёр алхмыг хийж, гурван цэгийг авсны дараа гуу жалгын ёроолын дагуу эхний ба гуравдугаар цэгийг холбосон векторын чиглэлд гурав дахь алхамыг хийх хэрэгтэй.
Квадраттай ойролцоо функцүүдийн хувьд коньюгат градиент арга нь үр дүнтэй байдаг.
Хиймэл мэдрэлийн сүлжээнд хэрэглэх[ | ]
Градиент десантын арга нь зарим өөрчлөлттэй, перцептроныг сургахад өргөн хэрэглэгддэг бөгөөд хиймэл мэдрэлийн сүлжээний онолд буцах тархалтын арга гэж нэрлэгддэг. Перцептрон төрлийн мэдрэлийн сүлжээг сургахдаа сүлжээний жингийн коэффициентийг өөрчлөх шаардлагатай. дундаж алдаасургалтын оролтын өгөгдлийн дарааллыг оролтод нийлүүлэх үед мэдрэлийн сүлжээний гаралт дээр. Албан ёсоор, градиент буурах аргыг ашиглан нэг алхам хийх (сүлжээний параметрүүдэд зөвхөн нэг өөрчлөлт хийх) тулд сургалтын өгөгдлийг бүхэлд нь сүлжээний оролтод дараалан оруулах, объект бүрийн алдааг тооцоолох шаардлагатай. сургалтын өгөгдлийг боловсруулж, сүлжээний коэффициентүүдийн шаардлагатай засварыг тооцоолно (гэхдээ энэ залруулга хийхгүй), бүх өгөгдлийг оруулсны дараа сүлжээний коэффициент тус бүрийн (градиентийн нийлбэр) тохируулгын хэмжээг тооцоолж, "нэг алхам" коэффициентийг залруулна. . Мэдээжийн хэрэг, их хэмжээний сургалтын өгөгдөлтэй бол алгоритм нь маш удаан ажиллах болно, тиймээс практик дээр сүлжээний коэффициентийг сургалтын элемент бүрийн дараа ихэвчлэн тохируулдаг бөгөөд градиент утгыг зөвхөн нэг сургалтаар тооцоолсон зардлын функцын градиентаар ойртуулдаг. бүрэлдэхүүн. Энэ аргыг нэрлэдэг стохастик градиент уналт эсвэл үйл ажиллагааны градиент уналт . Стохастик градиент уналтнь стохастик ойртох хэлбэрүүдийн нэг юм. Стохастик ойртолтын онол нь стохастик градиент удмын аргын нэгдэх нөхцлийг бүрдүүлдэг.
Холбоосууд [ | ]
- Ж.Матьюс.Хамгийн эгц уруудах эсвэл градиент аргын модуль. (боломжгүй холбоос)
Уран зохиол [ | ]
- Акулич I. L.Жишээ, бодлого дахь математикийн програмчлал. - М.: Дээд сургууль, 1986. - P. 298-310.
- Гилл Ф., Мюррей В., Райт М.Практик оновчлол = Практик оновчлол. - М.: Мир, 1985.
- Коршунов Ю.М., Коршунов Ю.М.Кибернетикийн математик үндэс. - М .: Energoatomizdat, 1972.
- Максимов Ю.А., Филлиповская Е.А.Шугаман бус програмчлалын асуудлыг шийдвэрлэх алгоритмууд. - М.: MEPhI, 1982.
- Максимов Ю.А.Шугаман болон дискрет програмчлалын алгоритмууд. - М.: MEPhI, 1980.
- Корн Г., Корн Т.Эрдэмтэн, инженерүүдэд зориулсан математикийн гарын авлага. - М.: Наука, 1970. - P. 575-576.
- С.Ю.Городецкий, В.А.Гришагин.Шугаман бус програмчлал ба олон талт оновчлол. - Нижний Новгород: Нижний Новгородын их сургуулийн хэвлэлийн газар, 2007. - хуудас 357-363.
Давталт бүрт хамгийн эгц буух аргыг хэрэглэх үед алхамын хэмжээ А к функцийн хамгийн бага нөхцлөөс сонгогдоно 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, ... градиентийн утгыг тооцоолно f"(x[к]) .
- 3. Алхам хэмжээ нь тодорхойлогддог а k, нэг хэмжээст багасгах замаар Афункцууд j (а) = f(x[к]-af"(x[к])).
- 4. Цэгийн координатыг тодорхойлно X[k+ 1]:
X би [k+ 1]= x би [к] -А к f" би (X[к]), i = 1,..., х.
5. Стерацийн процессыг зогсоох нөхцөлийг шалгана. Хэрэв тэдгээр нь биелсэн бол тооцоолол зогсох болно. Үгүй бол 1-р алхам руу очно уу.
Харгалзан үзэж буй аргад цэгээс хөдөлгөөний чиглэл X[к] цэг дээрх түвшний шугамд хүрнэ x[k+ 1] (Зураг 2.9). Буух зам нь зигзаг бөгөөд зэргэлдээ зигзаг холбоосууд хоорондоо ортогональ байдаг. Үнэхээр алхам а k-ийг багасгах замаар сонгоно Афункцууд? (а) = f(x[к] -af"(x[к])) . Урьдчилсан нөхцөлхамгийн бага функц г j (a)/da = 0.Нарийн төвөгтэй функцийн деривативыг тооцоолсны дараа бид зэргэлдээх цэгүүд дэх буурах чиглэлийн векторуудын ортогональ байдлын нөхцөлийг олж авна.
г j (a)/da = -f"(x[k+ 1]f"(x[к]) = 0.
Цагаан будаа. 2.9.
Градиент аргууд нь хамгийн багадаа нийлдэг өндөр хурд(хурдтай геометрийн прогресс) гөлгөр гүдгэр функцүүдийн хувьд. Ийм функцууд хамгийн их байдаг Мба хамгийн бага мХоёрдахь деривативын матрицын хувийн утга (Гессийн матриц)
бие биенээсээ бага зэрэг ялгаатай, өөрөөр хэлбэл матриц N(x)сайн нөхцөлтэй. Үүнийг сануулъя хувийн үнэ цэнэби, би =1, …, n, матрицууд нь шинж чанарын тэгшитгэлийн үндэс юм
Гэсэн хэдий ч практикт, дүрмээр бол багасгаж буй функцууд нь хоёр дахь деривативын тохиромжгүй матрицтай байдаг. (т/м<< 1). Зарим чиглэлийн дагуух ийм функцүүдийн утга нь бусад чиглэлээс хамаагүй хурдан (заримдаа хэд хэдэн дарааллаар) өөрчлөгддөг. Тэдний түвшний гадаргуу нь хамгийн энгийн тохиолдолд хүчтэй уртассан (Зураг 2.10), илүү төвөгтэй тохиолдолд нугалж, жалга мэт харагдана. Ийм шинж чанартай функцуудыг нэрлэдэг гуу жалга.Эдгээр функцүүдийн эсрэг градиентийн чиглэл (2.10-р зургийг үз) чиглэлээс хамгийн бага цэг хүртэл ихээхэн хазайдаг бөгөөд энэ нь нэгдэх хурдыг удаашруулахад хүргэдэг.
Цагаан будаа. 2.10.
Градиент аргуудын нэгдэх хурд нь градиент тооцооллын нарийвчлалаас ихээхэн хамаардаг. Ихэвчлэн хамгийн бага цэгүүдийн ойролцоо эсвэл гуу жалганд тохиолддог нарийвчлал алдагдах нь градиент уруудах үйл явцын нэгдлийг тасалдуулж болзошгүй юм. Дээрх шалтгааны улмаас градиент аргуудыг асуудлыг шийдвэрлэх эхний шатанд бусад илүү үр дүнтэй аргуудтай хослуулан ашигладаг. Энэ тохиолдолд гол зүйл Xхамгийн бага цэгээс хол байгаа бөгөөд антиградиентийн чиглэлийн алхамууд нь функцийг мэдэгдэхүйц бууруулах боломжийг олгодог.
