Exercicis de convexitat i KKT

El criteri. Per a una funció de classe $C^{2}$, ser convexa equival que la segona derivada sigui no negativa a tot el domini, i ser còncava que sigui no positiva.

Aquí: la segona derivada $6x$ canvia de signe, de manera que la funció és ni convexa ni còncava.

Els dos errors que cal evitar. El primer és comprovar el signe en un punt i generalitzar: la condició és global sobre el domini. El segon és oblidar quin és el domini: la funció inversa és convexa per a valors positius i còncava per a negatius, i no té sentit parlar-ne sense dir-ho.

Per què importa tant. Amb convexitat, tot mínim local és global i les condicions de primer ordre es converteixen en un certificat. Sense ella, trobar un punt crític no demostra pràcticament res.

Pas 1 — les condicions. Amb $g(x) = x \leq 0$:

$2(x-6) + \mu = 0,\qquad \mu \geq 0,\qquad \mu x = 0,\qquad x\leq0$

Pas 2 — cas inactiu ($\mu = 0$). L'estacionarietat donaria $x = 6$, que no compleix $x\leq0$. Descartat.

Pas 3 — cas actiu ($x = 0$). L'estacionarietat dona

$\mu = 2(6-0) = 12 \geq 0$

El signe és correcte, o sigui que totes les condicions es compleixen.

Per què això certifica l'òptim global. L'objectiu i la restricció són convexos, i en aquest cas complir les KKT és suficient per a optimalitat global. Sense convexitat, les KKT només donarien un candidat.

Interpretació del multiplicador: és la taxa a què milloraria l'òptim si afluixessis la restricció una unitat.

Pas 1 — les condicions. Amb $g(x) = x - 1 \leq 0$:

$2(x-6) + \mu = 0,\qquad \mu \geq 0,\qquad \mu(x - 1) = 0,\qquad x\leq1$

Pas 2 — cas inactiu ($\mu = 0$). L'estacionarietat donaria $x = 6$, que no compleix $x\leq1$. Descartat.

Pas 3 — cas actiu ($x = 1$). L'estacionarietat dona

$\mu = 2(6-1) = 10 \geq 0$

El signe és correcte, o sigui que totes les condicions es compleixen.

Per què això certifica l'òptim global. L'objectiu i la restricció són convexos, i en aquest cas complir les KKT és suficient per a optimalitat global. Sense convexitat, les KKT només donarien un candidat.

Interpretació del multiplicador: és la taxa a què milloraria l'òptim si afluixessis la restricció una unitat.

Pas 1 — les condicions. Amb $g(x) = x - 2 \leq 0$:

$2(x-6) + \mu = 0,\qquad \mu \geq 0,\qquad \mu(x - 2) = 0,\qquad x\leq2$

Pas 2 — cas inactiu ($\mu = 0$). L'estacionarietat donaria $x = 6$, que no compleix $x\leq2$. Descartat.

Pas 3 — cas actiu ($x = 2$). L'estacionarietat dona

$\mu = 2(6-2) = 8 \geq 0$

El signe és correcte, o sigui que totes les condicions es compleixen.

Per què això certifica l'òptim global. L'objectiu i la restricció són convexos, i en aquest cas complir les KKT és suficient per a optimalitat global. Sense convexitat, les KKT només donarien un candidat.

Interpretació del multiplicador: és la taxa a què milloraria l'òptim si afluixessis la restricció una unitat.

Pas 1 — les condicions. Amb $g(x) = x - 3 \leq 0$:

$2(x-6) + \mu = 0,\qquad \mu \geq 0,\qquad \mu(x - 3) = 0,\qquad x\leq3$

Pas 2 — cas inactiu ($\mu = 0$). L'estacionarietat donaria $x = 6$, que no compleix $x\leq3$. Descartat.

Pas 3 — cas actiu ($x = 3$). L'estacionarietat dona

$\mu = 2(6-3) = 6 \geq 0$

El signe és correcte, o sigui que totes les condicions es compleixen.

Per què això certifica l'òptim global. L'objectiu i la restricció són convexos, i en aquest cas complir les KKT és suficient per a optimalitat global. Sense convexitat, les KKT només donarien un candidat.

Interpretació del multiplicador: és la taxa a què milloraria l'òptim si afluixessis la restricció una unitat.

Pas 1 — les condicions. Amb $g(x) = x - 4 \leq 0$:

$2(x-6) + \mu = 0,\qquad \mu \geq 0,\qquad \mu(x - 4) = 0,\qquad x\leq4$

Pas 2 — cas inactiu ($\mu = 0$). L'estacionarietat donaria $x = 6$, que no compleix $x\leq4$. Descartat.

Pas 3 — cas actiu ($x = 4$). L'estacionarietat dona

$\mu = 2(6-4) = 4 \geq 0$

El signe és correcte, o sigui que totes les condicions es compleixen.

Per què això certifica l'òptim global. L'objectiu i la restricció són convexos, i en aquest cas complir les KKT és suficient per a optimalitat global. Sense convexitat, les KKT només donarien un candidat.

Interpretació del multiplicador: és la taxa a què milloraria l'òptim si afluixessis la restricció una unitat.

Pas 1 — les condicions. Amb $g(x) = x - 5 \leq 0$:

$2(x-6) + \mu = 0,\qquad \mu \geq 0,\qquad \mu(x - 5) = 0,\qquad x\leq5$

Pas 2 — cas inactiu ($\mu = 0$). L'estacionarietat donaria $x = 6$, que no compleix $x\leq5$. Descartat.

Pas 3 — cas actiu ($x = 5$). L'estacionarietat dona

$\mu = 2(6-5) = 2 \geq 0$

El signe és correcte, o sigui que totes les condicions es compleixen.

Per què això certifica l'òptim global. L'objectiu i la restricció són convexos, i en aquest cas complir les KKT és suficient per a optimalitat global. Sense convexitat, les KKT només donarien un candidat.

Interpretació del multiplicador: és la taxa a què milloraria l'òptim si afluixessis la restricció una unitat.

Pas 1 — les condicions. Amb $g(x) = x \leq 0$:

$2(x-10) + \mu = 0,\qquad \mu \geq 0,\qquad \mu x = 0,\qquad x\leq0$

Pas 2 — cas inactiu ($\mu = 0$). L'estacionarietat donaria $x = 10$, que no compleix $x\leq0$. Descartat.

Pas 3 — cas actiu ($x = 0$). L'estacionarietat dona

$\mu = 2(10-0) = 20 \geq 0$

El signe és correcte, o sigui que totes les condicions es compleixen.

Per què això certifica l'òptim global. L'objectiu i la restricció són convexos, i en aquest cas complir les KKT és suficient per a optimalitat global. Sense convexitat, les KKT només donarien un candidat.

Interpretació del multiplicador: és la taxa a què milloraria l'òptim si afluixessis la restricció una unitat.

Pas 1 — les condicions. Amb $g(x) = x - 1 \leq 0$:

$2(x-10) + \mu = 0,\qquad \mu \geq 0,\qquad \mu(x - 1) = 0,\qquad x\leq1$

Pas 2 — cas inactiu ($\mu = 0$). L'estacionarietat donaria $x = 10$, que no compleix $x\leq1$. Descartat.

Pas 3 — cas actiu ($x = 1$). L'estacionarietat dona

$\mu = 2(10-1) = 18 \geq 0$

El signe és correcte, o sigui que totes les condicions es compleixen.

Per què això certifica l'òptim global. L'objectiu i la restricció són convexos, i en aquest cas complir les KKT és suficient per a optimalitat global. Sense convexitat, les KKT només donarien un candidat.

Interpretació del multiplicador: és la taxa a què milloraria l'òptim si afluixessis la restricció una unitat.

Pas 1 — les condicions. Amb $g(x) = x - 2 \leq 0$:

$2(x-10) + \mu = 0,\qquad \mu \geq 0,\qquad \mu(x - 2) = 0,\qquad x\leq2$

Pas 2 — cas inactiu ($\mu = 0$). L'estacionarietat donaria $x = 10$, que no compleix $x\leq2$. Descartat.

Pas 3 — cas actiu ($x = 2$). L'estacionarietat dona

$\mu = 2(10-2) = 16 \geq 0$

El signe és correcte, o sigui que totes les condicions es compleixen.

Per què això certifica l'òptim global. L'objectiu i la restricció són convexos, i en aquest cas complir les KKT és suficient per a optimalitat global. Sense convexitat, les KKT només donarien un candidat.

Interpretació del multiplicador: és la taxa a què milloraria l'òptim si afluixessis la restricció una unitat.