郑州首笔捐赠哈密130万元善款 80万元物资

Графиконот на параболоид даден со z = f (x, y) = - (x2 + y2) + 4. Глобалниот максимум на (x, y, z) = (0, 0, 4) е означен со сина точка.

Нелдер-Мидово пребарува?е на минимум на функци?ата Симонеску. Симплексните теми?а се подредени по нивната вредност, со 1 има на?ниска (на?добра) вредност.

百度 针对元宵节期间人员密集场所人员集中、街镇企业相继复工等特点，大兴支队在对辖区重点单位、高层建筑、老旧小区、大型商市场进行监督的基础上，积极对各社区、大型商市场、重点单位微型消防站进行拉动，督促物业管理单位、企业单位做好灭火救灾、应急处置的充分准备，确保关键时刻能“拉得出、冲得上、打得赢”。

Во математиката, комп?утерските науки и истражувачките активности, математичката оптимизаци?а, (алтернативно позната и како математичко програмира?е или едноставно оптимизаци?а) е избор на на?добриот елемент (во однос на некои критериуми) од множество на достапни опции.

Во на?едноставен случа?, оптимизаци?ата се состои од максимизира?е и минимизира?е на реална функци?а од страна на систематски избрани вредности во рамките на едно дозволено множество од пресметани вредности на функци?ата. Генерално, оптимизациската теори?а и техника е една голема област од применетата математика. Поопшто, оптимизаци?ата вклучува изнао?а?е на ?на?добрата достапна“ вредност на неко?а функци?а на целта, дефинирана во домен (или input), вклучува??и различни видови на функци?а на целта и различни видови на домени.

Оптимизациски проблем

Еден оптимизациски проблем може да се претстави на следниов начин:

Дадено: e функци?а f: A → R од множеството А во множеството реални броеви,

се бара: елемент x₀ од А таков што f(x₀) ≤ f(x) за сите x кои припа?аат на А (минимум) или таков што f(x₀) ≥ f(x) за сите x кои и припа?аат на А (максимум).

Ваквата формулаци?а е наречена оптимизациски проблем или математичко-програмски проблем (термин ко? не е директно поврзан со комп?утерското програмира?е, но сè уште се користи како на пример во линеарното програмира?е). Многу теоретски и реални проблеми можат да се моделираат во овие рамки. Проблемите кои се формулирани користе??и ?а оваа техника, а се од полето на физиката и комп?утерите може да се однесуваат на техниките за минимизира?е на енерги?ата, односно вредноста на функци?ата f ко?а ?а претставува енерги?ата во системот ко? ?е биде моделиран.

Типично, А е некое подмножество на Евклидов простор Rn, често претставен со множество на ограничува?а, што елементите на А мора да ги задоволуваат. Доменот на f е наречен простор за пребарува?е или множество од избори, додека елементите на А се наречени ?кандидати за решени?а“ или допустливи решени?а.

Функци?ата f се именува на пове?е начини, функци?а на целта, функци?а на загуба, функци?а на трошоци (минимизаци?а), алатка функци?а, функци?а на добивка (максимизаци?а) или во некои поли?а, енергетска функци?а, функци?а на енерги?ата. Допустливото решение што ?а минимизира (или максимизира, ако тоа е целта) функци?ата на целта е нареченo оптимaлно решение.

Во математиката, конвенционалните проблеми на оптимизаци?а вообичаено се наведени во условите изразени преку термини за минимизаци?а. Поопшто земено, доколку и функци?ата на целта и множеството на допустливи решени?а не се конвексни во минимизацискиот проблем, можат да посто?ат неколку локални минимуми. Локалниот минимум x* е дефиниран како точка за ко?а постои неко? бро? δ > 0 така што за сите x за коишто:

    || x-x* || ≤ δ 

Неравенството:

    f(x* ) ≤ f(x)

важи, односно, за неко?а околина околу x* сите вредности на функци?ата се поголеми или еднакви на функциската вредност на таа точка. Локалните максимуми се дефинираат на сличен начин.

Додека локалниот минимум е барем исто толку добар колку и околните точки, глобалниот минимум е барем исто толку добар како и секо?а допустлива точка. За испакнат проблем, ако постои локален минимум ко? е внатрешен (не е на кра?от од множеството на допустливи точки) то? е исто така и глобален минимум, но неиспакнатиот проблем може да има пове?е од еден локален минимум од кои не мора сите да бидат глобални минимуми.

Голем бро? на алгоритми предложени за решава?е на неконвексни проблеми вклучува??и ги на?големиот бро? на комерци?ално достапни решeни?а не можат да направат разлика поме?у локалното оптимално решение, па ?е го третираат претходното како вистинско решение за првобитниот проблем. Глобалното оптимизира?е е гранка на применетата математика и бро?чената анализа ко?а се занимава со разво?от на детерминистичките алгоритми коишто се способни да гарантираат конвергенци?а во одредено време на вистинското решение на неиспакнатиот проблем.

