градиент аргууд. Математикийн оновчлолын бодлого дахь градиент аргуудын тойм

Энэ арга нь томъёоны дараах давталттай өөрчлөлт дээр суурилдаг

x k +1 = x k + a k s(x k),

x k+1 = x k - a k Ñ f(x k), энд

a - өгөгдсөн эерэг коэффициент;

Ñ ​​f(x k) - градиент зорилгын функцэхний захиалга.

Алдаа:

-ийн тохирох утгыг сонгох хэрэгцээ;

Энэ цэгийн ойр орчимд f(x k)-ийн жижиг байдлаас шалтгаалан хамгийн бага цэг хүртэл удаан нийлэх.

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

Хамгийн энгийн анхны согогоос ангид градиент арга, учир нь a k-ийг нэг хэмжээст оновчлолын аргуудын аль нэгийг х k+1 = x k - a k Ñ f(x k) ашиглан Ñ f(x k) чиглэлийн дагуу Ñ f(x k) багасгах бодлогыг бодно.

Энэ аргыг заримдаа Коши арга гэж нэрлэдэг.

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

Холболтын чиглэлийн арга

Хязгаарлалтгүй шугаман бус програмчлалын ерөнхий асуудал нь дараах байдалтай байна: f(x), x E n -ийг багасгах, f(x) нь зорилгын функц юм. Энэ асуудлыг шийдвэрлэхдээ бид f(x *)=0 тэгшитгэлээр тодорхойлогдсон суурин f(x) цэг рүү хөтөлдөг багасгах аргуудыг ашигладаг. Коньюгат чиглэлийн арга нь дериватив ашигладаг хязгааргүй багасгах аргуудыг хэлнэ. Даалгавар: f(x), x E n , энд f(x) нь n бие даасан хувьсагчийн зорилгын функц юм. Чухал онцлогЭнэ нь чиглэлийг сонгохдоо хариу урвалын гадаргуугийн топологийн талбайг дүрсэлсэн Hessian матрицыг ашигладаг тул хурдан нэгдэх явдал юм. Ялангуяа, хэрэв зорилгын функц нь квадрат бол хамгийн бага цэгийг асуудлын хэмжээстэй тэнцүү хэд хэдэн алхамаас илүүгүй хугацаанд авч болно.

Энэ аргыг практикт хэрэгжүүлэхийн тулд чиглэлийн системийн нэгдэл, шугаман бие даасан байдлыг шалгах журамд нэмэлт оруулах шаардлагатай. Хоёрдахь эрэмбийн аргууд

Ньютоны арга

Квадрат ойртуулах схемийг дараалан хэрэглэх нь томъёоны дагуу Ньютоны оновчлолын аргыг хэрэгжүүлэхэд хүргэдэг.

x k +1 = x k - Ñ 2 f(x k -1) Ñ f(x k).

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

x k +1 = x k - a k Ñ 2 f(x k -1) Ñ f(x k), энд

a k нь f(x k+1) мин байхаар сонгосон параметр юм.

2. Хязгаарлалтгүйгээр функцийн экстремумыг олох

Зарим функц f(x) нь х аргументийн өөрчлөлтийн нээлттэй интервал (a, c) дээр өгөгдсөн. Энэ интервал дотор exst байдаг гэж бид таамаглаж байна (ерөнхий тохиолдолд үүнийг математикийн хувьд урьдчилан хэлэх боломжгүй гэж хэлэх ёстой; гэхдээ техникийн хэрэглээнд аргументын хэлбэлзлийн тодорхой интервалд exst байх нь ихэвчлэн тохиолддог. интервалыг физик хүчин зүйлээс урьдчилан таамаглах боломжтой).

Exst-ийн тодорхойлолт. (a, c) интервал дээр өгөгдсөн f (x) функц нь x * max (min) цэг дээр байна, хэрэв энэ цэгийг ийм интервалаар (x * -ε, x * + ε) хүрээлж болох юм бол интервал (a, c) , (x * -ε, x * +ε) интервалд хамаарах түүний бүх x цэгүүдэд дараахь тэгш бус байдал үүснэ.

f(x) ≤ f(x *) → хамгийн их

f(x) ≥ f(x *) → мин

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

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

Фермагийн теорем. f(x) функцийг ямар нэгэн интервалд (a, b) тодорхойлж, энэ интервалын "c" цэгт хамгийн том (хамгийн бага) утгыг авна. Хэрэв энэ үед хоёр талт төгсгөлтэй дериватив байгаа бол exst байх шаардлагатай.

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

* Тохиолдолд min, хэзээ →max. Эцэст нь, хэрэв x=x 0 байвал 2-р деривативыг ашиглах нь тус болохгүй бөгөөд та жишээ нь exst гэсэн тодорхойлолтыг ашиглах хэрэгтэй.

I асуудлыг шийдвэрлэхдээ шаардлагатай нөхцөл exst (өөрөөр хэлбэл Фермагийн теорем) ихэвчлэн ашиглагддаг.

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

Үүнийг бас тэмдэглэе:

-аас шаардлагатай нөхцөлямар төрлийн экстремумыг хамгийн их эсвэл мин гэж хэлэх боломжгүй: үүнийг тодорхойлохын тулд нэмэлт судалгаа хийх шаардлагатай;

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

Тиймээс, exst-ийн сэжигтэй цэгүүд олдвол тэдгээрийг жишээлбэл, exst эсвэл 2-р деривативын тодорхойлолт дээр үндэслэн нэмэлт судалгаа хийдэг.

Лекц 6

