4 votos

Maximización de una función convexa

El siguiente problema es el ejercicio I. 6 de Bellman Programación Dinámica.

Considere el problema de maximización de la función de $$ F(x_{1} , \ldots , x_{N}) = \sum_{i = 1}^{n} \varphi(x_{i}), $$ sujeto a las restricciones $x_{i} \geq 0$$\displaystyle\sum_{i = 1}^{N} x_{i} = c$. Mostrar que si $\varphi$ es convexa, entonces el máximo es de $\varphi(c)$.

No creo que este problema es el correcto tal como está escrito. Considere el ejemplo con $n = 2$, $c = 1$ y $\varphi : \mathbf{R} \to \mathbf{R} : x \mapsto x^{2} + 1$. A continuación, $\varphi(c) = 2$, pero $x = (1,0)$ es factible y alcanza un valor objetivo de $F(1,0) = \varphi(1) + \varphi(0) = 2 + 1 = 3$, por lo que el máximo no es $\varphi(c)$.

¿Qué crees que el autor quería preguntar? Una modificación que he encontrado es la siguiente.

Considere el problema de minimización de la función $$ F(x_{1} , \ldots , x_{N}) = \sum_{i = 1}^{n} \varphi(x_{i}), $$ sujeto a las restricciones $x_{i} \geq 0$$\displaystyle\sum_{i = 1}^{N} x_{i} = c$. Mostrar que si $\varphi$ es convexa, entonces el máximo es de $n \varphi\left(\frac{c}{n}\right)$.

Puede alguien pensar en algo mejor? Mi problema pierde la simplicidad de la respuesta, $\varphi(c)$, y también el carácter de la maximización de una función convexa.

1voto

Sharkos Puntos 11597

Resumen: la respuesta Correcta es $\phi(c) + (n-1)\phi(0)$ en general, por lo que probablemente asumió $\phi(0)=0$ que es un trivial de turno del problema.

Por qué? Debido a la convexidad implica inmediatamente que tomar un poco más grande $x$ y agregarlo a cualquiera de los demás disminuye la función de destino. Esto es debido a que el gradiente de $\phi$ es más pronunciada en el valor más grande. Por lo tanto $(c,0,0,\cdots,0)$ es trivialmente óptimo.

Los siguientes son mi primera ingenuo primeras horas de aproximación.


Creo que es más fácil de resolver el problema y, a continuación, trabajar de lo que era la respuesta. El siguiente es innecesariamente complicado, pero totalmente irracional que a veces es una ventaja. Vamos a buscar puntos estacionarios dentro de la gama de multiplicadores de Lagrange:

$G(x_i;\lambda) = \sum\phi(x_i) - \lambda (\sum x_i - c)$

Esto le da a $\phi'(x_i) = \lambda$ todos los $x_i$. Por lo tanto, si $\phi''$ tiene una señal definitiva, no es más que una solución a esta ecuación (desde $\phi'$ es monótona) y, por tanto,$x_1=x_2=\cdots=x^\star$. Pero a partir de la restricción, $nx^\star = c$ y por lo tanto el único punto fijo es

$$\boxed{n \phi(\frac{c}{n})}$$

como usted sugiere.

Ahora lo que el máximo en el límite? Configuración de una variable a la vez a cero, nos encontramos con que los posibles puntos estacionarios aquí son versiones de las anteriores restringido a un número menor de variables. Por tanto, la posible puntos estacionarios son

$$n \phi\left(\frac{c}{n}\right), (n-1) \phi\left(\frac{c}{n-1}\right)+\phi(0), (n-2) \phi\left(\frac{c}{n-2}\right)+2\phi(0), \cdots, \phi(c)+(n-1)\phi(0)$$

dependiendo de cuántas variables son no-cero.

La única pregunta que queda es cual de estos es el más grande. Tenga en cuenta que

$$m \phi(c/m) +(n-m)\phi(0) = n\phi(0) + m(\phi(c/m) -\phi(0))$$

Pero mientras $\phi''(0) > 0$, $$\phi(x) -\phi(0) > m (\phi(x/m)-\phi(0))$$ y, por tanto, el máximo es de hecho $$\boxed{\phi(c)+(n-1)\phi(0)}$$

Usted puede ver esto mediante el uso estándar de los resultados de las funciones convexas. Intuitivamente, es mejor poner todos los huevos en una sola canasta, ya que su tasa de retorno va con su inversión.

Por lo tanto, él era probable asumiendo $\phi(0)=0$.

Edit: di cuenta y fijo enorme error.

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