Problema de otimização restrito na entropia matricial

10

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 i(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.[viviT]vi

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

minimizesum(entr(eig(A)))

.

subject toA=civiviTci=1ci0

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).

Seca
fonte

Respostas:

8

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.ci>0

A(c):=i=1NciviviT
viA

ci0AAσmin(A(c))0ci0σlog(σ)σ0ci0

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.

AA=UΛUT

dΛ=I(UTdAU),
dU=UC(dA),
C={uiTdAujλjλi,i=j0,i=j

AU=ΛUdΛ

d2Λ=d(I(UTdA1U))=I(dU2TdA1U+UTdA1dU2)=2I(dU2TdA1U).

d2ΛdU2Cvi

Eliminando a restrição de igualdade

i=1Nci=1N1

cN=1i=1N1ci.

N1

df=dC1TMT[I(VTUBUTV)]
ddf=dC1TMT[I(VT[2dU2BaUT+UBbUT]V)],
M=[111111],

Ba=diag(1+logλ1,1+logλ2,,1+logλN),

Bb=diag(d2λ1λ1,,d2λNλ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. c~=[1/N,1/N,,1/N]
  2. c=[c~,1i=1N1ci]
  3. A=iciviviT
  4. UΛA
  5. G=MT[I(VTUBUTV)]
  6. HG=ppHHδc~dU2BaBb
    MT[I(VT[2dU2BaUT+UBbUT]V)]
  7. c~c~p
  8. Vá para 2.

Resultados

viN=100vi

>> 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. insira a descrição da imagem aqui

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

Nick Alger
fonte
Muito obrigado! Resolvi-o com simplicidade, com gradiente asscent, mas isso provavelmente é mais confiável. O fato de que v precisa ser de classificação completa no arquivo matlab é a única coisa que me incomoda.
Seca
@NickAlger O link fornecido não está funcionando, posso solicitar que você dê uma olhada?
Criador
@Creator link atualizado no post! github.com/NickAlger/various_scripts/blob/master/…
Nick Alger
@NickAlger Existe uma restrição na matriz que o algoritmo pode operar? Esse algoritmo é bom para matrizes com elementos complexos? No meu caso, o SVD falha após algum tempo, pois a matriz possui Nan.
Criador
Não acho que números complexos devam ser um problema. Uma limitação do método é que a solução ideal não pode ter autovalores repetidos, o que acho que é o que está acontecendo aqui. Nesse caso, o método converge para algo que está dividindo por zero na equação C. Você pode tentar perturbar as entradas aleatoriamente um pouco e ver se isso ajuda as coisas. Existe uma maneira de contornar isso no artigo de Overton mencionado acima, mas meu código não é tão avançado.
Nick Alger