Шугаман бус програмчлалын асуудлыг шийдвэрлэх градиент аргууд.

Асуултууд: 1. ерөнхий шинж чанараргууд.

2. Градиент арга.

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

4. Фрэнк-Фулфын арга.

5. Торгуулийн чиг үүргийн арга.

1. Аргуудын ерөнхий шинж чанар.

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

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

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

Градиент аргаар шийдлийг тодорхойлохдоо давтагдах үйл явц нь дараах хүртэл үргэлжилнэ.

Аль ч grad F(x*) = 0, (яг шийдэл);

хаана
- дараалсан хоёр оноо,
нь шийдлийн нарийвчлалыг тодорхойлдог бага тоо юм.

2. Градиент арга.

Доод тал руугаа буух шаардлагатай жалга довны энгэр дээр зогсож байгаа хүнийг төсөөлөөд үз дээ. Хамгийн байгалийн нь хамгийн эгц налуу руу чиглэсэн чиглэл юм шиг санагддаг, өөрөөр хэлбэл. чиглэл (-grad F(x)). Үр дүнд нь стратеги, гэж нэрлэдэг градиент арга, алхам бүр нь хоёр үйлдлийг агуулсан дараалал юм:

а) уруудах (өгсөх) хамгийн их эгц чиглэлийг тодорхойлох;

б) тодорхой алхамаар сонгосон чиглэлд шилжих.

Зөв алхамыг сонгох нь чухал юм. Алхам бага байх тусам үр дүн нь илүү нарийвчлалтай байх болно, гэхдээ илүү их тооцоолол хийх болно. Градиент аргын янз бүрийн өөрчлөлтүүд нь алхамыг тодорхойлох янз бүрийн аргыг ашиглахаас бүрддэг. Хэрэв аль нэг алхам дээр F(x)-ийн утга буураагүй бол энэ нь хамгийн бага цэгийг "алгасан" гэсэн үг бөгөөд энэ тохиолдолд өмнөх цэг рүү буцаж, алхмыг жишээлбэл хагасаар багасгах шаардлагатай болно.

Шийдлийн схем.

зөвшөөрөгдөх бүсэд хамаарах

3. h алхамын сонголт.

x(k+1) = x(k)

"-" - хэрэв мин.

5. F(x (k +1))-ийн тодорхойлолт ба:

Хэрвээ
, шийдэл олдсон;

Сэтгэгдэл.Хэрэв grad F(x (k)) = 0 бол шийдэл нь яг таарна.

Жишээ. F(x) = -6x 1 + 2x 1 2 – 2x 1 x 2 + 2x 2 2
мин,

x1 +x2 2х1 0,x2 0,= 0,1.

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

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

Шийдлийн схем.

1. Тодорхойлолт x 0 \u003d (x 1, x 2, ..., x n),

зөвшөөрөгдсөн бүсэд хамаарах,

ба F(x 0), k = 0.

2. gradF(x 0) эсвэл –gradF(x 0)-ийн тодорхойлолт.

3. h алхамын сонголт.

4. Томъёогоор дараагийн цэгийг тодорхойлох

x(k+1) = x(k) h grad F(x (k)), "+" - хэрэв хамгийн их бол,

"-" - хэрэв мин.

5. F(x (k +1))-ийн тодорхойлолт ба:

Хэрвээ
, шийдэл олдсон;

Хэрвээ биш бол:

a) мин гэж хайхдаа: - хэрэв F(x (k +1))

Хэрэв F(x (k +1)) >F(x (k)) - 2-р алхам руу очно уу;

б) max-ыг хайхдаа: - хэрэв F(x (k +1)) >F(x (k)) - 4-р алхам руу очно уу;

Хэрэв F(x (k + 1))

Тэмдэглэл: 1. Хэрэв grad F(x (k)) = 0 бол шийдэл яг гарна.

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

тооцооны бууралт, учир нь град F(x) бүх цэг дээр тооцоологдоогүй

томоохон хэмжээний асуудалд чухал ач холбогдолтой.

3. Сул тал нь тийм биш байхын тулд шат нь бага байх ёстой

хамгийн оновчтой цэгийг алгасах.

Жишээ. F(x) \u003d 3x 1 - 0.2x 1 2 + x 2 - 0.2x 2 2
хамгийн их,

x 1 + x 2 7х1 0,

x1 + 2x2 10х2 0.

4. Фрэнк-Вольфийн арга.

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

Шийдлийн схем.

1. Тодорхойлолт x 0 = (x 1, x 2,…, x n), зөвшөөрөгдөх бүсэд хамаарах ба F(x 0), k = 0.

2. F(x (k)) зэрэглэлийн тодорхойлолт.

3. Функц бүтээх

(min - "-"; хамгийн их - "+").

4. Анхны хязгаарлалтын дор max(min)f(x)-ийг тодорхойлох. Үүнийг z (k) цэг гэж үзье.

5. Тооцооллын алхамыг тодорхойлох x (k +1) = x (k) + (k) (z (k) –x (k)), хаана (k) – алхам, коэффициент, 0 1. (k) -ийг F(x) функцийн утга x (k +1) цэг дээр max (min) байхаар сонгосон. Үүнийг хийхийн тулд тэгшитгэлийг шийднэ
ба үндэснүүдээс хамгийн жижиг (хамгийн том)-ыг сонгох боловч 0 1.

6. F(x (k +1))-ийг тодорхойлж, цаашдын тооцооллын хэрэгцээг шалгана уу:

Хэрвээ
эсвэл grad F(x (k + 1)) = 0, дараа нь шийдэл олно;

Үгүй бол 2-р алхам руу очно уу.

