Өзбекстан республикасы жоқары ҳӘм орта арнаўлы билимлендириў министрлиги

Теорема 1 Мейли 1)-3) шәртлери орынлы болсын, онда туўры ҳәм қосарлы мәселелериниң оптимал шешимлери көплиги бос емес, оның менен бирге бул мәселелердиң мақсет функцияларының оптимал мәнислери бир-бирине сәйкес келеди.
Теорема 2 Мейли 1)-8) шәртлер орынлы болсын. Онда Лагранж функционалының еркли точкасы бар болады.
Соның менен бирге қәлеген жуп шешим -функционалға ерлик точкасын дүзеди.
ҳәм керисинше -функционалдың ерликточкасы (1)-(5) ҳәм (7)-(8) мәселелериниң шешимин анықлайды.
II-бап. Еки этаплы стохастикалық сызықлы программаластырыў мәселеси
§2.1. Еки этаплы стохастикалық сызықлы мәселениң қойылыўы ҳәм шешилиў усыллары.


§2.2. Стохастикалық квазиградиентлер усылының эффективлигин асырыў усыллары.
Шексиз адымлы итерациялық методлардың эффективлиги (бул усылларға квазиградиентлер усылы да қараслы) төмендеги факторға байланыслы яғный ҳәр бир итерацияда есаплаўлар саны ҳәм сол усылдың жыйнақлылық тезлиги стохастикалық субградиенти (1.31) ға сәйкес есаплаўда баслы қыйыншылық ны табыў, оның ушын төмендеги мәселени шешиў зәрүр:
(3.24)
(3.25)
(3.26)
Бул мәселениң өлшеми жүзлеген шегаралық ҳәм мыңлаған өзгериўшилерден турыўы мүмкин ҳәм оны ҳәр бир итерацияда шешиў керек, сонлықтан есаплаўлар санын қысқартыў усыллары зәрүр болады.
матрица ҳәм вектор дитерминерленген жағдайын қараймыз. Онда (3.24)-(3.26) мәселесинде шегаралық шәртлери итерациядан итерацияға өзгермейди, сонлықтан ди табыў ушын мәселениң -итерацияда симплекс таблицасын пайдаланыў мүмкин, басланғыш тирек шешим ретинде есапланады. Есаплаўларды усылай шөлкемлестириўде еки есе утысқа ериседи. Бириншиден, мийнет талап ететуғын әмеллерде басланғыш тирек шешимлерди табыў кереклиги алып тасланады (мысал ушын M-метод жәрдеминде). Екиншиден ға жақсы жуўықласыў болады ҳәм шегаралық шәртлери менен кесилискен көпжақлылық төбесинен төбесине өтиў ушын симплекс методының бир неше итерациясы талап етиледи. матрицасы тосынанлы емес болып табылады.
Яғный
(3.27)
мәселе қаралады.
(3.27) ни -итерацияда шешиў ушын төмендеги усылды келтириў мүмкин. Дәслеп төмендеги мәселе (3.27) мәселениң симплекс таблицасынан пайдаланып шешиледи.
(3.28)
Кейин төмендеги мәселе (3.28) мәселесиниң симплекс таблицасынан пайдаланып шешиледи.
(3.29)
Бирақ бунда қосарлы симплекс усылы пайдаланады, бул (3.29) мәселениң өтирик шешими (псевдорешение) сыпатында (3.28) шешими қолланылады.
Егер матрица тосынанлы болып есапланса, онда «жақын» сызықлы мәселе ушын исленген арнаўлы методларды пайдаланыў керек болады. Соның менен бирге төмендеги яғный мәселениң -ши итерациядан итерациядағы мәселеге өтиўдиң төмендеги избе-излигин пайдаланыўға болады.

Айрым ўақытлары (3.24)-(3.26) мәселесин шешиўге сызықлы программаластырыўдың улыўма методларын қолланыў шәрт емес, себеби бул мәселе арнаўлы класс мәселелерине қараслы болыўы мүмкин. Бундай мәселелер менен биз төменде танысамыз.
Стохастикалық субградиентти есаплаўда есаплаўлардың үлкен бөлеги рекуррент формулалар бойынша есапланады. Стохастикалық квазиградиентлерди проекциялаў методы мүмкин болған көпликлерди ҳәр итерацияда проекциялаўды талап етеди ҳәм көплик әпиўайы түрге ийе болғанда ҳәм проекциялаў әмелин иске асырыў аңсат болғанда қолланыў мүмкин. Улыўма жағдайда областқа проекциялаў ушын үлкен өлшемдеги

