Maximizando una función convexa con una restricción lineal

maximizar F (X) sujeto a UN X = si

$\text{maximize } f(\mathbf{x}) \quad\text{subject to } \mathbf{Ax} = \mathbf{b}$

dónde

F (X) = \sum_{yo = 1}^{norte} \sqrt{1 + \frac{X_{yo}^{4 4}}{{(\sum_{yo = 1}^{norte} X_{yo}^{2})}^{2}}},

$f(\mathbf{x}) = \sum_{i=1}^N\sqrt{1+\frac{x_i^4}{\left(\sum_{i=1}^{N}x_i^2\right)^2}},$

y . $\mathbf{x} = [x_1,x_2,...,x_N]^T \in \mathbb{R}^{N\times 1}$ $\mathbf{A} \in \mathbb{R}^{M\times N}$

Podemos ver que es convexa y de la forma $f$ . También se puede demostrar queestá acotada en $\sqrt{1+y^2}$ $f$ . Sé que un problema de maximización convexa es NP-hard, en general. $[\sqrt{2}, 2]$

Sin embargo, utilizando la naturaleza específica del problema, ¿es posible resolverlo utilizando algún software / paquete estándar de optimización convexa?

optimization Sooraj
fuente

Hay dos sumas, una dentro de la otra, que usan la misma "variable de bucle"

. Parece claro por el contexto qué usos de

son cuáles, pero por favor arregle para mayor claridad.

i

$i$

i

$i$

j_random_hacker

Respuestas:

Sí, la optimización convexa con restricción de igualdad es NP-Hard en general. Sin embargo, existen técnicas maduras que encuentran soluciones aproximadas muy buenas para los problemas de optimización convexa, como el Descenso de coordenadas.

Suponga que usa el descenso coordinado y la matriz A tiene rango . Puede fijar NK-1 coordenadas de su solución factible y entonces los vectores de solución en el espacio de la solución se determina de forma única por una coordenada, por ejemplo . En ese caso, puede simplemente tomar la derivada de con respecto a para encontrar el máximo en esta iteración. $k$ $x = (x_1, x_2, x_3, ..., x_n)$ $x_i$ $f(\cdot)$ $x_i$

Luego arreglamos iterativamente la coordenada nk-1 y mejoramos la solución hasta que se encuentre una solución óptima.

Strin
fuente

@RodrigodeAzevedo: No es una contradicción o sorprendente que LP, un caso especial de optimización convexa, sea más fácil que el caso general.

j_random_hacker