Жишээ. F(x) = 4x 1 + 10x 2 –x 1 2 –x 2 2
хамгийн их,

x1 +x2 4х1 0,

x2 2х2 0.

5. Торгуулийн чиг үүргийн арга.

F(x 1 ,x 2 ,…,x n)-ийг олох шаардлагатай байг.
хамгийн их (мин),

g i (x 1 , x 2 ,…,x n) b i , i =
, xj 0, j = .

F ба g i функцууд нь гүдгэр эсвэл хотгор юм.

Торгуулийн функцийн аргын санаа нь шинэ зорилгын Q(x) = F(x) + H(x) -ийн оновчтой утгыг олох явдал бөгөөд энэ нь анхны зорилгын функц ба H(x) зарим функцийн нийлбэр юм. ) хязгаарлалтын системээр тодорхойлогдох ба торгуулийн функц гэж нэрлэдэг. Торгуулийн чиг үүргийг зөвшөөрөгдсөн бүс рүү хурдан буцаах, эсвэл тэндээс гарах боломжгүй болгох үүднээс барьсан. Торгуулийн функцын арга нь нөхцөлт экстремумын асуудлыг болзолгүй экстремумын дараалсан асуудлыг шийдвэрлэхэд багасгадаг бөгөөд энэ нь илүү хялбар байдаг. Торгуулийн функцийг бий болгох олон арга бий. Ихэнхдээ иймэрхүү харагддаг:

H(x) =
,

хаана

- зарим эерэг Const.

Анхаарна уу:

Илүү бага , шийдлийг хурдан олох тусам нарийвчлал буурдаг;

Уусмалыг бага багаар эхлүүл дараагийн алхмуудад тэдгээрийг нэмэгдүүлэх.

Торгуулийн функцийг ашиглан нэг цэгээс нөгөө цэг рүү дараалан шилжиж, хүлээн зөвшөөрөгдөх шийдэлд хүрнэ.

Шийдлийн схем.

1. Эхлэх цэгийг тодорхойлох x 0 \u003d (x 1, x 2, ..., x n), F (x 0) ба k \u003d 0.

2. Тооцооллын алхамыг h сонгоно уу.

3. Хэсэгчилсэн деривативыг тодорхойлно уу болон .

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

x j (k+1)
.

5. Хэрэв x (k+1) бол Хүчинтэй бүс, шалгана уу:

Хэрвээ
- шийдэл олдсон, үгүй ​​бол 2-р алхам руу орно.

б) хэрвээ град F(x (k + 1)) = 0 бол яг шийдлийг олно.

Хэрэв x(k+1) Хүчинтэй талбар, шинэ утгыг тохируулна уу 4-р алхам руу очно уу.

Жишээ. F(x) = – x 1 2 – x 2 2
хамгийн их,

(x 1 -5) 2 + (x 2 -5) 2 8х1 0,x2 0.

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

Алхам сонгох янз бүрийн арга байдаг бөгөөд тус бүр нь градиент аргын тодорхой хувилбарыг тодорхойлдог.

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

Нэг скаляр хувьсагчийн функцийг авч үзээд тэнцүү байх утгыг сонго

1845 онд О.Кошигийн санал болгосон энэ аргыг одоо хамгийн эгц буух арга гэж нэрлэдэг.

Зураг дээр. 10.5-д хоёр хувьсагчийн функцийг багасгах энэ аргын геометрийн дүрслэлийг үзүүлэв. Чиглэл дэх түвшний шугамд перпендикуляр байх эхлэлийн цэгээс туяа дагуух функцын хамгийн бага утгад хүрэх хүртэл буултыг үргэлжлүүлнэ. Олдсон цэг дээр энэ туяа түвшингийн шугамд хүрнэ.Дараа нь тухайн цэгээс тухайн цэгийн энэ цэгийг дайран өнгөрч буй түвшний шугамд харгалзах цацраг хүрэх хүртэл түвшний шугамд перпендикуляр чиглэлд буулт хийнэ.

Давталт бүрт алхамыг сонгох нь нэг хэмжээст багасгах асуудлыг шийдэхийг хэлнэ (10.23). Заримдаа энэ үйлдлийг аналитик аргаар, жишээлбэл, квадрат функцийн хувьд хийж болно.

Квадрат функцийг багасгахын тулд бид хамгийн эгц буух аргыг хэрэглэдэг

тэгш хэмт эерэг тодорхой матрицтай А.

(10.8) томъёоны дагуу энэ тохиолдолд (10.22) томъёо дараах байдалтай байна.

анзаараарай, тэр

Энэ функц нь a параметрийн квадрат функц бөгөөд ийм утгад хамгийн багадаа хүрдэг

Тиймээс квадратыг багасгахад ашигладаг

функц (10.24), хамгийн эгц буух арга нь (10.25) томъёогоор тооцоолсонтой тэнцүү байна.

Тайлбар 1. Функцийн хамгийн бага цэг (10.24) нь системийн шийдэлтэй давхцаж байгаа тул хамгийн эгц буух аргыг (10.25), (10.26) тэгш хэмтэй эерэг шугаман алгебрийн тэгшитгэлийн системийг давтах арга болгон ашиглаж болно. тодорхой матрицууд.

Тайлбар 2. Рэйлийн хамаарал хаана байгааг анхаарна уу (§ 8.1-ийг үзнэ үү).

Жишээ 10.1. Квадрат функцийг багасгахын тулд бид хамгийн эгц буух аргыг хэрэглэдэг

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

Бид анхны ойролцоо тооцоог авч, (10.25), (10.26) томъёог ашиглан тооцооллыг хийнэ.

