Математичка оптимизација

Графиконот на параболоид даден со z = f (x, y) = - (x² + y²) + 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)