Нелинеарно програмирање

У математици, нелинеарно програмирање (НЛП) је процес решавања оптимизационог проблема где су нека од ограничења или објективних функција нелинеарна. Оптимизациони проблем је један од прорачуна екстрема (максимума, минимума или стационарних тачака) једне објективне функције над сетом непознатих реалних променљивих, који је условљен задовољавањем система једначина и неједначина, колективно званих ограничења. То је потпоље математичке оптимизације које се бави проблемима који нису линеарни.

Примењивост

Типични неконвексни проблем је проблем оптимизације трошкова превоза селекцијом из сета транспортних метода, од којих један или више манифестују ефекте размера, с различитим степенима повезивања и ограничењима капацитета. Пример би био транспорт нафтних деривата с обзиром на избор или комбинацију цевовода, жељезничких танкера, цестовних танкера, речне барке или приобалског брода. Због економије величине шарже, трошковне функције могу имати и дисконтинуитете осим глатких промена.

У експерименталној науци неке се једноставних анализа података (попут уклапања спектра са збиром пикова познатог положаја и облика, али непознате магнитуде) могу се обавити линеарним методама, али генерално су и ови проблеми нелинеарни. Типично постоји теоријски модел испитиваног система с промењивим параметрима у њему, и модел експеримента или експеримената, који такође може да има непознате параметре. Потребно је да се нумерички пронађе најбоље уклапање. У овом случају се често захтева извесна мера прецизности резултата, као и само најбоље уклапање.

Дефиниција

Нека су n, m, и p позитивни цели бројеви. Нека је X подскуп скупа Rⁿ, нека су f, g_i, и h_j функције реалних вредности на X за свако i у {1, …, m} и свако j у {1, …, p}, при чему је бар једна од f, g_i, и h_j нелинеарна.

Проблем нелинеаре минимизације је проблем оптимизације облика

${\begin{aligned}{\text{minimiziraj }}&f(x)\\{\text{tako da je }}&g_{i}(x)\leq 0{\text{ za svako }}i\in \{1,\dotsc ,m\}\\&h_{j}(x)=0{\text{ za svako }}j\in \{1,\dotsc ,p\}\\&x\in X.\end{aligned}}$

Проблем нелинеарне максимизације је дефинисан на сличан начин.

Могући типови сета ограничења

Постоји неколико могућности за природу скупа ограничења, познатог и под називом изводљиви скуп или изводљива регија. Неизводљив је проблем за који ниједан скуп вредности за изабране променљиве не задовољава сва ограничења. То јест, ограничења су узајамно контрадикторна и не постоји решење, те је изводљиви скуп је празан скуп. Изводљив је проблем за који постоји барем један низ вредности за скуп изабраних променљивих који задовољава сва ограничења. Неограничени проблем је изводљив проблем за који се циљна функција може учинити бољом од било које дате коначне вредности. Према томе, не постоји оптимално решење, јер увек постоји изводљиво решење које даје бољу вредност објективне функције од било којег предложеног решења.

Методи за решавање проблема

Ако је циљна функција f линеарна, а ограничени простор политоп, проблем је проблем линеарног програмирања, који се може решити коришћењем познатих техника линеарног програмирања, као што је симплекс метода.

Ако је циљна функција конкавна (проблем максимизације), или конвексна (проблем минимизације), и скуп ограничења је конвексан, онда се програм назива конвексним и опште методе из конвексне оптимизације могу се користити у већини случајева.

Ако је циљна функција квадратна, а ограничења линеарна, користе се технике квадратног програмирања.

Ако је циљна функција однос конкавне и конвексне функције (у случају максимизације), а ограничења су конвексна, онда се проблем може трансформисати у проблем конвексне оптимизације помоћу техника фракцијског програмирања.