Би давталт.

II давталт.

Давталтын үед бүх утгыг олж авах болно гэдгийг харуулж болно

Ингэснээр,

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

Зураг дээр. 10.5 нь энэ жишээн дээр олж авсан буух замыг яг харуулж байна.

Квадрат функцийг багасгах тохиолдолд дараах ерөнхий үр дүн гарна.

Теорем 10.1. А тэгш хэмт эерэг тодорхой матриц байж, квадрат функцийг (10.24) багасгая. Дараа нь анхны ойролцоолсон аль ч сонголтын хувьд хамгийн эгц буух арга (10.25), (10.26) нийлж, дараах алдааны тооцоо үнэн болно.

Энд болон Ладо нь А матрицын хамгийн бага ба хамгийн их хувийн утга юм.

Энэ арга нь геометрийн прогрессийн хурдаар нийлдэг гэдгийг анхаарна уу, хуваагч нь ойролцоо байвал энэ нь бага бөгөөд арга нь маш хурдан нийлдэг. Жишээ нь, жишээ 10.1-д бид байна, тиймээс, Хэрэв Asch, дараа нь 1, мөн бид хамгийн эгц буух арга аажмаар нийлнэ гэж хүлээх ёстой.

Жишээ 10.2. Анхны ойролцоолсон үед квадрат функцийг багасгахын тулд хамгийн эгц буух аргыг хэрэглэх нь ойролцоогоор өгөгдсөн дарааллыг өгдөг. 10.6.

Дараалал нь геометр прогрессийн хурдаар нийлдэг бөгөөд хуваагч нь, өөрөөр хэлбэл, хамаагүй удаан,

өмнөх жишээнээс илүү. Эндээс авсан үр дүн нь тооцоололтой (10.27) бүрэн тохирч байна.

Тайлбар 1. Зорилгын функц квадрат байх тохиолдолд хамгийн эгц буух аргын нийлбэрийн тухай теоремыг томъёолсон. Ерөнхий тохиолдолд, хэрэв багасгаж буй функц нь хатуу гүдгэр бөгөөд хамгийн бага х цэгтэй бол анхны ойролцоолсон сонголтоос үл хамааран энэ аргаар олж авсан дараалал нь x дээр нийлдэг. Энэ тохиолдолд хамгийн бага цэгийн хангалттай жижиг хороололд орсны дараа нийлэлт нь шугаман болж, харгалзах геометрийн прогрессийн хуваагчийг Hessian матрицын утга ба хаана, хамгийн бага ба хамгийн их хувийн утгуудаар дээрээс нь тооцоолно.

Тайлбар 2. Квадрат зорилгын функцийн хувьд (10.24) нэг хэмжээст багасгах бодлогын шийдлийг (10.23) энгийн тодорхой томьёо (10.26) хэлбэрээр олж болно. Гэсэн хэдий ч бусад ихэнх шугаман бус функцүүдийн хувьд үүнийг хийх боломжгүй бөгөөд хамгийн огцом уналтын тооцооллын хувьд өмнөх бүлэгт авч үзсэн шиг нэг хэмжээст багасгах тоон аргуудыг ашиглах шаардлагатай болдог.

2. " Жалга довны" асуудал.

Дээрх хэлэлцүүлгээс харахад багасгасан функцийн түвшний гадаргуу нь бөмбөрцөгт ойрхон байвал (түвшингийн шугамууд тойрогтой ойрхон байвал) градиент арга нь нэлээд хурдан нийлдэг. Ийм функцүүдийн хувьд болон 1. Теорем 10.1, Тайлбар 1, жишээ 10.2-ын үр дүн нь нийлбэрийн хурд нь -ийн утгын хувьд огцом буурч байгааг харуулж байна. Хоёр хэмжээст тохиолдолд харгалзах гадаргуугийн рельеф нь жалга бүхий газар нутагтай төстэй байдаг (Зураг 10.7). Тиймээс ийм функцийг ихэвчлэн жалга гэж нэрлэдэг. "Жалгийн ёроол"-ыг тодорхойлсон чиглэлүүдийн дагуу жалгын функц нь бага зэрэг өөрчлөгддөг бол "жалгын налуу"-ыг тодорхойлсон бусад чиглэлд үйл ажиллагааны огцом өөрчлөлт гардаг.

Хэрэв эхлэлийн цэг нь "жалганы налуу" дээр унасан бол градиент уруудах чиглэл нь "жалганы ёроол" -д бараг перпендикуляр болж хувирдаг бөгөөд дараагийн ойролцоолсон "жалганы налуу" дээр унадаг. " Жалга довны ёроол " руу чиглэсэн дараагийн алхам нь анхны "жалганы налуу" руу хандах хандлагыг буцаана. Үүний үр дүнд "жалганы ёроол" дагуу хамгийн бага цэг рүү шилжихийн оронд буух зам нь "жалга" дээгүүр зигзаг үсрэлт хийж, зорилтот түвшинд бараг ойртохгүй (Зураг 10.7).

Градиент аргын нэгдлийг хурдасгахын тулд жалгын функцийг багасгахын тулд хэд хэдэн тусгай "жалга" аргыг боловсруулсан. Хамгийн энгийн аргуудын талаар санаа өгье. Хоёр ойрхон эхлэлийн цэгээс "жалгын ёроол" руу градиент буулт хийдэг. Олдсон цэгүүдээр шулуун шугамыг зурж, түүний дагуу том "жалга" алхам хийдэг (Зураг 10.8). Ингэж олсон цэгээс цэг хүртэл градиент уруулын нэг алхмыг дахин авч, дараа нь цэгүүдийг дайран өнгөрөх шулуун шугамын дагуу хоёр дахь "жалга" алхмыг хийнэ. Үүний үр дүнд "жалганы ёроол" дагуух хамгийн бага цэг хүртэл хөдөлгөөн ихээхэн хурдасдаг.

