Аптымізацыйных задача - гэта задача знаходжання экстрэмуму (мінімуму ці максімуму) мэтавай функцыі ў некаторай вобласці канечнамернае вектарнага прасторы, абмежаванай наборам лінейных і / або нелінейных роўнасцяў і / або няроўнасцей.
Мэтавая функцыя ўяўляе сабой набор крытэраў якасці, якія павінны быць аптымізаваныя адначасова. У агульным выпадку мэтавая функцыя складаецца з кіраваных і некіравальных зменных. Ўмова пошуку экстрэмуму мэтавай функцыі запісваецца ў наступным выглядзе:
Метады рашэння аптымізацыйных задач вывучае матэматычнае праграмаванне. Матэматычнае праграмаванне - гэта матэматычная дысцыпліна, якая вывучае тэорыю і метады рашэння задач па вызначэнні экстрэмуму функцый на мноствах канечнамернае вектарнага прасторы, якiя вызначаюцца наборам лінейных і / або нелінейных абмежаванняў (роўнасць і / або няроўнасць). Матэматычнае праграмаванне ўяўляе сабой, як правіла, шматкроць паўтаральную вылічальную працэдуру, якая прыводзіць да шуканага аптымальнаму рашэнню. Выбар метаду матэматычнага праграмавання для вырашэння аптымізацыйных задачы вызначаецца выглядам залежнасцяў у матэматычнай мадэлі, характарам шуканых зменных, катэгорыяй зыходных дадзеных і колькасцю крытэрыяў аптымальнасці:
- Метады лінейнага праграмавання выкарыстоўваюцца ў выпадку, калі ў матэматычнай мадэлі маюцца толькі лінейныя залежнасці паміж зменнымі, для вырашэння аптымізацыйных задачы.
- Метады нелінейнага праграмавання выкарыстоўваюцца ў выпадку, калі ў матэматычнай мадэлі маюцца нелінейныя залежнасці паміж зменнымі, для вырашэння аптымізацыйных задачы.
- Метады цэлалікавага або дыскрэтнай праграмавання выкарыстоўваюцца ў выпадку, калі сярод зменных маюцца цэлалікавых або дыскрэтныя зменныя, адпаведна.
- Метады стахастычнага праграмавання выкарыстоўваюцца ў выпадку, калі зыходныя дадзеныя або іх частка з'яўляюцца выпадковымі велічынямі.
- Матэматычны апарат тэорыі гульняў выкарыстоўваюцца ў выпадку, калі зададзена недетерминированная (нявызначаная) зыходная інфармацыя.
Рашэнне задачы аптымізацыі ажыццяўляецца з дапамогай пошукавых метадаў, якія выкарыстоўваюць папярэднюю інфармацыю для пабудовы палепшанага рашэння задачы (ітэрацыйныя метады разліку). Да цяперашняга часу распрацавана дастаткова шмат метадаў лакальнай аптымізацыі для вырашэння задач агульнага выгляду. Большасць з іх выкарыстоўваюць прынцып лакальнага спуску, калі метад паслядоўна на кожным кроку пераходзіць да кропак з істотна меншымі (вялікім) значэннямі мэтавай функцыі. Дадзеныя метады адрозніваюцца адзін ад іншага спосабам вызначэння напрамкі руху да оптымуму, памерам кроку і працягласцю пошуку ўздоўж знойдзенага напрамкі, а таксама крытэрамі заканчэння пошуку. Пошук аптымальнага значэння ў такіх задачах можа быць прадстаўлены ў выглядзе ітэрацыйныя суадносін:
дзе пераменная 
- гэта прырашчэнне вектара кіраваных параметраў. У залежнасці ад ўмовы пошуку (пошук максімальнага або мінімальнага значэння мэтавай функцыі) выкарыстоўваецца альбо знак «+», альбо знак «-».
Прырашчэнне вектара кіраваных параметраў у большасці выпадках вылічаецца па формуле:
У дадзеным выразе 
- значэнне вектара кіраваных параметраў на k-ым кроку, 
- крок разліку, а 
- кірунак пошуку экстрэмуму функцыі.
У залежнасці ад колькасці кіраваных параметраў адрозніваюць метады аднамернай і шматмернай аптымізацыі (многокритериальная аптымізацыя). Пошук лічыцца аднамерны, у выпадку калі аргументам мэтавай функцыі з'яўляецца адзін кіраваны параметр.
крок разліку
Ітэрацыйныя форма метадаў лакальнай аптымізацыі для вырашэння задач пошуку экстрэмуму мэтавай функцыі патрабуе выбару кроку разліку ўздоўж зададзеных кірункаў на кожным кроку ітэрацыі. Крок разліку можа быць пастаянным або пераменным, але аптымальнае значэнне даўжыні кроку вызначаецца ў выніку пошуку экстрэмуму мэтавай функцыі ў абраным кірунку 
з выкарыстаннем метадаў аднамернай аптымізацыі:
Іншымі словамі, велічыня кроку разліку вылічаецца пры вырашэнні наступнага выказвання:
У выніку рашэння дадзенага раўнанне мы атрымаем, што крок разліку ў сімвальным выглядзе вызначаецца наступным чынам:
дзе 
- значэнне аргументу функцыі на k-ым кроку ітэрацыі;
n - колькасць невядомых зменных, якія вызначаюцца ў ходзе рашэння задачы;
L - некаторая канстанта, якая вызначаецца з вызначальніка наступнай матрыцы:
У выніку для вызначэння аптымальнага кроку разліку патрабуецца выканаць вялікі аб'ём вылічэнняў мэтавай функцыі. Для зніжэння колькасці аперацый на практыцы выкарыстоўваюць іншы падыход: падбіраюць такія значэнні кроку разліку 
, Каб яны задавальнялі любому з унізе умове.
дзе каэфіцыент 
, А крок разліку вызначаецца итеративно шляхам множання першапачатковага кроку 
на каэфіцыент 
да таго часу, пакуль не будзе выконвацца ўмова.
Крытэрый выбару кроку разліку па правілу Армихо
Методыка вызначэння кроку разліку аптымізацыйных задачы ў адпаведнасці з правілам Армихо заключаецца ў наступным:
1.Задать каэфіцыент 
у дыяпазоне ад 0 да 1.
2.Задать пачатковае значэнне кроку .
Працэдура пошуку (праверка выканання ўмовы па правілу Армихо)
3. У выпадку, калі ўмова па правілу Армихо не выконваецца, тады неабходна скарэктаваць крок разліку 
, Дзе пераменная 
можа прымаць любое значэнне ад 0 да 1, па змаўчанні прымем, што пераменная 
, а 
- бягучы крок пошуку.
4. У выпадку калі ўмова па правілу Армихо выконваецца, тады ў якасці кроку разліку можна прыняць 
, А працэдура пошуку завяршаецца.
Дадзенае правіла патрабуе аднаразовага вылічэнні градыенту, пасля чаго невялікая колькасць ітэрацый затрачваецца на падбор падыходнага кроку. Кожная з такіх ўкладзеных ітэрацый, у сваю чаргу, патрабуе вылічэнні значэння мэтавай функцыі без градыенту, то ёсць якія праводзяцца выпрабаванні адносна легкаважныя. Варта адзначыць, што дадзенае ўмова задавальняецца для ўсіх досыць малых . Правіла Армихо можна пашырыць на многокритериальный выпадак: няроўнасць 3.19 варта разумець покомпонентно.
- Другая ўмова (Правіла Вольф-Паўэла - Wolfe. P) з'яўляецца мадыфікаваным крытэрыем, дазваляе выбраць крок разліку ў выпадку выканання дзвюх умоў:
- функцыя 
не павінна перавышаць значэння некаторай меншае лінейнай функцыі, роўнай 
ў нулі:
- велічыня хуткасці змены функцыя ў зададзеным кірунку 
была ў 
разоў больш, чым хуткасць змены функцыі ў першапачатковай кропкі
Крытэрый выбару кроку разліку па правілу Вольф-Паўэла
Методыка вызначэння кроку разліку аптымізацыйных задачы ў адпаведнасці з правілам Вольф-Паўэла заключаецца ў наступным:
1. Задаць каэфіцыент 
і 
у дыяпазоне ад 0 да 1 
.
2. Задаць пачатковае значэнне кроку 
, Прыняць каэфіцыент 
і 
Працэдура пошуку (праверка выканання ўмовы па правілу Вольф-Паўэла)
3. У выпадку калі першае ўмова па правілу Вольф-Паўэла не выконваецца, тады прыняць каэфіцыент 
. Перайсці да пункта №5.
4. У выпадку калі другая ўмова па правілу Вольф-Паўэла не выконваецца, тады прыняць каэфіцыент 
:
- у выпадку калі 
, То перайсці да пункта №5;
- у выпадку калі выканаць экстрапаляцыю, паклаўшы 
, Дзе r - каэфіцыент экстрапаляцыі 
. Перайсці да пункта №3.
5. Выканаць бягучы разлік кроку па формуле
дзе 
- каэфіцыент інтэрпаляцыі, які вызначаецца ў наступным дыяпазоне 
Перайсці да пункта №3.
6. У выпадку, калі выконваюцца абодва ўмовы правілу Вольф-Паўэла, тады ў якасці кроку разліку можна прыняць , А працэдура пошуку завяршаецца.
- Трэцяя ўмова (правіла Гольдштэйна-армій) дазваляе выбраць крок разліку, разглядаючы наступнае няроўнасць:
Методыка вызначэння кроку разліку аптымізацыйных задачы ў адпаведнасці з правілам Гольдштэйна-армій заключаецца ў наступным:
1.Задать каэфіцыент 
і 
у дыяпазоне ад 0 да 1 
.
2. Задаць пачатковае значэнне кроку
3. У выпадку, калі ўмова па правілу Гольдштэйна-армій не выконваецца, тады неабходна скарэктаваць крок разліку , Дзе пераменная можа прымаць любое значэнне ад 0 да 1, па змаўчанні прымем, што пераменная , а - бягучы крок пошуку.
4. У выпадку калі ўмова па правілу Гольдштэйна-армій выконваецца, тады ў якасці кроку разліку можна прыняць , А працэдура пошуку завяршаецца.
Крытэрыі супыну аптымізацыйных працэсу
Пошук аптымальнага рашэння завяршаецца ў выпадку, калі на ітэрацыйныя кроку разліку выконваецца адзін (ці некалькі) крытэрыяў:
- траекторыя пошуку застаецца ў малой наваколлі бягучай пункту пошуку:
- прырашчэнне мэтавай функцыі не змяняецца:
- градыент мэтавай функцыі ў кропцы лакальнага мінімуму звяртаецца ў нуль:
Класіфікацыя метадаў аптымізацыі.
У цяперашні час для вырашэння задач аптымізацыі распрацавана велізарная колькасць розных матэматычных метадаў. Ужыванне таго ці іншага метаду вызначаецца пастаноўкай задачы, складанасцю вылічэнні функцыі і яе вытворных, паводзінамі функцыі і т. Д.
Задачы аптымізацыі і метады іх рашэння можна падзяліць па наяўнасці або адсутнасці абмежаванняў (задаецца сістэмай няроўнасцей і роўнасцяў ці больш складаным алгарытмам) у матэматычных мадэлях на метады ўмоўнай і безумоўнай аптымізацыі. Для рэальных задач характэрна наяўнасць абмежаванняў, аднак метады безумоўнай аптымізацыі таксама ўяўляюць цікавасць, паколькі задачы ўмоўнай аптымізацыі з дапамогай спецыяльных метадаў могуць быць зведзены да задач без абмежаванняў.
Метады безумоўнай аптымізацыі
Класічная задача безумоўнай аптымізацыі фармулюецца наступным чынам: патрабуецца знайсці вектар зменных 
, Пры якім мэтавая функцыя прымае экстрэмальнае (максімальнае або мінімальнае значэнне) значэнне
Экстрэмальнае значэнне мэтавай функцыі адпавядае аптымальнаму кіраванню. У графічным выглядзе пастаноўка задачы выглядае наступным чынам:
Задача безумоўнай аптымізацыі для функцыі дзвюх зменных
Сутнасць метаду аптымізацыі ў першую чаргу вызначаецца спосабам выбару напрамку руху да экстрэмуму. У залежнасці ад выкарыстоўванага парадку вытворных мэтавай функцыі метады безумоўнай аптымізацыі дзеляць на метады нулявога, першага і другога парадкаў. Калі вытворныя не выкарыстоўваюцца, то мае месца метад нулявога парадку, калі выкарыстоўваюцца першыя ці другія вытворныя, то адпаведна метад першага або другога парадку.
- Метады нулявога парадку (метады прамога пошуку) для пошуку экстрэмуму функцыі патрабуюць вылічэнне толькі значэнняў функцыі ў кропках прасторы аптымізацыі. У дадзеным метадзе інфармацыя аб вытворных не выкарыстоўваецца і, адпаведна, не патрабуюць вызначэння аналітычнага выгляду вытворных. У залежнасці ад колькасці кіраваных параметраў адрозніваюць метады аднамернага і шматмернага пошуку.
Найбольш папулярнымі (з пункту гледжання навучання ў вышэйшай школе) з'яўляюцца наступныя метады рашэння аптымізацыйных задач нулявога парадку:
Метады аднамернага пошуку:
- Метад дихотомического дзялення і метад залатога перасеку - гэта метады аднамернай аптымізацыі, заснаваныя на дзяленні адрэзка, на якім шукаецца экстрэмуму, напалову або ў прапорцыях залатога перасеку (0,382 / 0,618), адпаведна.
- Метад паліномны апраксімацыі (метад квадратычнай інтэрпаляцыі) - гэта метад аднамернай аптымізацыі, у адпаведнасці з якім мэтавая функцыя апраксімуецца квадратычным полиномом.
Метады шматмернага пошуку:
- Метад покоординатного спуску (Гаўса-Зейделя) - гэта метад безумоўнай аптымізацыі нулявога парадку, у якім кірунку пошуку выбіраюцца па чарзе ўздоўж усіх каардынатных восяў, крок разлічваецца на аснове аднамернай аптымізацыі.
- Метад верцяцца каардынатаў (Метад Розенброка) - гэта метад безумоўнай аптымізацыі нулявога парадку, у якім рэалізуецца покоординатный спуск, але ўздоўж каардынатных восяў, паварочваецца такім чынам, каб кірунак адной з восяў было блізка да кірунку, паралельны дне яра.
- сімплексным метад (метад дэфармуемага мнагагранніка або метад Нелдера-МЗС) - гэта метад безумоўнай аптымізацыі нулявога парадку, заснаваны на шматкроць паўтараных аперацыях пабудовы мнагагранніка з (n + 1) вяршынямі, дзе n - памернасць прасторы кіраваных параметраў, і перамяшчэння найгоршай вяршыні (з найгоршым значэннем мэтавай функцыі) у напрамку цэнтра цяжару мнагагранніка.
- Метады першага парадку (градыентныя метады пошуку) для пошуку экстрэмуму патрабуюць вылічэнні значэнняў функцыі ў кропках прасторы аптымізацыі, а таксама вызначэнне аналітычнага выгляду вытворных першага парадку па кіраваным параметрах. Метады першага парадку называюць таксама Градыентнае, паколькі вектар першых вытворных функцыі F (X) па оптимизируемым пераменным X ёсць градыент мэтавай функцыі:
Градыент ў базавай кропцы строга ортогонален да паверхні, а яго кірунак паказвае кірунак найхутчэйшага ўзрастання функцыі, а супрацьлеглае кірунак (антиградиента), адпаведна, паказвае кірунак найхутчэйшага змяншэння функцыі. Градыентныя метады адрозніваюцца адзін ад іншага спосабам вызначэння напрамкі руху да оптымуму, памерам кроку і працягласцю пошуку ўздоўж знойдзенага напрамкі, а таксама крытэрамі заканчэння пошуку.
Найбольш папулярнымі (з пункту гледжання навучання ў вышэйшай школе) з'яўляюцца наступныя метады рашэння аптымізацыйных задач першага парадку:
- Метад градыентнага спуску - гэта метад знаходжання лакальнага мінімуму (максімуму) функцыі з дапамогай руху ўздоўж градыенту з пераменным (дробавым) крокам, які задаецца карыстальнікам.
- Метад найхутчэйшага спуску - гэта метад знаходжання лакальнага мінімуму (максімуму) функцыі пры руху ўздоўж градыенту з аптымальным крокам. Крок разліку выбіраецца мінімуму мэтавай (минимизируемой) функцыі ў кірунку спуску.
- Метад спалучаных градыентаў (метад Флетчара-Ривса) - гэта метад безумоўнай аптымізацыі першага парадку, у якім кірунак пошуку на чарговым кроку ёсць Градыентнае кірунак, адкарэктаваныя з улікам кірунку пошуку на папярэднім кроку.
- Метад зменнай метрыкі (метад Девидона-Флетчара-Паўэла) - гэта метад безумоўнай аптымізацыі, у якім за аснову ўзята рашэнне сістэмы раўнанняў, якія выказваюць неабходныя ўмовы экстрэмуму.
- Метады другога парадку для пошуку экстрэмуму патрабуюць вылічэнні значэнняў функцыі ў кропках прасторы аптымізацыі, а таксама вызначэнне аналітычнага выгляду вытворных першага і другога парадку па кіраваным параметрах.
Найбольш папулярнымі (з пункту гледжання навучання ў вышэйшай школе) з'яўляюцца наступныя метады рашэння аптымізацыйных задач другога парадку:
- метад Ньютана - гэта метад безумоўнай аптымізацыі, заснаваны на выкарыстанні неабходных умоў безумоўнага экстрэмуму мэтавай функцыі: роўнасці нуля першай вытворнай. У адпаведнасці з дадзеным метадам вызначаюць матрыцу другое прыватных вытворных мэтавай функцыі па кіраваным параметрах (матрыцы Гесэ).
- Метад Марквардт - гэта метад безумоўнай аптымізацыі, накіраваны на вырашэнне задач ацэньвання задача. З'яўляецца альтэрнатывай метадзе Гаўса - Ньютана. Можа разглядацца як камбінацыя апошняга з метадам градыентнага спуску або як метад даверных інтэрвалаў.
Метады ўмоўнай аптымізацыі
Класічная задача ўмоўнай аптымізацыі фармулюецца наступным чынам: неабходна знайсці вектар зменных 
, Пры якім мэтавая функцыя прымае экстрэмальнае (максімальнае або мінімальнае значэнне) значэнне
пры зададзеных умовах (роўнасць і / або няроўнасць), пры гэтым колькасць абмежаванняў m можа быць як больш, так і менш ліку зменных n.
, J = 1,2, ..., m.
Іншымі словамі, неабходна знайсці экстрэмуму мэтавай функцыі пры ўмове, што значэнні аргументаў функцыі належаць вобласці дапушчальных значэнняў, якая утвараецца сістэмай абмежаванняў. Экстрэмальнае значэнне мэтавай функцыі адпавядае аптымальнаму кіраванню. У графічным выглядзе пастаноўка задачы выглядае наступным чынам:
Задача ўмоўнай аптымізацыі для функцыі дзвюх зменных
У залежнасці ад выкарыстоўванага метаду рашэння метады ўмоўнай аптымізацыі можна падзяліць на метады звесткі задачы да безумоўнай аптымізацыі і метады непасрэднага рашэння.
- Метады звесткі задачы да безумоўнай аптымізацыі - гэта задача ўмоўнай аптымізацыі, заснаваная на пераўтварэнне задачы нелінейнага праграмавання ў паслядоўнасць задач безумоўнай аптымізацыі шляхам пабудовы дапаможных функцый
Найбольш папулярнымі (з пункту гледжання навучання ў вышэйшай школе) з'яўляюцца наступныя метады рашэння аптымізацыйных задач ўмоўнай аптымізацыі:
- Метад нявызначаных множнікаў Лагранжа - гэта метад ўмоўнай аптымізацыі, арыентаваны на пошук экстрэмуму мэтавай функцыі пры наяўнасці абмежаванняў тыпу роўнасцяў.
- Умовы Куна-Таккер - гэта метад рашэння аптымізацыйных задачы матэматычнага праграмавання з зададзенымі абмежаваннямі. Метад з'яўляецца абагульненнем метаду множнікаў Лагранжа на выпадак агульнай задачы нелінейнага праграмавання з абмежаваннямі, як у выглядзе роўнасцяў, так і ў выглядзе няроўнасцей.
- Метад штрафных функцый - гэта метад або група метадаў для вырашэння задач матэматычнага праграмавання, заснаваныя на пераўтварэнні задачы ўмоўнай аптымізацыі ў задачу безумоўнай аптымізацыі шляхам фарміравання новай мэтавай функцыі, якая ўлічвае абмежаванні задачы.
- Метады непасрэднага рашэння задачы ўмоўнай аптымізацыі - гэта задача ўмоўнай аптымізацыі, заснаваная на руху з адной дапушчальнай кропкі, дзе выкананы ўсе абмежаванні, да іншай дапушчальнай кропцы з лепшым значэннем мэтавай функцыі.
Найбольш папулярнымі (з пункту гледжання навучання ў вышэйшай школе) з'яўляюцца наступныя метады рашэння аптымізацыйных задач ўмоўнай аптымізацыі:
- Метад прыведзенага градыенту - гэта метад ўмоўнай аптымізацыі, арыентаваны на рашэнне задач з абмежаваннямі тыпу роўнасцяў. Напрамак рух у дадзеным метадзе вызначае прыведзены градыент функцыі.
- Метад магчымых напрамкаў (метад Зойтендейка) - гэты метад рашэння задач матэматычнага праграмавання заснаваны на руху з адной дапушчальнай кропкі да іншай з лепшым значэннем мэтавай функцыі.
Лікавыя метады аптымізацыі рэалізаваны і шырока выкарыстоўваюцца ў розных матэматычных пакетах. Пры гэтым наяўнасць гатовых праграмных сродкаў (матэматычных бібліятэк і пакетаў) не толькі не здымае неабходнасць вывучэння метадаў, а наадварот, робіць падрыхтоўку ў гэтым напрамку яшчэ больш актуальнай. Гэта звязана з тым, што пры вырашэнні рэальнай задачы ад спецыяліста патрабуецца пісьменная матэматычная пастаноўка задачы, яе фармалізацыя, абгрунтаванне і выбар найбольш эфектыўнага метаду разліку, а таксама ўменне вырабляць ацэнку адэкватнасці і дакладнасці атрыманых вынікаў.
Для таго, каб дадаць Ваш каментар да артыкула, калі ласка, зарэгіструйцеся на сайце.