Optimisació en restriccions

En l'optimisació matemàtica, la optimisació en restriccions és el procés d'optimisació d'una funció objectiu sobre algunes variables en restriccions en les mateixes. La funció objectiu és, o be una funció de cost o funció d'energia que deu ser minimisada, o una funció de recompensa o funció d'utilitat, que ha de ser maximizar. Les restriccions poden ser tant restriccions dures que establixen condicions per a les variables que es requerixen per a estar satisfeta, o restriccions blanes que tenen alguns valors de les variables que estan penalisats en la funció objectiu si, i basats en la mida en que, les condicions en les variables no són satisfet.

Forma general

Un problema general de minimisació restringida es pot escriure com seguix:

$\begin{array}{cccc}\min & & f(𝐱)& \\ \mathrm{s}\mathrm{u}\mathrm{j}\mathrm{e}\mathrm{t}\mathrm{o}\mathrm{a}& & g_i(𝐱)=c_i& \text{for }i=1,\dots ,n\text{Restricciones de igualdad}\\ & & h_j(𝐱)\geqq d_j& \text{for }j=1,\dots ,m\text{Restricciones de desigualdad}\end{array}$

a on $g_i(𝐱)=c_i$ per a $i=1,\dots ,n$ i $h_j(𝐱)\ge d_j$ per a $j=1,\dots ,m$ són les restriccions que es requerixen per a satisfer el resultat; estes es diuen restriccions dures.

En alguns problemes, a sovint cridats problemes d'optimisació en restriccions, la funció objectiu és en realitat la suma de funcions de cost, cada una penalisa la mida (si l'hi ha) en la que una restricció blana (una restricció que es preferix pero no es requerix per a ser satisfet) és violada.

Métodos de solució

Molts algoritmes d'optimisació en restriccions es poden adaptar al cas sense restriccions, a sovint a través de l'us d'un método de penalisacions. No obstant, els passos de busca obtingudes pel método sense restriccions poden ser inacceptables per al problema restringida, lo que du a una falta de convergència. Açò es coneix com l'efecte Maratos.

Restriccions d'igualtat

Si el problema restringit només té restriccions d'igualtat, el método dels multiplicadors de Lagrange pot ser utilisat per a convertir-ho en un problema sense restriccions el número de les quals de variables és el número original de les variables més el número original de restriccions d'igualtat. Alternativament, si les restriccions són totes les restriccions d'igualtat i són llineals, que es poden resoldre per a algunes de les variables en térmens dels atres, i l'antiga poden ser substituïts de la funció objectiu, deixant un problema sense restriccions en un número menor de variables.

Restriccions de desigualtat

En restriccions de desigualtat, el problema pot ser caracterisat en térmens de les condicions de Karush-Kuhn-Tucker, en la que els problemes poden ser resolts.

Programació llineal

Si la funció objectiu i totes les restriccions són llineals, llavors el problema és problema de programació llineal. Açò es pot resoldre pel método simplex. Generalment funciona en temps polinomial en el tamany del problema, pero no es garantisa, o per mig de métodos de punts interiors que es garantisa que funcionen en temps polinomial.

Programació quadràtica

Si totes les restriccions dures són llineals, pero la funció objectiu és quadràtica, el problema és un problema de programació quadràtic . Encara es pot resoldre en temps polinomial pel método de l'elipsoide si la funció objectiu és convexa ; de lo contrari, el problema és NP complet .

Problemes d'optimisació de restricció

Branca i nugat

L'optimisació de restriccions pot resoldre's per mig d'algoritmes de Ramificació i poda. Estos són algoritmes de back-tracking que almagasenen el cost de la millor solució trobada durant l'eixecució i l'usen per a evitar part de la busca. Més precisament, cada volta que l'algoritme troba una solució parcial que no es pot estendre per a formar una solució de millor cost que el millor cost almagasenat, l'algoritme retrocedix, en lloc d'intentar estendre esta solució.

Suponent que el cost es minimise, l'eficiència d'estos algoritmes depén de cóm s'evalua el cost que es pot obtindre en estendre una solució parcial. De fet, si l'algoritme pot donar marcha arrere des d'una solució parcial, part de la busca s'omet. Quant menor siga el cost estimat, millor serà l'algoritme, ya que és més provable que un menor cost estimat siga menor que el millor cost de solució trobat fins ara.

Per un atre costat, este cost estimat no pot ser menor que el cost efectiu que es pot obtindre estenent la solució, ya que de lo contrari l'algoritme podria retrocedir mentres existix una solució millor que la millor fins ara. Com a resultat, l'algoritme requerix un llímit superior en el cost que es pot obtindre en estendre una solució parcial, i este llímit superior deu ser lo més chicotet possible.

Una variació d'este enfocament, cridat método de Hansen, usa métodos d'interval. Implementa intrínsecament restriccions rectangulars.

Funcions de llímit de primera elecció

Una forma d'evaluar este llímit superior per a una solució parcial és considerar cada restricció blana per separat. Per a cada restricció suau, se supon el valor màxim possible per a qualsevol assignació a les variables no assignades. La suma d'estos valors és un llímit superior perque les restriccions blanes no poden assumir un valor més alt. És exacte perque els valors màxims de restriccions suaus poden derivar d'evaluacions diferents: una restricció suau pot ser màxima per a $x=b$. mentres que una atra restricció és màxima per a $x=a$.