" Жалга гуу жалга " ба "жалга" аргын асуудлын талаархи дэлгэрэнгүй мэдээллийг жишээлбэл, , -ээс олж болно.

3. Буух алхамыг тодорхойлох бусад аргууд.

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

Та мөн градиентийн чиглэлд хамгийн сайн цэгийг хайж олохгүй, харин одоогийнхоос илүү сайн зүйлийг хайж болно.

Орон нутгийн оновчлолын бүх аргуудыг хэрэгжүүлэхэд хамгийн хялбар. Энэ нь нилээд сул нийлэх нөхцөлтэй боловч нэгдэх хурд нь харьцангуй бага (шугаман) юм. Алхам градиент аргыг ихэвчлэн Fletcher-Reeves арга гэх мэт бусад оновчлолын аргуудын нэг хэсэг болгон ашигладаг.

Тодорхойлолт [ | ]

Сайжруулалт[ | ]

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

Квадраттай ойролцоо функцүүдийн хувьд коньюгат градиент арга нь үр дүнтэй байдаг.

Хиймэл мэдрэлийн сүлжээнд хэрэглэх[ | ]

Перцептроныг сургахад зарим нэг өөрчлөлттэй градиентийн уналтын аргыг өргөн ашигладаг бөгөөд хиймэл мэдрэлийн сүлжээний онолд буцааж тархалтын арга гэж нэрлэдэг. Перцептрон төрлийн мэдрэлийн сүлжээг сургахдаа сургалтын оролтын өгөгдлийн дарааллыг оролт руу оруулах үед мэдрэлийн сүлжээний гаралтын дундаж алдааг багасгахын тулд сүлжээний жингийн коэффициентийг өөрчлөх шаардлагатай. . Албан ёсоор, градиент буурах аргын дагуу зөвхөн нэг алхам хийх (сүлжээний параметрүүдэд зөвхөн нэг өөрчлөлт хийх) тулд сургалтын бүх багц мэдээллийг сүлжээний оролт руу дараалан оруулах, сургалтын өгөгдөл бүрийн алдааг тооцоолох шаардлагатай. Сүлжээний коэффициентүүдийн шаардлагатай засварыг тооцоолж (гэхдээ энэ залруулгыг хийхгүй), бүх өгөгдлийг оруулсны дараа сүлжээний коэффициент тус бүрийн залруулгын нийлбэрийг (градиентийн нийлбэр) тооцоолж, коэффициентийг "нэг алхамаар" залруулна. . Мэдээжийн хэрэг, олон тооны сургалтын өгөгдөлтэй бол алгоритм нь маш удаан ажиллах тул практик дээр сүлжээний коэффициентийг сургалтын элемент бүрийн дараа тохируулдаг бөгөөд энд градиент утгыг зөвхөн нэг дээр тооцсон зардлын функцийн градиентаар ойртуулдаг. сургалтын элемент. Ийм аргыг нэрлэдэг стохастик градиент уналт эсвэл үйл ажиллагааны градиент уналт . Стохастик градиентийн уналт нь стохастик ойртох хэлбэр юм. Стохастик ойртолтын онол нь стохастик градиент удмын аргын нэгдэх нөхцлийг бүрдүүлдэг.

Холбоосууд [ | ]

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

Уран зохиол [ | ]

• Акулич I. L.Жишээ, даалгаварт математикийн програмчлал. - М.: Дээд сургууль, 1986. - S. 298-310.
• Гилл Ф., Мюррей В., Райт М.Практик оновчлол = Практик оновчлол. - М.: Мир, 1985.
• Коршунов Ю.М., Коршунов Ю.М.Кибернетикийн математик үндэс. - М .: Energoatomizdat, 1972.
• Максимов Ю.А., Филипповская Е.А.Шугаман бус програмчлалын асуудлыг шийдвэрлэх алгоритмууд. - М.: MEPhI, 1982.
• Максимов Ю.А.Шугаман болон дискрет програмчлалын алгоритмууд. - М.: MEPhI, 1980.
• Корн Г., Корн Т.Эрдэмтэн, инженерүүдэд зориулсан математикийн гарын авлага. - М.: Наука, 1970. - S. 575-576.
• С.Ю.Городецкий, В.А.Гришагин.Шугаман бус програмчлал ба олон экстремаль оновчлол. - Нижний Новгород: Нижний Новгород их сургуулийн хэвлэл, 2007. - S. 357-363.

Лекц No8

Шугаман бус програмчлалын асуудлыг шийдвэрлэх градиент аргууд. Торгуулийн чиг үүргийн аргууд. Үйл ажиллагааны судалгааны асуудалд шугаман бус програмчлалын хэрэглээ.

Хязгааргүй даалгавар.Ерөнхийдөө шугаман бус аливаа асуудлыг градиент аргаар шийдэж болно. Гэхдээ энэ тохиолдолд зөвхөн орон нутгийн экстремум олддог. Тиймээс аливаа локал экстремум нь глобал шинж чанартай байдаг гүдгэр програмчлалын асуудлыг шийдвэрлэхэд энэ аргыг хэрэглэх нь илүү тохиромжтой (Теорем 7.6-г үзнэ үү).