Оптимизациските проблеми често се изрази со специ?ална нотаци?а

Вредноста на минимумот и максимумот на функци?ата: Да ?а земеме предвид следнава формула:$min_{x\in R}(x^{2}+1)$

Ова ?а означува минималната вредност на функци?ата на целта $x^{2}+1$, кога се избира x од множество на реални броеви. Минималната вредност во ово? случа? е 1, ако x=0.

Слично, формулата :$min_{x\in R}2x$

?а бара максимална вредност на функци?ата на целта 2x, каде што x може да биде ко? било реален бро?. Во ово? случа? нема таква максимална вредност затоа што функци?ата на целта е неограничена, така што одговорот е ?бесконечност“ или ?недефиниранa вредност“.

Оптимални влезни (input) аргументи:

Да ?а разгледаме следнава формула:

$\arg min_{x\in (-\infty ,-1]}x^{2}+1$

Односно еквивалентно на:

${\displaystyle \arg min_{x}x^{2}+1}$ , така што : $x\in (-\infty ,-1]$

Ова ?а претставува вредноста (или вредностите) на аргументот x во интервалот $(-\infty ,-1]$ што ?а минимизира (или ги минимизира) функци?ата на целта $x^{2}+1$ (вистинската на?мала вредност на функци?ата не е она што проблемот го бара). Во ово? случа? одговорот е x= -1, поради тоа што x= 0 е невозможно односно не припа?а на даденото множество. Слично,

${\displaystyle \arg max_{x\in [5,-5],y\in R}x\cos(y)}$

или еквивалентно

${\displaystyle {\displaystyle \arg max_{x,y}x\cos(y)}}$ ; така што $x\in [5,-5],y\in R$

го претставува подредениот пар (или паровите) (x,y), ко? ?а максимизира (или ги максимизира) вредноста на функци?ата на целта xcos(y), со зададените ограничува?а х да лежи во интервалот [-5,5], (повторно вистинската максимална вредност на функци?ата во формулава не е важна). Во ово? случа?, решени?ата се подредените парови $(5,2k\Pi )$ и $(-5,(2k+1)\Pi )$ каде што k прима вредност на цел бро?.

Истори?а

Ферма и Лагранж пронашле формула заснована на пресметки за идентификаци?а на оптимумот, додека ?утн и Гаус предложиле итеративни методи за придвижува?е кон оптимумот.

Терминот линеарно програмира?е за одредени оптимизациски случаи се должи на ?ор? Б. Данциг, иако голем дел од теори?ата била развиена од страна на Леонид Канторович 1939 г. (Програмира?ето во ово? контекст не се однесува на комп?утерско програмира?е, туку потекнува од употребата на зборот програмира?е од страна на американската во?ска што се однесува на предложените тренинзи за логичко распоредува?е кои Данциг ги проучувал во тоа време). Данциг го об?авил ?симплексниот алгоритам“ во 1947 година, а ?он фон Но?ман ?а развил ?теори?ата за дуалност“ истата година.

Поважни гранки