квадратлық программаластырыў мәселесин шешиў керек болады. Сызықландырыў методларында квадратлық программаластырыў мәселесиниң орнына

сызықлы программаластырыў мәселеси шешиледи.
Бул мәселени шешиўде стохастикалық субградиентти есаплаў ушын керек болған түсиниклерди қолланыў мүмкин.
Әсиресе (3,19), (3,19¹),(3,22)
Сонлықтан тың өсиўи менен тен ге өтиў ушын керек болған итерациялар саны сәйкес кемейеди.
Стохастикалық квазиградиентлер усылларында ҳәр бир итерацияда есаплаў көлемине байланыслы болып қалмастан, ал оның жыйнақлылық тезлигинде байланыслы болады.
Алынған теориялық баҳалаўлар стохастикалық квазиградиентлер методларының тезлиги үлкен емеслигин көрсетеди. Буның себеплериниң бири.
Стохастикалық квазиградиентлерди проекциялаў методында тоқтаймыз. Бунда -адым узынлығы төмендеги шәртлерди қанаатландырады.
(3.27)
Бул қатнасларды мәселен әмелде тмендегише сайлап алыўға болады.
(3.28)
Бунда ти итерациялық процесстиң жағдайына ғәрезли өзгертиў мүмкин. Егер функциясын максимумластырыў мәселесин шешетуғын болса, онда айрым жағдайда төмендеги мәселелерди анализ ислеў мақсетке муўапық болады.

ге қойылатуғын шәртлердиң бири дәслепкидегидей яғный ҳәм лер 1-ши итерациясында бирдей тәртипке ийе болыўы болып есапланады. Бул шәртлерден ти сайлап алыў мүмкин. ЭЕМ де өткерилген экспериментлер саны соны көрсетеди, итерацияның айырым санлары процесс басында турақлы адым менен ҳәрекет етеди, ал кейин ти (3,28) формулаға тийкарлап сайлап алыў мүмкин. Сызықлы емес программаластырыўдың (традициялық) методларында процесстиң жуўмақланыўын анықлаў ушын традициялық есаплаўға тийкарланған оптималластырыў шәрти пайдаланады. Мәселен дифференциалланыўшы мақсет функциясы мейли дөңес программаластырыў мәселесин яғный , шешиўде оптимумға ийе болыўының жеткиликли шәрти төмендеги теңсизликтиң орынланыўы болып есапланады.
(3.29)
бунда
(3.30)
Стохастикалық программаластырыў мәселесинде ты ҳәр бир итерацияда есаплаў мәселеси айрықша мийнет талап етеди. Сонлықтан градиент ҳәм оның аналогин көбирек есаплаў көз-қарасынан қолайлы векторға алмастырыў керек. Дифференциалланыўшы функциялар ушын стохастикалық сызықландырыў методында бундай шама болып есапланады ти дың орнына қолланыў көрсетилген яғный

Солай етип дифференциалланыўшы функция ушын арналған стохастикалық сызықландырыў методын пайдаланыўда (3,29) (3,30) қатнасықларының орнына
(3.31)
(3.32)
қатнасларынан пайдаланыў мүмкин.
Адымы көбейтиўшилер итерациялардың белгили бир санынан кейин жүдә киши болыўы мүмкин ҳәм -дан жеткиликли узақта жайласыўына қарамастан итерациядан итерацияға аз өзгерип барады. Бул жағдай болмаўы ушын процессти яғный ти көбейтиў ҳәм процессти қайтадан баслаў тийис. Дифференциалланыўшы ты стохастикалық сызықландырыў методы ушын тиң текшеше өзгериўиниң төмендеги процессин яғный (3.31) (3.32) қатнасларын келтириў мүмкин.
Мейли, бунда ҳәм -функционал бойынша талап етилген дәллик. Итерацияның 1- сериясында:

Егер болса 1- серия жуўмақланады.
1- серия жуўмақланатуғын номерди арқалы аңлатамыз. Итерацияның 2- сериясында:

итерацияның k-сериясында:

уқсаслығы бойынша -арқалы биз сондай номерды белгилеймиз, яғный төмендеги
(3.33)
теңсизлиги орынлы болады.