Шугаман бус дифференциалагдах функцийг хамгийн их болгох асуудлыг авч үзэх болно е(x). Хамгийн их цэгийг хайж олох градиентийн мөн чанар X* маш энгийн: та дур зоргоороо цэг авах хэрэгтэй X 0 ба энэ цэг дээр тооцоолсон градиентийг ашиглан аль чиглэлийг тодорхойлно е(X) хамгийн их хэмжээгээр нэмэгддэг (Зураг 7.4),

дараа нь олсон чиглэлд бага зэрэг алхам хийж, шинэ цэг рүү оч x i. Дараа нь дараагийн цэг рүү очих хамгийн сайн чиглэлийг дахин тодорхойлно X 2 гэх мэт. Зураг дээр. 7.4 хайлтын зам нь тасархай шугам юм X 0 , x 1 , X 2 ... Тиймээс цэгүүдийн дарааллыг бий болгох шаардлагатай X 0 , x 1 , X 2 ,...,x k , ... ингэснээр хамгийн дээд цэгт нийлнэ X*, өөрөөр хэлбэл, дарааллын цэгүүдийн хувьд нөхцөл

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

Нэг цэгээс хөдөлгөөн х кшинэ цэг рүү xk+1цэгийг дайран өнгөрөх шулуун шугамын дагуу гүйцэтгэнэ х кба тэгшитгэлтэй байна

(7.29)

Энд λ k нь алхамын хэмжээнээс хамаарах тоон үзүүлэлт юм. (7.29) тэгшитгэлийн параметрийн утгыг сонгонгуут: λ k =λ k 0, хайлтын олон шугамын дараагийн цэг тодорхойлогдоно.

Градиент аргууд нь алхамын хэмжээг сонгох замаар бие биенээсээ ялгаатай байдаг - λ k параметрийн λ k 0 утга. Жишээлбэл, λ k = λ тогтмол алхамаар нэг цэгээс цэг рүү шилжих боломжтой, өөрөөр хэлбэл ямар ч тохиолдолд. к

Хэрэв энэ нь тогтоогдвол , дараа нь та цэг рүү буцаж очоод параметрийн утгыг багасгах хэрэгтэй, жишээлбэл, to λ /2.

Заримдаа алхамын хэмжээг градиентийн модультай пропорциональ авдаг.

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

Хэрэв зорилгын функц е(x) нь хотгор (гүдгэр), дараа нь цэгийн оновчтой байх шаардлагатай бөгөөд хангалттай нөхцөл юм X* нь тухайн цэг дэх функцийн тэг градиент юм.

Градиент хайлтын нийтлэг хувилбарыг хамгийн эгц өгсөх арга гэж нэрлэдэг. Үүний мөн чанар нь дараах байдалтай байна. Нэг цэгийн градиентыг тодорхойлсны дараа х кшулуун шугамын дагуу хөдөлгөөн хийх цэг хүртэл үйлдвэрлэсэн x k+ 1 , функцийн хамгийн их утгад хүрсэн байна е(X) градиентийн чиглэлд. Дараа нь энэ цэг дээр градиентийг дахин тодорхойлж, хөдөлгөөнийг шинэ градиентийн чиглэлд шулуун шугамаар цэг рүү хийнэ. x k+ 2 , энэ чиглэлд хамгийн их утгад хүрсэн газар е(x). Хөдөлгөөн нь цэг хүрэх хүртэл үргэлжилнэ. X* зорилгын функцийн хамгийн том утгатай харгалзах е(x). Зураг дээр. 7.5 нь оновчтой цэг хүртэлх хөдөлгөөний схемийг харуулав X* хамгийн хурдан өсөлтийн арга. Энэ тохиолдолд цэг дээрх градиентийн чиглэл х кгадаргуугийн түвшний шугамд шүргэгч байна е(X) цэг дээр x k+ 1, тиймээс цэг дээрх градиент x k+ 1 нь градиент руу ортогональ байна (Зураг 7.4-тэй харьцуулна уу).

Нэг цэгээс хөдөлж байна х кцэг хүртэл функцын өсөлт дагалддаг е(x) утгаараа

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

(7.31)

(7.30) тэгш байдлыг нийлмэл функцээр ялгах замаар деривативын илэрхийллийг олцгооё.

Энэ үр дүнг тэгш байдал (7.31) болгон орлуулснаар бид олж авна

Энэ тэгш байдал нь энгийн геометрийн тайлбартай: дараагийн цэг дэх градиент x k+ 1 , өмнөх цэгийн градиент руу ортогональ х к.

энэ гадаргуугийн түвшний шугамууд баригдсан. Энэ зорилгоор тэгшитгэлийг хэлбэрт оруулав ( x 1 -1) 2 + (x 2 -2) 2 \u003d 5-0.5 е, үүнээс параболоидын огтлолцлын шугамууд нь хавтгайтай параллель байгаа нь тодорхой байна. x 1 О x 2 (түвшний шугам) нь радиустай тойрог юм. At е=-150, -100, -50 тэдгээрийн радиус тус тус тэнцүү байна , нийтлэг төв нь (1; 2) цэг дээр байна. Энэ функцийн градиентийг ол:

Би алхлаа. Бид тооцоолно:

Зураг дээр. 7.6 цэг дээр гарал үүсэлтэй X 0 =(5; 10) 1/16 векторыг байгуулж, цэг дээрх функцийн хамгийн хурдан өсөх чиглэлийг заана. X 0 . Дараагийн цэг нь энэ чиглэлд байрладаг. Энэ үед .

(7.32) нөхцөлийг ашиглан бид олж авна