• Конвексното програмира?е ги проучува случаите кога функци?ата на целта е конвексна (минимизаци?а) или вдлабната (максимизаци?а) и допустливото множество е конвексно. Ова може да се разгледува и како специ?ален случа? на нелинеарно програмира?е или како генерализаци?а на линеарното или конвексното квадратно програмира?е.
• Линеарното програмира?е како тип на конвексно програмира?е, ги проучува случаите во кои функци?ата на целта f е линеарна и ограничува?ата се дадени со линеарни равенства и неравенства. Таквото множество е наречено полихедрон или политоп ако е ограничено.
• Конусното програмира?е од втор ред вклучува одредени типови на квадратно програмира?е.
• Семидефинитното програмира?е е подгранка на конвексната оптимизаци?а каде основните променливи се семидефинитни матрици. Тоа е генерализаци?а на линеарното и конвексното квадратно програмира?е.
• Геометриското програмира?е е техника со ко?а ограничува?ата во облик на неравенства изразени како полиноми и ограничува?а во облик на равенства изразени како мономи, да можат да се трансформираат во конвексна програма.
• Целобро?ното програмира?е го проучува линеарното програмира?е во кое некои или сите променливи се ограничени да примаат целобро?ни вредности. Ова не е конвексно, и обично е многу потешко отколку вообичаеното линеарно програмира?е.
• Квадратното програмира?е е такво што и дозволува на функци?ата на целта има квадратни членови, додека допустливото множество мора да биде одредено со линеарни равенстава и неравенства. За специфични форми на квадратните членови односно, ова е тип на конвексно програмира?е.
• Дробно-рационалното програмира?е ?а проучува оптимизаци?ата на количникот (односот) на две нелинеарни функции. Специ?алната класа на вдлабнати дробно-рационални програми може да биде трансформирана во испакнат оптимизациски проблем.
• Нелинеарното програмира?е ги проучува општите случaи во кои функци?ата на целта содржи нелинеарни делови. Ова може, а и не мора да биде конвексна програма. Главно, дали програмата е конвексна или не вли?ае врз потешкотиите при решава?ето на проблемот.
• Стохастичкото програмира?е ги проучува случаите во кои некои од ограничува?ата или параметрите зависат од случа?ни променливи.
• Робусното програмира?е е, како и стохастичкото, обид да се опфатат неодреденостите во податоците кои подлежат на оптимизацискиот проблем. Робусната оптимизаци?а тежнее да на?де решени?а што се точни за сите можни реaлизации на променливите.
• Комбинаторската оптимизаци?а се занимава со проблемите каде што множеството од возможни решени?а е дискретно, или може да се сведе на едно дискретно множество од решени?а.
• Стохастичката оптимизаци?а користи случа?на функци?а на пребарува?е или случа?ни влезни податоци во процесот на пребарува?е.
• Бескра?но-димензионалната оптимизаци?а проучува случаи кога множеството допустливи решени?а е подмножество на бескра?но-димензионалниот простор, како што е просторот на функциите.
• Евристиката и метаевристиката не тргнуваат од претпоставките дека проблемот може да биде оптимизиран. Обично, евристиката не гарантира дека ?е се изна?де некое оптимално решение. Од друга страна, евристиката се користи за да се на?дат приближните решени?а на многу комплицирани проблеми.
• Сатисфакци?а на ограничува?а проучува случаи во кои функци?ата на целта f е константна (ова се користи во вештачката интелигенци?а, особено во автоматизираното размислува?е).
• Програмира?е со ограничува?а е парадигма за програмира?е при што односите ме?у променливите се сведуваат во форма на ограничува?а.
• Динамичното програмира?е го проучува случа?от во ко? оптималната стратеги?а е заснована на деле?е на проблемот во помали подгрупи-потпроблеми. Равенките коишто ги об?аснуваат врските ме?у овие потпроблеми се викаат Белманови равенки.
• Математичкото програмира?е со урамнотежени ограничува?а е всушност она во кое ограничува?ето вклучува неравенства со вари?ации или комплементарност.

Мултимодална оптимизаци?а

Проблемите на оптимизаци?а често се мултимодални и тоа е затоа што тие поседуваат пове?е добри решени?а. Тие сите би можеле да бидат глобално добри (?а имаат истата вредност на функци?ата на трошоци) или може да има мешавина на глобално добри и локално добри решени?а. Добива?ето на сите (или барем некои) пове?екратни решени?а е целта на мултимодалниот оптимизатор.

Класичните оптимизациски техники поради нивниот итеративен пристап не функционираат на задоволителен начин кога тие се користат за да се доби?ат пове?екратни решени?а, биде??и то? не гарантира дека ?е се доби?ат различни решени?а дури и со различни по?довни точки во пове?е тестира?а на алгоритмот.

Еволутивните алгоритми, сепак, се многу популарен пристап за добива?е на пове?екратни решени?а во мултимодална задача на оптимизаци?а.

Класификаци?а на критичните точки и екстреми

Физибилити проблем

Физибилити проблемот, или поточно проблемот на допустливост, е проблемот на пронао?а?е на кое било допустливо решение воопшто, без оглед на неговата вредност на функци?ата на целта. Ова може да се смета како посебен случа? на математичката оптимизаци?а каде што вредноста на функци?ата на целта е иста за секое решение, и на то? начин секое решение е оптимално.

Многу оптимизациски алгоритми треба да започнат од допустлива точка. Еден начин да се добие таква точка е да се олабават физибилити условите преку користе?е на слаба променлива, така што ко?а било по?довна точка да е допустлива. Потоа се намалува слабата променлива додека вредноста стане нула или негативна.

Постое?е

Теоремата на екстремна вредност на Карл Ва?ерштрас наведува дека непрекината реално-вредносна функци?а на компактно множество ?а достигнува сво?ата максимална и минимална вредност.

Потребни услови за оптималност

