Асуудлын талаархи мэдэгдэл

Функцийг өгье 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<λk < 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 .

3 0 . Тооцоод үзье

4 0 . Тооцоод үзье . 5-р алхам руу шилжье.

5 0 . Нөхцөл байдлыг шалгацгаая . 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 .

3 0 . Тооцоод үзье

4 0 . Тооцоод үзье . 5-р алхам руу шилжье.

5 0 . Нөхцөл байдлыг шалгацгаая . 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.

3 0 . Нөхцөл хангагдсан эсэхийг шалгацгаая

4 0 . Тогтооцгооё k = 0.

5 0 . Нөхцөл хангагдсан эсэхийг шалгацгаая

6 0 . Тооцоод үзье

7 0 . Нөхцөл байдлыг шалгацгаая

8 0 . Тогтооцгооё

9 0 . Тооцоод үзье , Хаана

10 0 . Нөхцөл байдлыг шалгацгаая

Дүгнэлт: бид таамаглаж, 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. Ventzel E.S., Ovcharov L.A. Магадлалын онол ба түүний инженерчлэлийн хэрэглээ. 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), Хаана

Функцийн утгын өөрчлөлтийг харилцаа холбоогоор тодорхойлно

Нэгдүгээр эрэмбийн 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)

Цэг дэх дифференциал болох 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, эсрэгтөрөгчийн чиглэлд хэвтэх - функцийн хамгийн хурдан бууралт. Буух чиглэл болгон сонгох[к r ] эсрэг градиент - 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]

Энд e ба g-г бага хэмжээгээр өгөв. a k f"(x.

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

