Problema de otimização restrito na entropia matricial

Eu tenho um problema de otimização restrito na entropia da matriz (Shannon) . A matriz A pode ser escrita como a soma das matrizes de classificação 1 do formulário [ v $\mathtt{(sum(entr(eig(A))))}$$A$ onde v i é um dado vector normalizado. Os coeficientes das matrizes da classificação um são as incógnitas em que otimizamos e elas devem ser maiores que zero e somar 1.$[v_i\,v_i^T]$$v_i$

Em uma sintaxe semelhante ao CVX, o problema é o seguinte: dada a variável $\mathtt{c(n)}$

$$\text{minimize} \qquad \mathtt{sum(entr(eig(A)))}$$

.

$$\begin{align} \text{subject to} \qquad A &= \sum c_i v_i v_i^T\\ \sum c_i &= 1\\ c_i &\ge 0\end{align}$$

Alguém tem uma idéia de como resolver isso com eficiência? Eu já sei que provavelmente não pode ser lançado como um problema de programação semi-definida (SDP).

Editar: um colega me informou que meu método abaixo é uma instância do método geral no artigo a seguir, quando especializado na função entropia,

Overton, Michael L. e Robert S. Womersley. "Segundas derivadas para otimizar valores próprios de matrizes simétricas." Jornal SIAM sobre Análise e Aplicações de Matrizes 16.3 (1995): 697-718. http://ftp.cs.nyu.edu/cs/faculty/overton/papers/pdffiles/eighess.pdf

visão global

Neste post, mostro que o problema de otimização está bem colocado e que as restrições de desigualdade estão inativas na solução; depois, calculamos o primeiro e o segundo derivados de Frechet da função entropia; em seguida, proponho o método de Newton para o problema com a restrição de igualdade eliminada. Finalmente, o código Matlab e os resultados numéricos são apresentados.

Boa postura do problema de otimização

Primeiro, a soma de matrizes definidas positivas é definida positiva, de modo que para , a soma de rank-1 matrizes A ( c ) : = N Σ i = 1 c i v i v o t i é definida positiva. Se o conjunto de v i é a classificação completa, os autovalores de A são positivos, de modo que os logaritmos dos autovalores podem ser obtidos. Assim, a função objetivo é bem definida no interior do conjunto viável.$c_i > 0$

$$A(c):=\sum_{i=1}^N c_i v_i v_i^T$$ $v_i$$A$

$c_i \rightarrow 0$$A$$A$$\sigma_{min}(A(c)) \rightarrow 0$$c_i \rightarrow 0$$-\sigma \log(\sigma)$$\sigma \rightarrow 0$$c_i \ge 0$

Derivados de Frechet da função entropia

No interior da região viável, a função de entropia é Frechet diferenciável em todos os lugares e duas vezes Frechet diferenciável onde quer que os autovalores não sejam repetidos. Para fazer o método de Newton, precisamos calcular derivadas da entropia da matriz, que depende dos valores próprios da matriz. Isso requer sensibilidades computacionais da decomposição de autovalor de uma matriz em relação a alterações na matriz.

$A$$A = U \Lambda U^T$

$$d\Lambda = I \circ (U^T dA U),$$ $$dU = UC(dA),$$ $\circ$ $$C = \begin{cases} \frac{u_i^T dA u_j}{\lambda_j - \lambda_i}, & i=j \\ 0, &i=j \end{cases}$$

$AU=\Lambda U$$d\Lambda$

$$\begin{align} d^2 \Lambda &= d(I \circ (U^T dA_1U)) \\ &= I \circ (dU_2^T dA_1 U + U^T dA_1 dU_2) \\ &= 2 I \circ (dU_2^T dA_1 U). \end{align}$$

$d^2 \Lambda$$dU_2$$C$$v_i$

Eliminando a restrição de igualdade

$\sum_{i=1}^N c_i = 1$$N-1$

$$c_N = 1-\sum_{i=1}^{N-1} c_i.$$

$N-1$

$$df = dC_1^T M^T [I \circ (V^T U B U^T V)]$$ $$ddf = dC_1^T M^T [I \circ (V^T[2dU_2 B_a U^T + U B_b U^T]V)],$$ $$M = \begin{bmatrix} 1 & \\ & 1 & \\ &&\ddots& \\ &&&1\\ -1 & -1 & \dots & -1 \end{bmatrix},$$

$$B_a = \mathrm{diag}(1+\log \lambda_1, 1 + \log \lambda_2, \ldots, 1 + \log \lambda_N),$$

$$B_b = \mathrm{diag}(\frac{d_2\lambda_1}{\lambda_1},\ldots,\frac{d_2\lambda_N}{\lambda_N}).$$

Método de Newton após eliminar a restrição

Como as restrições de desigualdade são inativas, simplesmente começamos no conjunto viável e executamos a região de confiança ou a pesquisa de linhas inexata newton-CG para convergência quadrática aos máximos interiores.

O método é o seguinte, (não incluindo detalhes da pesquisa de região de confiança / linha)

1. $\tilde{c} = [1/N,1/N,\ldots,1/N]$
2. $c = [\tilde{c},1 - \sum_{i=1}^{N-1} c_i]$
3. $A = \sum_i c_i v_i v_i^T$
4. $U$$\Lambda$$A$
5. $G = M^T [I \circ (V^T U B U^T V)]$
6. $H G = p$$p$$H$$H$$\delta \tilde{c}$$dU_2$$B_a$$B_b$ $$M^T [I \circ (V^T[2dU_2 B_a U^T + U B_b U^T]V)]$$
7. $\tilde{c} \leftarrow \tilde{c} - p$
8. Vá para 2.

Resultados

$v_i$$N=100$$v_i$

>> N = 100;
>> V = padrão (N, N);
>> para k = 1: NV (:, k) = V (:, k) / norma (V (:, k)); fim
>> maxEntropyMatrix (V);
Iteração de Newton = 1, norma (grad f) = 0,67748
Iteração de Newton = 2, norma (grad f) = 0,03644
Iteração de Newton = 3, norma (grad f) = 0.0012167
Iteração de Newton = 4, norma (grad f) = 1.3239e-06
Iteração de Newton = 5, norma (grad f) = 7.7114e-13

Para ver que o ponto ótimo calculado é de fato o máximo, aqui está um gráfico de como a entropia muda quando o ponto ótimo é perturbado aleatoriamente. Todas as perturbações fazem a entropia diminuir.

Código Matlab

Função tudo em 1 para minimizar a entropia (adicionada recentemente a esta postagem): https://github.com/NickAlger/various_scripts/blob/master/maxEntropyMatrix.m