Considere el problema de optimización $$ \min_{x\in X} f(x) $$ donde $X\subset\mathbb{R}^n$ es un vacío cerrado conjunto convexo. $f$ es continua en todas partes en $X$. Puedo mostrar que $f$ es convexa en el interior de $X$. No tengo una prueba de que $f$ es convexa en el límite de $X$. Son los Karush-Kuhn-Tucker condiciones suficientes para caracterizar una solución a este problema de optimización, en este caso?
Respuesta
¿Demasiados anuncios?
Ali
Puntos
1
Sí, de Hecho, hemos $$\text{Set of optimal solutions} = \text{Set of KKT points} $$ If $f$ is continuous on $X$ while convex on $\text{int} X$, then $f$ has to be Convex on whole $X$. Also we know that $\text{int} X \neq \emptyset$ this shows the slater QC holds , therefore aevery optimal point is indeed KKT point. we show that also each KKT point is indeed optimal. To this end, take $\bar{x} \in X$ which satisfies KKT system i.e., $$ 0 \in \partial f( \bar{x} ) + N(\bar{x}; X)$$ Donde $N(\bar{x}; X)$ $\partial f(x)$ son convexo de la normal de cono de $X$ $\bar{x},$ y convexo subdifferential de $f$ $\bar {x}$ respectivamente. Dependiendo de la estructura de las limitaciones de $N(\bar{x}; X)$ puede ser reducido a un sistema que contiene multiplicadores de Lagrange. De KKT condición en la que nos podríamos encontrar vectores $u \in \partial f(\bar{x})$ $ v \in N(\bar{x}; X)$ tal que$$u + v =0$$
Ahora tome $x \in X$, Ya que el $u \in \partial f(\bar {x})$ hemos
\begin{align*} \langle u , x -\bar {x} \rangle \leq f(x ) - f(\bar{x}) \\ \Rightarrow \langle v , x -\bar {x} \rangle \ge f(\bar{x}) - f(x ) \end{align*}
Y que el lado izquierdo es negativo debido a $v \in N(\bar{x} ; X)$, por lo tanto $f(x) \ge f(\bar{x}).$ por lo Tanto $\bar{x} \in X$ es óptimo.
Tenga en cuenta que la continuidad de $f$ en el límite de las $X$ es un presupuesto básico!
Tomar, por ejemplo,$X=[0,1]$$f=1$$\text{int}X = (0,1)$$f(x) = 0$$x \in \{0, 1\}$, Entonces todo punto de vivir en $(0,1)$ son de KKT puntos, Ya que para $\bar{x} \in (0,1)$tenemos $f' (\bar{x}) =0 $ (tenga en cuenta que en los puntos del interior de todos los multiplicadores de Lagrange son cero, por eso KKT sistema se reduce a $f' = 0.$ Por otro lado, claramente ninguno de estos puntos son de óptima!
P. S:
En realidad lo que he mencionado aquí como Slater control de calidad no es el bien conocido Slater Restricción de la Calificación (de curso $X$ no ha sido representado por las desigualdades y las igualdades), tal vez debería eliminar esa palabra para evitar la confusión. Es una slater tipo de calificación de condición (control de calidad) que garantiza la Suma de la Regla i.e, $$ \partial (f+g) (x) = \partial f(x) + \partial g (x) $$ Donde $g$ es la función de indicador de $X$, lo $\partial g(\bar{x}) = N(\bar{x} ; X)$. Y tenga en cuenta que la restricción problema es equivalente a unconstraint problema con el nuevo objetivo $f+g$. Es por eso que tenemos la implicación $ Optimal \to KKT $. En general, de alguna manera todos restricción de calificaciones puede ser visto como condiciones de garantía la Suma de la regla entre la función objetivo y la función de indicador de conjunto de Restricciones. He utilizado la suma de la regla bajo la condición hecho en Moreu-Rockafellar teorema, que corresponde a Slater cualificación de las restricciones. También hay algunas otras condiciones para el cálculo de las reglas que de alguna manera han contador de la parte en la Restricción de Calificación y viceversa!