функц буурах, өөрөөр хэлбэл тэгш бус байдлыг хангах болно к+1]) = f(x f(x[ [k] - 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.

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

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

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

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

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

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

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

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

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

Эхлээд энэ аргыг квадрат функцийг багасгах асуудалтай холбон авч үзье. Буух чиглэл болгон сонгох[кЧиглэл

]-ийг дараах томъёогоор тооцоолно. к] = -- x[к]) p[ -f(x[к+b k-1 к>= 1;

-l], p = -’(эсвэл) .

е к b утгууд -f(x[к], Буух чиглэл болгон сонгох[к-1 чиглэлийг сонгосон байхаар хосолсон-1] байсан :

(-f(x[к], -коньюгат[HP 1])= 0.

к-

,

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

давталттай багасгах үйл явц нь хэлбэртэй байна к f'(x x[[к]=x[к],

Хаана Буух чиглэл болгон сонгох[к] - +a k p HPуруудах чиглэл м алхам;ба к - алхамын хэмжээ. By АСүүлийнх нь функцийн хамгийн бага нөхцлөөс сонгогдоно

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

a k r

ар

Квадрат функцийн хувьд X Fletcher-Reeves коньюгат градиент аргын алгоритм нь дараах байдалтай байна. -f(x = -- x) .

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

к f(x[к+1]) ба хугацаа - x[к+1]) .

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

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

давталттай багасгах үйл явц нь хэлбэртэй байна к f'(x 1) 1-4-р процедурын давталт нь солих замаар мөчлөгөөр давтагдана[к]=x[к],

]-ийг дараах томъёогоор тооцоолно. к] дээр[к])+ +1] ба тооцоолол нь өгөгдсөн тоо хаана байна. Энэ тохиолдолд аргын дараах өөрчлөлтийг ашиглана. HP 1 -f(x[к+b k-1 к>= 1;

= x k+);

функц буурах, өөрөөр хэлбэл тэгш бус байдлыг хангах болно к] + = -f’(x[к]) = f(x[к] б[к];

.

p = -f’( a k p+ap a k pЭнд I- олон индексүүд: N -= (0, n, 2

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

. Дараа нь чигийн дагуу функцийн хамгийн бага утгыг олно N -= (0, n, 2

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

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 болно

Зураг 3. Хамгийн эгц буух аргын геометрийн тайлбар. Алхам бүрт дараагийн давталт нь L туяа дээрх функцийн хамгийн бага цэг байхаар сонгогдоно.

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

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

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

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

Тоон жишээнүүд

Тогтмол алхамтай градиент буурах арга

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

Хүлээн авсан үр дүнгээс харахад хэрэв цоорхой нь хэтэрхий том бол арга нь зөрүүтэй бол энэ нь аажмаар нийлж, нарийвчлал нь муу болно гэж дүгнэж болно. Арга нь нийлж байгаа алхамуудаас хамгийн том алхамыг сонгох шаардлагатай.

Алхам хуваах градиент арга

Алхам хуваах (2) бүхий градиент буурах аргын нийлэлтийг судлахын тулд дараах функцийг сонгосон.

Анхны ойролцоолсон цэг (10,10).

Ашигласан зогсоох шалгуур:

Туршилтын үр дүнг хүснэгтэд үзүүлэв.

Хүлээн авсан үр дүнгээс бид параметрийн оновчтой сонголт нь дараах байдалтай байна гэж дүгнэж болно: Хэдийгээр энэ арга нь параметрийн сонголтод маш мэдрэмтгий биш юм.

Хамгийн огцом буух арга

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

Анхны ойролцоолсон цэг (10,10). Ашигласан зогсоох шалгуур:

Нэг хэмжээст оновчлолын асуудлыг шийдэхийн тулд алтан зүсэлтийн аргыг ашигласан.

Энэ арга нь 9 давталтаар 6e-8 нарийвчлалтай болсон.

Эндээс бид хамгийн эгц уруудах арга нь шатаар хуваах градиент арга болон тогтмол шаталсан градиент уруудах аргаас илүү хурдан нийлдэг гэж дүгнэж болно.

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

Градиент буурах аргуудыг програмчлахдаа параметрүүдийг сонгохдоо болгоомжтой байх хэрэгтэй

• · Тогтмол алхамтай градиент буурах арга: алхмыг 0.01-ээс бага сонгох хэрэгтэй, эс тэгвээс арга нь зөрөх (судлах функцээс хамааран арга нь ийм алхамтай байсан ч зөрөөтэй байж болно).
• · Алхам хуваах градиент арга нь параметрийн сонголтод тийм ч мэдрэмтгий биш юм. Параметрүүдийг сонгох сонголтуудын нэг:
• · Хамгийн эгц буух арга: Алтан харьцааны аргыг (боломжтой бол) нэг хэмжээст оновчлолын арга болгон ашиглаж болно.

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

Оновчлолын асуудлын талаархи мэдэгдэл

Олонлог өгөгдөх ба энэ олонлог дээр зорилгын функц тодорхойлогдоно. Оновчлолын асуудал нь олонлог дээрх зорилгын функцийн яг дээд буюу яг доод хязгаарыг олохоос бүрдэнэ. Зорилгын функцийн доод хязгаарт хүрэх цэгүүдийн багцыг зааж өгсөн болно.

Хэрэв, оновчлолын асуудлыг хязгаарлалтгүй гэж нэрлэдэг. Хэрэв, оновчлолын асуудлыг хязгаарлагдмал гэж нэрлэдэг.

Квадрат функциональд зориулсан коньюгат градиент арга

Аргын тухай мэдэгдэл

Дараах оновчлолын асуудлыг авч үзье.

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

Дараагийн ойртолт бүрийг дараах томъёогоор тооцоолно.

Тодорхойлолт. Хоёр вектор ба тэгш хэмтэй В матрицтай холбоотой коньюгат гэнэ

Коньюгат градиент аргаар суурь байгуулах аргыг тайлбарлая. Давталт бүрт дараах дүрмийг сонгоно.

Үндсэн векторуудыг дараах томъёогоор тооцоолно.

Коэффициентийг Векторууд ба А-тай холбосон байхаар сонгоно.

Хэрэв бид -ээр тэмдэглэвэл хэд хэдэн хялбаршуулсаны дараа коньюгат градиент аргыг практикт хэрэглэхэд ашигласан эцсийн томъёог олж авна.

Коньюгат градиент аргын хувьд дараах теоремыг баримтална: Теорем Let, энд хэмжээ нь тэгш хэмт эерэг тодорхой матриц юм. Дараа нь коньюгат градиент арга нь алхам алхмаар нэгдэх ба дараах харилцааг хангана.

Аргын нэгдэл

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

Энэ нь матрицын хамгийн их ба хамгийн бага хувийн утгуудын тооцооллыг мэддэг бол нийлэх хурдыг тооцоолох боломжийг олгодог. Практикт дараахь зогсоох шалгуурыг ихэвчлэн ашигладаг.

Тооцооллын нарийн төвөгтэй байдал

Аргын давталт бүрт үйлдлүүд хийгддэг. Бүтээгдэхүүнийг тооцоолохын тулд ийм тооны үйлдлүүдийг хийх шаардлагатай байдаг - энэ нь давталт бүрт хамгийн их цаг хугацаа шаардсан журам юм. Бусад тооцоололд O(n) үйлдэл шаардлагатай. Аргын нийт тооцооллын нарийн төвөгтэй байдал нь давталтын тоо n-ээс ихгүй тул давтагдахгүй.

Тоон жишээ

Коньюгат градиент аргыг ашиглан энэ системийн шийдлийг хоёр давталтаар олж авдаг системийг шийдэхийн тулд коньюгат градиент аргыг хэрэглэцгээе. Матрицын хувийн утга нь 5, 5, -5 - тэдгээрийн дунд хоёр өөр байдаг тул онолын тооцоогоор давталтын тоо хоёроос хэтрэхгүй байх ёстой.

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

Ерөнхийдөө коньюгат градиент арга

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

Тасралтгүй ялгах функц. Энэ асуудлыг шийдэхийн тулд коньюгат градиент аргыг өөрчлөхийн тулд А матрицыг оруулаагүй томъёоны хувьд дараахь зүйлийг авах шаардлагатай.

гурван томъёоны аль нэгийг ашиглан тооцоолж болно:

1. - Флетчер-Ривзийн арга

• 2. - Полак-Рибьерийн арга

Хэрэв функц нь квадрат бөгөөд хатуу гүдгэр бол гурван томъёо бүгд ижил үр дүнг өгнө. Хэрэв дурын функц бол томъёо бүр нь коньюгат градиент аргын өөрийн гэсэн өөрчлөлттэй тохирч байна. Гурав дахь томъёог бараг ашигладаггүй, учир нь энэ нь аргын алхам бүрт функц болон функцийн Hessian-ийн тооцоог шаарддаг.

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

Аргын нэгдэл

Флетчер-Ривзийн аргын хувьд багасгаж байгаа функцэд тийм ч хатуу нөхцөл тавьдаггүй нэгдэх теорем байдаг: Теорем. Дараах нөхцлийг хангасан байх ёстой.

Төрөл бүрийн зүйл хязгаарлагдмал

Дериватив нь Липшицийн нөхцлийг зарим хөршийн тогтмол тоогоор хангадаг

багц M: .

Полак-Райберийн аргын хувьд нэгдмэл байдал нь хатуу гүдгэр функц гэсэн таамаглалаар нотлогддог. Ерөнхий тохиолдолд Полак-Рейберийн аргын нэгдмэл байдлыг нотлох боломжгүй юм. Үүний эсрэгээр дараах теорем үнэн болно: Теорем. Полак-Райберийн аргад алхам бүрийн утгыг яг нарийн тооцоолсон гэж үзье. Дараа нь функц, анхны таамаглал байдаг.

Гэсэн хэдий ч практик дээр Полак-Райберийн арга илүү сайн ажилладаг. Практикт хамгийн түгээмэл зогсоох шалгуурууд: Градиент норм нь тодорхой босго хэмжээнээс бага болно. Функцийн утга m дараалсан давталтуудад бараг өөрчлөгдөөгүй хэвээр байна.

Тооцооллын нарийн төвөгтэй байдал

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

Бид коньюгат градиент аргыг ашиглан функцийн хамгийн бага утгыг хайх болно

Энэ функцийн хамгийн бага нь 1 бөгөөд (5, 4) цэг дээр хүрнэ. Энэ функцийг жишээ болгон Полак-Райбер, Флетчер-Ривзийн аргуудыг харьцуулж үзье. Одоогийн алхам дээр градиентийн квадрат норм багасах үед хоёр аргын давталт зогсдог. Сонголт хийхэд алтан харьцааны аргыг ашигладаг

Коньюгат градиент аргын хоёр хувилбарыг хэрэгжүүлсэн: квадрат функцийг багасгах, дурын функцийг багасгах. Эхний тохиолдолд энэ аргыг вектор функцээр гүйцэтгэдэг Шийдвэр олох(матриц А, вектор b) Энд A ба b нь квадрат оновчлолын бодлогыг тодорхойлоход оролцсон матриц ба вектор юм. Дурын функцийг багасгахын тулд та вектор гэсэн хоёр функцийн аль нэгийг ашиглаж болно FletcherRievesMethod(int spaceSize, Function F, вектор (*GradF) (вектор )) вектор PolakRibiereMethod(int spaceSize, функц F, вектор (*GradF) (вектор )) Хоёр функцийн параметрүүд нь ижил бөгөөд дараах утгатай: spaceSize - зайны хэмжээ (багасгасан функцээс хамаарах хувьсагчийн тоо) F - багасгах функцийг заагч. Функц нь double хэлбэртэй байх ёстой<имя функции>(вектор ) GradF - багасгаж буй функцийн градиентийг тооцоолох функцийн заагч. Хоёр арга нь нэг хэмжээст оновчлолын асуудлыг шийдвэрлэхэд туслах функцийг ашигладаг. Хөтөлбөр нь алтан зүсэлтийн аргыг ашиглан нэг хэмжээст оновчлолыг хэрэгжүүлдэг.

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