Maximizando uma função convexa com uma restrição linear

maximize f (x) subject to A x = b

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

Onde

f (x) = \sum_{i = 1}^{N} \sqrt{1 + \frac{x_{i}^{4}}{{(\sum_{i = 1}^{N} x_{i}^{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}},$

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

Podemos ver que é convexo e tem a forma . Também pode ser mostrado que é delimitado em . Eu sei que um problema de maximização convexa é NP-difícil, em geral. $f$ $\sqrt{1+y^2}$ $f$ $[\sqrt{2}, 2]$

No entanto, usando a natureza específica do problema, é possível resolvê-lo usando qualquer software / pacote de otimização convexa padrão?

optimization Sooraj
fonte

Existem dois somatórios, um dentro do outro, que usam a mesma "variável de loop"

i

$i$ . Parece claro, a partir do contexto, quais usos de

i

$i$ são quais, mas corrija para maior clareza.

Jrandom_hacker

Respostas:

Sim, a otimização convexa com restrição de igualdade é NP-Hard em geral. No entanto, existem técnicas maduras que encontram soluções aproximadas muito agradáveis para problemas de otimização convexos, como a Descida de coordenadas.

Suponha que você use a descida de coordenadas e a matriz A tenha a classificação . Você pode corrigir as coordenadas nk-1 da sua solução viável e os vetores da solução no espaço da solução são determinados exclusivamente por uma coordenada, por exemplo . Nesse caso, você pode apenas pegar a derivada de com relação a para encontrar o máximo nesta iteração. $k$ $x = (x_1, x_2, x_3, ..., x_n)$ $x_i$ $f(\cdot)$ $x_i$

Em seguida, fixamos iterativamente as coordenadas nk-1 e melhoramos a solução até encontrar uma aproximadamente ideal.

Strin
fonte

@RodrigodeAzevedo: Não é uma contradição ou surpresa que o LP, um caso especial de otimização convexa, seja mais fácil do que o caso geral.

j_random_hacker 7/05/19