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í: és convexa encara que no sigui derivable a l'origen, 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 \leq 0$:

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

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

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

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

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 és negativa, de manera que la funció és 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 - 1 \leq 0$:

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

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

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

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

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 $12x^{2}\geq 0$, 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 oscil·la 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 - 3 \leq 0$:

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

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

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

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

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 $-e^{-x} < 0$, de manera que la funció és 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 - 4 \leq 0$:

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

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

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

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