1 votos

Convención de signos de los multiplicadores KKT

Todos sabemos que si tenemos un problema de optimización de la forma general:

$$ \min f(x) $$

sujeto a: $$\begin{align} h(x) &= 0 \\ g(x) &\le 0. \end{align}$$

Entonces, tenemos un vector de multiplicadores, llamémoslo $s$ asociado a las restricciones de igualdad y un vector de multiplicadores asociado a las restricciones de desigualdad, llamémoslo $d$ .

Las condiciones KKT requieren (aparte de muchas otras cosas) que los componentes de d satisfagan la condición de no negatividad: $d\ge 0$

Mi pregunta es: ¿depende esta condición de la estructura del problema? de si tengo un problema mínimo o máximo? Y si es así ¿de qué depende?

Gracias, señor,

Mari

2voto

jms Puntos 6

Depende de la estructura del problema. Veamos qué es lo que queremos conseguir. En su ejemplo, queremos minimizar una función $f(x)$ sujeta a las restricciones $h(x) = 0$ y $g(x) \le 0$ .

Cuando introducimos los multiplicadores, formamos la expresión $$ L(x, s, d) = f(x) + s\cdot h(x) + d \cdot g(x). $$ Pienso en la optimización como un juego con un adversario: Yo controlo la variable original $x$ y quiero minimizar esta expresión (De hecho quiero minimizar la función $f(x)$ sujeto a las restricciones, pero el juego garantiza que es equivalente). El adversario controla los multiplicadores introducidos $s$ y $d$ y está intentando maximizar la expresión.

La forma en que diseñamos este juego es que cada vez que yo infrinjo las restricciones, ¡el adversario puede ganar haciendo que su objetivo sea infinito! En concreto, si selecciono $x$ para lo cual $g(x) >0$ entonces el oponente puede seleccionar $d \rightarrow \infty$ y conducir $L(x,s,d)$ a $\infty$ . Por el contrario, cuando elijo $x$ que hace pas violar la restricción, el oponente no debería poder conducir $L(x,s,d)$ a $\infty$ . Por eso restringimos al oponente para que sólo use $d \ge 0$ . Obsérvese que si violamos $h(x)=0$ entonces el oponente debería ser capaz de ganar independientemente de si $h(x) >0$ o $h(x)<0$ y por eso no ponemos ninguna restricción al multiplicador $s$ .

Si la restricción original era $g(x) \ge 0$ entonces podríamos formar una expresión diferente: $L(x, s, d) = f(x) + s\cdot h(x) - d \cdot g(x)$ , o podríamos mantenerlo como estaba requiriendo que $d \le 0$ . Por último, obsérvese que si el problema original era maximizar $f(x)$ entonces siempre se puede pensar en ello como minimizar $-f(x)$ .

1voto

littleO Puntos 12894

Sí, se puede pensar en el término $ d_i g_i ( x) $ en el Lagrangiano como penalizador de las violaciones de la restricción de desigualdad. Eso te ayudará a recordar si debes tener $ d \geq 0$ o $d \leq 0$ .

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X