Доступно је неколико метода за решавање неконвексних проблема. Један од приступа је употреба посебних формулација проблема линеарног програмирања. Друга метода укључује употребу техника сепарације и евалуације, где је програм подељен на подкласе које треба решити конвексним (проблем минимизације) или линеарним апроксимацијама, које формирају доњу границу свеукупних трошкова у поделама. С накнадним поделама, у неком тренутку ће се добити стварно решење, чији је трошак једнак најбољој доњој граници добивеној за било које од приближних решења. Ово решење је оптимално, мада је могуће да није јединствено. Алгоритам се такође може зауставити рано, са сигурношћу да је најбоље могуће решење унутар толеранције од најбоље пронађене тачке; такве тачке се називају ε-оптималним. Прекид на ε-оптималним тачкама је обично неопходан да би се осигурао коначни прекид. Ово је посебно корисно за велике, тешке проблеме и проблеме са непредвидивим трошковима или вредностима, где се неизвесност може проценити одговарајућом проценом поузданости.

Под претпоставкама диференцијабилности и константних квалификација, Каруш–Кан–Такерови услови (ККТ) пружају потребне услове да решење буде оптимално. Под претпоставком конвексности, ови услови су такође довољни. Ако су неке функције недиференциране, субдиференцијабилне верзије ККТ услова су доступне.

Примери

Дводимензиони пример

Плави регион је изводљиви регион. Тангента линије са изводивим регионом представља решење. Та линија је најбоје остварива контурна линија (локус са датом вредношћу објективне функције).

Једноставни проблем (приказан на дијаграму) може се дефинисати помоћу ограничења

x₁ ≥ 0

x₂ ≥ 0

x₁² + x₂² ≥ 1

x₁² + x₂² ≤ 2

са објективном функцијом коју треба максимизовати

ф(x) = x₁ + x₂

где је x = (x₁, x₂).

Тродимензиони пример

Тангента горње површине са ограниченим простором у средини представља решење.

Још један једноставан проблем (погледајте дијаграм) може се дефинисати помоћу ограничења

x₁² − x₂² + x₃² ≤ 2

x₁² + x₂² + x₃² ≤ 10

са објективном функцијом коју треба максимизовати

ф(x) = x₁x₂ + x₂x₃

где је x = (x₁, x₂, x₃).

Литература

