Testando se uma matriz é semi-definida positiva

11

Eu tenho uma lista L de matrizes simétricas que eu preciso verificar quanto à semi-definição positiva (ou seja, seus valores próprios não são negativos).

O comentário acima implica que alguém poderia fazê-lo calculando os respectivos autovalores e verificando se não são negativos (talvez seja necessário cuidar de erros de arredondamento).

Computar os autovalores é bastante caro no meu cenário, mas notei que a biblioteca que estou usando possui um teste rápido de definição positiva (ou seja, se os autovalores de uma matriz forem estritamente positivos).

Portanto, a idéia seria que, dada uma matriz BL , se testa se B+ϵI é definitivo positivo. Se não for, então B não é semi-definido positivo, caso contrário, pode-se calcular os autovalores de B para garantir que ele seja realmente semidefinido positivo.

Minha pergunta agora é:

Existe uma maneira mais direta e eficiente de testar se uma matriz é semi-definida positiva, desde que seja realizado um teste eficiente de definição positiva?

Jernej
fonte
1
O teste que você notou na biblioteca provavelmente é baseado na proposição de que a matriz real simétrica é definida positivamente se, e somente se, cada princípio principal menor der um determinante positivo, algo que poderia ser verificado pela eliminação sem girar na aritmética exata. A sutil dificuldade de estender isso para um caso semi-definido atraiu muitos autores para a distorção. Eu sei que o tópico foi abordado em uma pergunta Math.SE, então tentarei fornecer um link. A
hardmath
1
Para as pessoas mais qualificadas aqui - seria bom mudar o espectro para positivo adicionando para c grande , depois encontre o valor próprio mínimo do sistema deslocado (por exemplo, com iteração inversa) e verifique se o menor valor próprio de o sistema deslocado é menor que o turno c ? O deslocamento c pode ser, por exemplo, o maior autovalor de magnitude que pode ser encontrado rapidamente. B+cIccc
Nick Alger
Sim, você pode alterar os autovalores e calcular o menor autovalor, mas ainda tem o problema de definir alguma tolerância para o que aceitará (e garantir que seus autovalores sejam calculados com pelo menos essa tolerância!)
Brian Borchers
Não tenho certeza se isso seria útil, mas observe que uma vez que você sabe que uma matriz não é positiva definida, para verificar se é semidefinida positiva, basta verificar se seu kernel está vazio.
Abel Molina

Respostas:

20

Qual é a sua definição de trabalho de "semidefinido positivo" ou "definido positivo"? Na aritmética de ponto flutuante, você precisará especificar algum tipo de tolerância para isso.

Aλ=1.01030λ=1.0

λ máxϵ|λmax|λmax

Infelizmente, calcular todos os autovalores de uma matriz consome bastante tempo. Outra abordagem comumente usada é que uma matriz simétrica é considerada definida positivamente se a matriz tiver uma fatoração de Cholesky na aritmética de ponto flutuante. O cálculo da fatoração de Cholesky é uma ordem de magnitude mais rápido que o cálculo dos valores próprios. Você pode estender isso para semidefinitividade positiva adicionando um pequeno múltiplo da identidade à matriz. Novamente, há problemas de dimensionamento. Uma abordagem rápida é fazer um dimensionamento simétrico da matriz para que os elementos diagonais sejam 1,0 e adicione à diagonal antes de calcular a fatoração de Cholesky. ϵ

Você deve ter cuidado com isso, porque existem alguns problemas com a abordagem. Por exemplo, há circunstâncias em que e são definidos positivamente no sentido de que eles têm fatorações de Cholesky de ponto flutuante, mas não tem uma fatoração de Cholesky. Portanto, o conjunto de "matrizes definidas positivas fatoráveis ​​de Cholesky de ponto flutuante" não é convexo! B ( A + B ) / 2AB(A+B)/2

Brian Borchers
fonte
Você poderia elaborar esse último parágrafo ou postar um link em uma fonte? Isso é muito bizarro.
Daniel Shapero
1
Uma referência clássica a essa escala é A. van der Slui. Números de condição e equilíbrio de matrizes Numerische Mathematik 14 (1): 14-23, 1969. Também é discutido em livros didáticos como Golub e van Loan. O bit no último parágrafo é da experiência pessoal conquistada com dificuldade na pesquisa de linhas de codificação em um código de programação semidefinido - eu encontrei situações em que e têm fatorações de Cholesky por LAPACK, mas não possui uma fatoração de Cholesky de acordo com LAPACK. Esses tipos de problemas começam a ocorrer quando você é quase singular. X + α Δ X X + 0,95 α Δ XXX+αΔXX+0.95αΔX
Brian Borchers
Também não é incomum descobrir que algumas matrizes podem ser fatoradas em Cholesky com precisão estendida ou quádrupla, mas não com aritmética regular de precisão dupla ou dupla precisão.
Brian Borchers
3
Vários dos códigos de pontos interiores primários e duplos para SDP (CSDP, SDPT3, SDPA) sempre retornam matrizes que são definidas positivamente e possuem fatorações de Cholesky, enquanto outro solucionador popular (SeDuMi) usa uma decomposição de autovalores e retornará soluções que possuem valores negativos muito pequenos. autovalores.
Brian Borchers
3
Thomas H. Kerr III
fonte
4
Parece que o nome de usuário praticamente revela a relação entre o autor da resposta e o autor dos trabalhos. Um pouco mais de informação sobre o conteúdo do artigo seria bom; apesar de tudo, é muito interessante e relevante para a lista de perguntas dos artigos!
Anton Menshov