эсвэл 1-4=0, үүнээс =1/4. -ээс хойш олсон утга нь хамгийн их цэг болно. Бид олдог x 1 =(5-16/4; 10-32/4)=(1; 2).

II алхам. Хоёр дахь алхамын эхлэх цэг x 1 =(1; 2). =(-4∙1 +4; -4∙2+8)=(0; 0)-ийг тооцоол. Үүний үр дүнд, X 1 =(1; 2) нь хөдөлгөөнгүй цэг юм. Гэхдээ энэ функц нь хотгор тул олсон цэг дээр (1; 2) дэлхийн дээд хэмжээнд хүрнэ.

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

Шугаман хязгаарлалттай гүдгэр програмчлалын бодлогыг авч үзье.

(7.34)

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

Асуудлыг шийдвэрлэх үйл явцын геометрийн дүрслэлээр эхэлцгээе (Зураг 7.7). Эхлэх цэгээ өгье X 0 нь зөвшөөрөгдсөн талбайн дотор байрладаг. Нэг цэгээс X 0 хүртэл та градиентийн чиглэлд шилжиж болно е(x) дээд хэмжээнд хүрэхгүй. Манай тохиолдолд е(x) байнга нэмэгддэг тул та цэг дээр зогсох хэрэгтэй X, хилийн шугам дээр. Зураг дээрээс харахад бид зөвшөөрөгдөх талбайг орхих тул градиентийн чиглэлд цааш явах боломжгүй юм. Тиймээс, нэг талаас зөвшөөрөгдсөн бүсээс гарахгүй, нөгөө талаас хамгийн их өсөлтийг хангах хөдөлгөөний өөр чиглэлийг олох шаардлагатай байна. е(x). Ийм чиглэл нь тухайн цэгээс гарч буй бусад вектортой харьцуулахад вектортой хамгийн бага хурц өнцөг үүсгэх векторыг тодорхойлно. x iмөн зөвшөөрөгдөх бүсэд хэвтэж байна. Аналитик байдлаар ийм векторыг скаляр үржвэрийг ихэсгэх нөхцлөөс олж болно . Энэ тохиолдолд хамгийн ашигтай чиглэлийг харуулсан вектор нь хилийн шугамтай давхцдаг.

Тиймээс дараагийн алхамд хүртэл хилийн шугамын дагуу шилжих шаардлагатай байна е(x); бидний тохиолдолд - цэг хүртэл X 2. Скаляр үржвэрийг ихэсгэх нөхцлөөс олдсон векторын чиглэлд цаашаа шилжих ёстойг зургаас харж болно. , өөрөөр хэлбэл, хилийн шугамын дагуу. Хөдөлгөөн нь нэг цэг дээр дуусдаг X 3 , оновчлолын хайлт энэ үед дуусдаг тул функцээс хойш е(X) орон нутгийн дээд талтай. Энэ үед хонхорхойн улмаас е(X) мөн зөвшөөрөгдөх бүс нутагт дэлхийн дээд хэмжээнд хүрдэг. хамгийн дээд цэгт градиент X 3 =X* дайран өнгөрөх хүчинтэй мужаас дурын вектортой мохоо өнцөг үүсгэнэ x 3, тэгэхээр цэгийн үржвэр нь ямар ч хүчинтэй үед сөрөг байх болно rk, Түүнээс гадна r 3 хилийн шугамын дагуу чиглэсэн. Үүний хувьд скаляр үржвэр = 0, учир нь ба харилцан перпендикуляр байдаг (хилийн шугам нь гадаргуугийн түвшний шугамд хүрдэг. е(X) хамгийн их цэгээр дамжин өнгөрөх X*). Энэ тэгш байдал нь тухайн цэгт аналитик шинж тэмдэг болдог X 3 функц е(x) дээд цэгтээ хүрсэн.

Одоо асуудлын аналитик шийдлийг авч үзье (7.33) - (7.35). Хэрэв оновчлолын хайлт нь зөвшөөрөгдөх бүсэд байрлах цэгээс эхэлбэл (асуудлын бүх хязгаарлалтыг хатуу тэгш бус байдлаар хангасан) дээр дурдсанчлан градиентийн чиглэлд шилжих хэрэгтэй. Гэсэн хэдий ч одоо сонголт λk(7.29) тэгшитгэлийн хувьд дараагийн цэг нь зөвшөөрөгдөх талбайд үлдэх шаардлагаар төвөгтэй байдаг. Энэ нь түүний координатууд нь (7.34), (7.35) хязгаарлалтуудыг хангасан байх ёстой, өөрөөр хэлбэл тэгш бус байдлыг хангасан байх ёстой гэсэн үг юм.

(7.36)

Шугаман тэгш бус байдлын системийг (7.36) шийдэж, параметрийн зөвшөөрөгдөх утгын сегментийг олно. λk, түүний доор x k +1 цэг нь зөвшөөрөгдөх бүсэд хамаарна.

Утга λ к *(7.32) тэгшитгэлийг шийдсэний үр дүнд тодорхойлогддог.

Аль нь е(x) нь орон нутгийн дээд хязгаартай байна λkчиглэл нь сегментэд хамаарах ёстой. Хэрэв үнэ цэнэ нь олдвол λkзаасан сегментээс цааш, дараа нь зэрэг λ к *хүлээн авдаг. Энэ тохиолдолд хайлтын траекторийн дараагийн цэг нь системийн тэгш бус байдалд (7.36) тохирох хилийн гиперплан дээр байх бөгөөд үүний дагуу системийг шийдвэрлэх үед зөв төгсгөлийн цэгийг олж авсан болно. зөвшөөрөгдөх параметрийн утгуудын интервал λk.

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