Една од теоремите на Ферма наведува дека на?големата вредност на проблеми без ограничува?е се нао?а во стационарните точки, каде што првиот извод или градиент на функци?ата на целта е нула. Поопшто, тие може да се на?дат во критични точки, каде што првиот извод или градиент на функци?ата на целта е нула или е недефиниран, или на границата на поставениот домен. Равенката (или множеството на равенки) ко?а наведува дека првиот извод е еднаков на нула во внатрешен оптимум се нарекува ?состо?ба од прв ред“ или збир на услови од прв ред.

Оптимум на проблемите ограничени со равенства може да се на?де преку Лагранжовиот метод на мултупликатор. Оптимум на проблемите ограничени со равенства или неравенства може да се на?де со помош на Каруш-Кун-Такер условите.

Доволни услови за оптималност

Додека тестот на првиот извод идентификува точки кои би можеле да се екстремни, ово? тест не прави разлика поме?у точка што е минимум од точка што е максимум или точка ко?а не претставува ниту минимум ниту максимум. Кога функци?ата на целта е двапати диференци?абилна, овие случаи можат да се разликуваат преку проверка на вториот извод или матрицата на вториот извод (наречена Хесеова матрица) ка? проблеми без ограничува?а, или матрицата на вториот извод на функци?а на целта и ограничува?ата наречена ограничена Хесеова матрица ка? проблеми со ограничува?е. Условите кои ги разликуваат максимумот или минимумот од другите стационарни точки се нарекуваат ?услови од втор ред“. Ако решението кое е кандидат ги исполнува условите од прв ред, тогаш исполнува?ето на условите од втор ред е доволно да се утврди барем локалната оптималност.

Чувствителност и континуитет на оптимумот

Писмо - Теоремата опишува како вредноста на оптимално решение се менува кога основниот параметар ?е се промени. Процесот на пресметува?е на оваа промена се нарекува компаративна статика.

Теоремата за максимум на Клод Берж (1963) ?а опишува непрекинатоста на оптималното решение како функци?а од основните (клучните) параметри.

Пресметува?е на оптимизаци?а

За проблеми без ограничува?е со двократно диференци?абилни функции, може да се на?дат некои критични точки со нао?а?е на точките каде градиентот на функци?ата на целта е нула (т.е. стационарните точки). Поопшто со нула субградиент се потврдува дека е на?ден локалниот минимум за минимизира?е на проблемите за конвексни функции и други локални функции на Липшиц.

Понатаму, критичните точки може да се класифицираат со користе?е на дефинитноста на Хесеовата матрица. Ако Хесеовата матрица е позитивно определена во критичната точка, тогаш точката е локален минимум; ако Хесеовата матрица е негативно определена, тогаш точката е локален максимум; Конечно ако е неопределена, тогаш точката е неко? вид на седло (на средна) точка. Проблемите со ограничува?е често може да се претворат во проблеми без ограничува?е со помош множителите на Лагранж. Лагранж релаксаци?ата може да обезбеди приближни решени?а за тешки проблеми со ограничува?е.

Кога функци?ата на целта е конвексна, тогаш секо? локален минимум, исто така, ?е биде и глобален минимум. Посто?ат ефикасни бро?чени техники за минимизира?е на испакнатите функции, како што се методите со внатрешна точка.

Tехники за пресметува?е на оптимизаци?а

За решава?е на проблеми, истражувачите можат да ги користат алгоритмите кои завршуваат во конечен бро? на чекори, или итеративни методи кои се конвергираат кон решението (за неко?а одредена класа на проблеми), или евристички кои можат да овозможат приближни решени?а за одредени проблеми иако нивните итеративни не мора да се совпа?аат.

Оптимизациски алгоритми

• Симплексен алгоритам од ?ор? Данциг, наменет за линеарно програмира?е
• Проширува?е на симплекс алгоритмот, за квадратно програмира?е и за линеарно-дробно-рационално програмира?е
• Вари?анти на симплекс алгоритам кои се особено погодни за оптимизаци?а на мрежа
• Комбинаторни алгоритми

Надворешни врски

• COIN-OR—Computational Infrastructure for Operations Research
• Decision Tree for Optimization Software Links to optimization source codes
• Global optimization Архивирано на 28 декември 2008 г.
• Mathematical Programming Glossary Архивирано на 28 март 2010 г.
• Mathematical Programming Society
• NEOS Guide Архивирано на 1 март 2009 г. currently being replaced by the NEOS Wiki Архивирано на 22 август 2002 г.
• Optimization Online A repository for optimization e-prints
• Optimization Related Links
• Convex Optimization I Архивирано на 10 април 2015 г. EE364a: Course from Stanford University
• Convex Optimization – Boyd and Vandenberghe Book on Convex Optimization
• Book and Course on Optimization Methods for Engineering Design
• Mathematical Optimization in Operations Research from the Institute for Operations Research and the Management Sciences (INFORMS)