• Авриел, Мордецаи (2003). Нонлинеар Программинг: Аналyсис анд Метходс. Довер Публисхинг. ISBN 0-486-43227-0.
• Базараа, Мокхтар С. анд Схеттy, C. M. (1979). Нонлинеар программинг. Тхеорy анд алгоритхмс. Јохн Wилеy & Сонс. ISBN 0-471-78610-1.
• Боннанс, Ј. Фрéдéриц; Гилберт, Ј. Цхарлес; Лемарéцхал, Цлауде; Сагастизáбал, Цлаудиа А. (2006). Нумерицал оптимизатион: Тхеоретицал анд працтицал аспецтс. Университеxт (Сецонд ревисед ед. оф транслатион оф 1997 Френцх изд.). Берлин: Спрингер-Верлаг. стр. xив+490. ИСБН 3-540-35445-X. МР 2265882. дои:10.1007/978-3-540-35447-5. 
• Луенбергер, Давид Г.; Yе, Yинyу (2008). Линеар анд нонлинеар программинг. Интернатионал Сериес ин Оператионс Ресеарцх & Манагемент Сциенце. 116 (Тхирд изд.). Неw Yорк: Спрингер. стр. xив+546. ИСБН 978-0-387-74502-2. МР 2423726. 
• Јан Бринкхуис анд Владимир Тикхомиров, Оптимизатион: Инсигхтс анд Апплицатионс, 2005, Принцетон Университy Пресс
• Боyд, Степхен П.; Ванденбергхе, Лиевен (2004). Цонвеx Оптимизатион. Цамбридге: Цамбридге Университy Пресс. ИСБН 0-521-83378-7. 
• Гилл, П. Е.; Мурраy, W.; Wригхт, M. Х. (1982). Працтицал Оптимизатион. Лондон: Ацадемиц Пресс. ИСБН 0-12-283952-8. 
• Лее, Јон (2004). А Фирст Цоурсе ин Цомбинаториал Оптимизатион. Цамбридге Университy Пресс. ИСБН 0-521-01012-8. 
• Ноцедал, Јорге; Wригхт, Степхен Ј. (2006). Нумерицал Оптимизатион (2нд изд.). Берлин: Спрингер. ИСБН 0-387-30303-0. 
• Снyман, Ј. А.; Wилке, D. Н. (2018). Працтицал Матхематицал Оптимизатион : Басиц Оптимизатион Тхеорy анд Градиент-Басед Алгоритхмс (2нд изд.). Берлин: Спрингер. ИСБН 978-3-319-77585-2. 
• Хассанзадех, Хамидреза; Роухани, Модјтаба (2010). „А мулти-објецтиве гравитатионал сеарцх алгоритхм”. Ин Цомпутатионал Интеллигенце, Цоммуницатион Сyстемс анд Нетwоркс (ЦИЦСyН): 7—12. 
• Схирази, Али; Најафи, Бехзад; Аминyавари, Мехди; Риналди, Фабио; Таyлор, Роберт А. (2014-05-01). „Тхермал–ецономиц–енвиронментал аналyсис анд мулти-објецтиве оптимизатион оф ан ице тхермал енергy стораге сyстем фор гас турбине цyцле инлет аир цоолинг”. Енергy. 69: 212—226. дои:10.1016/ј.енергy.2014.02.071. 
• Најафи, Бехзад; Схирази, Али; Аминyавари, Мехди; Риналди, Фабио; Таyлор, Роберт А. (2014-02-03). „Еxергетиц, ецономиц анд енвиронментал аналyсес анд мулти-објецтиве оптимизатион оф ан СОФЦ-гас турбине хyбрид цyцле цоуплед wитх ан МСФ десалинатион сyстем”. Десалинатион. 334 (1): 46—59. дои:10.1016/ј.десал.2013.11.039. 
• Рафиеи, С. M. Р.; Амирахмади, А.; Грива, Г. (2009). „Цхаос рејецтион анд оптимал дyнамиц респонсе фор боост цонвертер усинг СПЕА мулти-објецтиве оптимизатион аппроацх”. 2009 35тх Аннуал Цонференце оф ИЕЕЕ Индустриал Елецтроницс. стр. 3315—3322. ИСБН 978-1-4244-4648-3. С2ЦИД 2539380. дои:10.1109/ИЕЦОН.2009.5415056. 
• Роппонен, А.; Ритала, Р.; Пистикопоулос, Е. Н. (2011). „Оптимизатион иссуес оф тхе броке манагемент сyстем ин папермакинг”. Цомпутерс & Цхемицал Енгинееринг. 35 (11): 2510. дои:10.1016/ј.цомпцхеменг.2010.12.012. 
• Пллана, Сабри; Мемети, Суејб; Колодзиеј, Јоанна (2019). „Цустомизинг Парето Симулатед Аннеалинг фор Мулти-објецтиве Оптимизатион оф Цонтрол Цабинет Лаyоут”. арXив:1906.04825  [цс.ОХ]. 
• Нгуyен, Хоанг Анх; ван Иперен, Зане; Рагхунатх, Среекантх; Абрамсон, Давид; Кипоурос, Тимолеон; Сомасекхаран, Сандееп (2017). „Мулти-објецтиве оптимисатион ин сциентифиц wоркфлоw”. Процедиа Цомпутер Сциенце. 108: 1443—1452. дои:10.1016/ј.процс.2017.05.213 . хдл:1826/12173. 
• Ганесан, Т.; Еламвазутхи, I.; Васант, П. (2015-07-01). „Мултиобјецтиве десигн оптимизатион оф а нано-ЦМОС волтаге-цонтроллед осциллатор усинг гаме тхеоретиц-дифферентиал еволутион”. Апплиед Софт Цомпутинг. 32: 293—299. дои:10.1016/ј.асоц.2015.03.016. 
• Ганесан, Т.; Еламвазутхи, I.; Схаари, Ку Зилати Ку; Васант, П. (2013-01-01). Зелинка, Иван; Цхен, Гуанронг; Рöсслер, Отто Е.; Снасел, Вацлав; Абрахам, Ајитх, ур. Хyперволуме-Дривен Аналyтицал Программинг фор Солар-Поwеред Ирригатион Сyстем Оптимизатион. Адванцес ин Интеллигент Сyстемс анд Цомпутинг. Спрингер Интернатионал Публисхинг. стр. 147—154. ИСБН 978-3-319-00541-6. дои:10.1007/978-3-319-00542-3_15. 
• Ганесан, Т.; Еламвазутхи, I.; Схаари, Ку Зилати Ку; Васант, П. (2013-01-01). Гаврилова, Марина L.; Тан, C. Ј. Кеннетх; Абрахам, Ајитх, ур. Мултиобјецтиве Оптимизатион оф Греен Санд Моулд Сyстем Усинг Цхаотиц Дифферентиал Еволутион. Лецтуре Нотес ин Цомпутер Сциенце. Спрингер Берлин Хеиделберг. стр. 145—163. ИСБН 978-3-642-45317-5. дои:10.1007/978-3-642-45318-2_6. 
• Сурекха, Б.; Каусхик, Лалитх К.; Пандуy, Абхисхек К.; Вундавилли, Панду Р.; Параппагоудар, Махесх Б. (2011-05-07). „Мулти-објецтиве оптимизатион оф греен санд моулд сyстем усинг еволутионарy алгоритхмс”. Тхе Интернатионал Јоурнал оф Адванцед Мануфацтуринг Тецхнологy. 58 (1–4): 9—17. ИССН 0268-3768. С2ЦИД 110315544. дои:10.1007/с00170-011-3365-8. 
• „МултиОбјецтиве Оптимизатион ин Енгине Десигн Усинг Генетиц Алгоритхмс то Импрове Енгине Перформанце | ЕСТЕЦО”. www.естецо.цом. Архивирано из оригинала 10. 04. 2017. г. Приступљено 2015-12-01. 
• Цоуртеилле, Е.; Мортиер, Ф.; Леотоинг, L.; Рагнеау, Е. (2005-05-16). „Мулти-Објецтиве Робуст Десигн Оптимизатион оф ан Енгине Моунтинг Сyстем”. САЕ Тецхницал Папер Сериес (ПДФ). 1. Wаррендале, ПА. дои:10.4271/2005-01-2412. 
• Доминго-Перез, Францисцо; Лазаро-Галилеа, Јосе Луис; Wиесер, Андреас; Мартин-Горостиза, Ернесто; Салидо-Монзу, Давид; Ллана, Алваро де ла (април 2016). „Сенсор плацемент детерминатион фор ранге-дифференце поситионинг усинг еволутионарy мулти-објецтиве оптимизатион”. Еxперт Сyстемс wитх Апплицатионс. 47: 95—105. дои:10.1016/ј.есwа.2015.11.008. ЦС1 одржавање: Формат датума (веза)
• Бемпорад, Алберто; Муñоз де ла Пеñа, Давид (2009-12-01). „Мултиобјецтиве модел предицтиве цонтрол”. Аутоматица. 45 (12): 2823—2830. дои:10.1016/ј.аутоматица.2009.09.032. 
• Панда, Сидхартха (2009-06-01). „Мулти-објецтиве еволутионарy алгоритхм фор СССЦ-басед цонтроллер десигн”. Елецтриц Поwер Сyстемс Ресеарцх. 79 (6): 937—944. дои:10.1016/ј.епср.2008.12.004. 
• Фиандаца, Гиованна; Фрага, Ериц С.; Брандани, Стефано (2009). „А мулти-објецтиве генетиц алгоритхм фор тхе десигн оф прессуре сwинг адсорптион”. Енгинееринг Оптимизатион. 41 (9): 833—854. С2ЦИД 120201436. дои:10.1080/03052150903074189. Приступљено 2015-12-01. 
• Сендíн, Јосé Осцар Х.; Алонсо, Антонио А.; Банга, Јулио Р. (2010-06-01). „Еффициент анд робуст мулти-објецтиве оптимизатион оф фоод процессинг: А новел аппроацх wитх апплицатион то тхермал стерилизатион”. Јоурнал оф Фоод Енгинееринг. 98 (3): 317—324. дои:10.1016/ј.јфооденг.2010.01.007. хдл:10261/48082 . 

Спољашње везе

• Mathematical Programming Glossary Архивирано на сајту Wayback Machine (28. март 2010)