хязгаарлалт дор

тэдний хувьд т, аль үед

хаана .

(7.37) - (7.40) асуудлыг шийдсэний үр дүнд градиенттай хамгийн бага хурц өнцөг үүсгэх вектор олдоно.

Нөхцөл (7.39) нь тухайн цэг нь зөвшөөрөгдөх бүсийн хилд хамаарах бөгөөд нөхцөл (7.38) нь векторын дагуух шилжилт нь зөвшөөрөгдөх бүс дотор эсвэл түүний хилийн дагуу чиглэнэ гэсэн үг юм. (7.40) -ын утгыг хязгаарлахад шаардлагатай бөгөөд өөрөөр хэлбэл зорилгын функцийн утгыг (7.37) дур зоргоороо томруулж болно. Нормчиллын нөхцлийн янз бүрийн хэлбэрүүд байдаг бөгөөд үүнээс хамаарч (7.37) - (7.40) асуудал гардаг. ) шугаман болон шугаман бус байж болно.

Чиглэлийг тодорхойлсны дараа утгыг олно λ к *дараагийн цэгийн хувьд хайлтын зам. Энэ тохиолдолд шаардлагатай экстремум нөхцөлийг тэгшитгэл (7.32) -тай төстэй хэлбэрээр ашигладаг, гэхдээ векторыг орлуулах замаар, өөрөөр хэлбэл.

(7.41)

Оновчлолын хайлт цэг хүрэх үед зогсдог x k *, үүнд .

Жишээ 7.5.Хязгаарлагдмал дор функцийг нэмэгдүүлэх

Шийдэл.Оновчлолын үйл явцыг дүрслэн харуулахын тулд бид үүнийг график дүрслэлээр дагалдах болно. Зураг 7.8-д өгөгдсөн гадаргуугийн хэд хэдэн түвшний шугамууд ба цэгийг олох боломжтой OABS-ийн зөвшөөрөгдөх талбайг харуулав. X* энэ функцийн дээд хэмжээг өгдөг (жишээ 7 4-ийг үзнэ үү).

Оновчлолын хайлтыг жишээ нь цэгээс эхлүүлье X 0 =(4, 2,5) AB хилийн шугам дээр хэвтэж байна x 1 +4x 2=14. Хаана е(X 0)=4,55.

Градиентийн утгыг ол

цэг дээр x 0 . Нэмж дурдахад, түүнээс дээш тэмдэгтэй шугамыг тэгшлэхийг зурагнаас харж болно е(x 0)=4.55. Нэг үгээр хэлбэл, та зүг чиг хайх хэрэгтэй r 0 =(r 01 , r 02) дараагийн цэг рүү шилжих x 1 оновчтой байдалд ойртлоо. Үүний тулд бид хязгаарлалтын дор функцийг нэмэгдүүлэх (7.37) - (7.40) асуудлыг шийддэг.

Гол цэгээс хойш X 0 нь зөвхөн нэг (эхний) хилийн шугам дээр байрладаг ( би=1) x 1 +4x 2 =14, тэгвэл (7.38) нөхцөлийг тэгш байдлын хэлбэрээр бичнэ.

Энэ асуудлын хязгаарлагдмал тэгшитгэлийн систем нь зөвхөн хоёр шийдэлтэй (-0.9700; 0.2425) ба (0.9700; -0.2425) функцэд шууд орлуулах замаар. Т 0-ийг дээд хэмжээнд нь тохируулсан Т 0 нь тэг биш бөгөөд үүнийг шийдвэрлэх замаар (-0.9700; 0.2425) хүрнэ. XВекторын чиглэлд 0 хэрэгтэй r 0 \u003d (0.9700; 0.2425), өөрөөр хэлбэл BA хилийн шугамын дагуу.

Дараагийн цэгийн координатыг тодорхойлох x 1 =(x 11 ; x 12)

(7.42)

функц байгаа параметрийн утгыг олох шаардлагатай е(x) цэг дээр x

эндээс =2.0618. Үүний зэрэгцээ = -0.3999<0. Значит,=2,0618. По формуле (7.42) находим координаты новой точки х 1 (2; 3).

Хэрэв бид оновчлолын хайлтыг үргэлжлүүлбэл дараагийн туслах бодлогыг (7.37) - (7.40) шийдвэрлэх үед Т 1 = болохыг олж мэдэх болно. , энэ нь x 1 цэг нь зөвшөөрөгдөх муж дахь зорилгын функцийн хамгийн их цэг x* гэсэн үг юм. Нэг түвшний шугам нь зөвшөөрөгдөх талбайн хил дээр хүрч байгаа x 1 цэг дээрх зургаас мөн адил зүйлийг харж болно. Тиймээс x 1 цэг нь хамгийн их х* цэг юм. Хаана ехамгийн их = е(x*)=5,4.

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

хилийн ойролцоо болон зөвшөөрөгдсөн талбайн дотор байрлах цэгүүдийн дарааллыг бий болгох, эсвэл хилийн боомтоор дамжих зигзаг хөдөлгөөнийг хангах хөдөлгөөний арга. Зургаас харахад x 1 цэгээс зөвшөөрөгдөх талбай руу буцах нь зөрчигдсөн хилийн функцын градиентийн дагуу хийгдэх ёстой. Энэ нь дараагийн x 2 цэг нь экстремум x* цэг рүү хазайхыг баталгаажуулна. Ийм тохиолдолд экстремумын тэмдэг нь векторуудын коллинеар байх болно.