Optimisasyong matematikal

Grapo ng paraboloid na ibinigay ng f(x,y) = -(x²+y²)+4. Ang global na maksimum sa (0,0,4) ay tinutukoy ng isang pulang tuldok.

Sa matematika, agham komputasyonal, o agham ng pangangasiwa, ang matematikal na optimisasyon o matemetikal na pagpoprograma, o optimisasyon ay tumutukoy sa pagpili ng pinakamahusay na elemento mula sa isang pangkat ng mga magagamit na alternatibo. Sa pinakasimpleng kaso, ang problemang optimisasyon ay binubuo ng pag-ma-maksima o pag-mi-minima ng isang real na punsiyon sa pamamagitan ng sistematikong pagpili ng mga halagang input sa loob ng isang pinapayagang pangkat at kukwentahin ang halaga ng punsiyon. Ang paglalahat ng teoriyang optimisasyon at mga paraan sa ibang mga pormulasyon ay binubuo ng isang malaking sakop ng nilalapat na matematika. Sa mas pangkalahatan, ang optimisasyon ay binubuo ng paghahanap ng "pinakamahusay na magagamit" na mga halaga ng isang obhektibong punisyon sa isang ibinigay na inilarawang sakop(domain) kabilang ang iba't ibang mga uri ng obhektibong punsiyon at iba't ibang mga uri ng sakop.

Mga problemang optimisasyon

Ang isang problemang optimisasyon ay maaaring ilarawan sa sumusunod na paraan

Ibinigay: ang isang punsiyon na f : A $\to$ R mula sa isang pangkat na A sa mga real na bilang

Hinanap: ang isang elementong x₀ sa A sa gayong ang f(x₀) ≤ f(x) para sa lahat ng x sa A ("minimisasyon") o sa paraang ang f(x₀) ≥ f(x) para sa lahat ng x sa A ("maksimisasyon").

Ang gayong pormulasyon ay tinatawag na optimisasyong problema o matematikal na pagpoprogramang problema. Maraming mga praktikal at teoretikal na problema ay maaaring imodelo sa pangkalahatang balangkas na ito. Ang mga problemang pinormula gamit ang paraang ito sa mga larangan ng pisika at bisyon ng kompyuter ay maaaring tumukoy sa paraang gaya ng enerhiyang minimisasyon na tumutukoy sa halaga ng punsiyong f bilang kumakatawan sa enerhiya ng sistemang minomodelo. Sa karaniwan, ang A ay isang pang-ilalim na pangkat ng espasyong Euclidean na Rⁿ, na kalimitang tinutukoy ng isang pangkat ng mga pagtatakda, mga ekwalidad at inekwalidad na kailangang sapatan ng mga kasapi ng A. Ang sakop na A ng f ay tinatawag na espasyo ng paghahanap o pangkat ng pagpipilian samantalang ang mga elemento ng A ay tinatawag na mga kandidatong solusyon o mga magagawang solusyon(feasible solutions). Ang punsiyong f ay tinatawag na obhektibong punsiyon, halagang punsiyon(cost function/minimization), utilidad na punsiyon(utilitiy function/maximization) sa ilang mga larangan, enerhiyang punsiyon o enerhiyang punsiyonal. Ang isang magagawang solusyon na nag-mi-minima(o nag-mamaksima kung ito ang layunin) ng obhektibong punsiyon ay tinatawag na solusyong optimal. Sa konbensiyon, ang pamantayang anyo ng isang problemang optimisasyon ay isinasaad sa mga termino ng minimisasyon. Sa pangkalahatan, malibang ang parehong obhektibong punsiyon at ang magagawang rehiyon ay konbeks sa isang problemang minimisasyon, maaaring mayroon ilang mga lokal na minima kung saan ang isang lokal na minimum na x^* ay inilalarawan bilang isang punto kung saan may umiiral na isang δ > 0 upang para sa lahat ng x sa gayong ang

