Simulacre d'examen 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 val $2 > 0$ a tot arreu, de manera que la funció és convexa.

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 - 2 \leq 0$:

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

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

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

$\mu = 2(5-2) = 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.

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-7) + \mu = 0,\qquad \mu \geq 0,\qquad \mu x = 0,\qquad x\leq0$

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

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

$\mu = 2(7-0) = 14 \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-9) + \mu = 0,\qquad \mu \geq 0,\qquad \mu(x - 1) = 0,\qquad x\leq1$

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

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

$\mu = 2(9-1) = 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.

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

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

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

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

$\mu = 2(12-10) = 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-20) + \mu = 0,\qquad \mu \geq 0,\qquad \mu(x - 5) = 0,\qquad x\leq5$

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

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

$\mu = 2(20-5) = 30 \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-13) + \mu = 0,\qquad \mu \geq 0,\qquad \mu(x - 2) = 0,\qquad x\leq2$

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

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

$\mu = 2(13-2) = 22 \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.