$\|\mathbf {x} -\mathbf {x} ^{*}\|\leq \delta ;\,$

ang ekspresyong

$f(\mathbf {x} ^{*})\leq f(\mathbf {x} )$

ay totoo. Ang ibig sabihin nito, sa isang rehiyon sa palibot ng x^*, ang lahat ng mga halaga ng punsiyon ay mas mataas o katumbas ng halaga sa puntong iyon. Ang lokal na maksima ay inilalarawan sa parehong paraan. Ang isang malaking bilang ng mga algoritmo sa paglutas ng mga hindi konbeks na problema kabilang ang karamihan ng mabibiling mga tagalutas(solvers) ay walang kakayahan na magtangi sa pagitan ng isang lokal na optimal na mga solusyon at tiyak na mga optimal na solusyon at tinatrato ang mga lokal na optimal na solusyon bilang mga aktuwal na solusyon sa orihinal na problema. Ang sangay ng nilalapat na matematika at numerikal na analisis na umuukol sa pagbuo ng deterministikong mga algoritmo na may kakayahan sa paggagarantiya ng pagtatagpo(convergence) sa may hangganang panahon sa aktuwal na optimal na solusyon ng isang hindi-konbeks na problema ay tinatawag na global na optimisasyon.

Notasyon

Ang mga problemang optimisasyon ay kalimitang inihahayag ng espesyal na notasyon. Ang mga sumusunod ang ilang mga halimbawa.

Minimum at maksimum na halaga ng isang punsiyon

Ituring ang sumusunod na notasyon:

$\min _{x\in \mathbb {R} }\;(x^{2}+1)$

Ito ay tumutukoy sa minimum na halaga ng obhektibong punsiyong x²$+1$ kapag pipili ng x mula sa pangkat ng mga real na bilang $\mathbb {R}$. Ang minimum na halaga sa kasong ito ay $1$, na umiiral sa $x=0$.

Katulad nito, ang notasyong

$\max _{x\in \mathbb {R} }\;2x$

ay humihingi ng maksimum na halaga ng obhektibong punsiyong 2x kung saan ang x ay maaaring anumang real na bilang. Sa kasong ito, walang gayong maksimum dahil ang obhektibong punsiyon ay hindi tinatakdaan kaya ang sagot ay inpinidad o "hindi matukoy".

Optimal na mga argumentong input

Pangunahing artikulo: Arg max

Ituring ang sumusunod na notasyon:

${\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1,$

o ang katumbas na

${\underset {x}{\operatorname {arg\,min} }}\;x^{2}+1,\;{\text{subject to:}}\;x\in (-\infty ,-1].$

Ito ay kumakatawan sa halaga o mga halaga ng argumentong x sa interbal na $(-\infty ,-1]$ na nagmi-minima ng obhektibong punsiyong x² + 1 (ang aktuwal na minimum na halaga ng punsiyong iyon ay hindi ang hinihingi ng problema). Sa kasong ito, ang sagot ay x = -1, dahil ang x = 0 ay hindi magagawa(infeasible) na ang ibig sabihin ay kabilang sa magagawang pangkat. Sa katulad na paraan.

${\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos(y),$

ang katumbas na

${\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos(y),\;{\text{subject to:}}\;x\in [-5,5],\;y\in \mathbb {R} ,$

ay kumakatawan sa pares na $(x,y)$ na nag-mamaksima ng halaga ng obhektibong punsiyong $x\cos(y)$ na may dinagdaga ng pagtatakdang ang x ay nasa interbal na $[-5,5]$ (muli, ang aktuwal na halagang maksimum ng ekspresyon ay hindi mahalaga). Sa kasong ito, ang mga solusyon ang pares ng anyong (5, 2kπ) at (−5,(2k+1)π) kung saan ang k ay sumasaklaw sa ibabaw ng lahat ng mga intedyer. Ang arg min at arg max ay minsang isinulat na argmin at argmax at tumatayo para sa argument of the minimum at argument of the maximum.