Quero minimizar uma função objetiva complicada e não tenho certeza se é convexa. Existe um bom algoritmo que tenta provar que não é convexo? É claro que o algoritmo poderia falhar em provar isso; nesse caso, eu não saberia se é convexo ou não, e isso está correto; Eu só quero tentar descartar a convexidade antes de gastar muito tempo tentando determinar analiticamente se a função objetivo é convexa, por exemplo, tentando reescrever o problema em um formulário padrão conhecido por ser convexo. Um teste rápido seria tentar minimizar a partir de vários pontos de partida e se vários mínimos locais forem encontrados dessa maneira, não será convexo. Mas eu queria saber se existe um algoritmo melhor que foi projetado com esse objetivo em mente.
9
Respostas:
fonte
Para vários testes de verificação de convexidade / não-convexidade praticamente úteis, consulte (auto-exoneração de responsabilidade, sou o terceiro autor deste artigo):
R. Fourer, C. Maheshwari, A. Neumaier, D. Orban e H. Schichl, detecção de convexidade e concavidade em gráficos computacionais. Tree Walks for Convexity Assessment, INFORMS J. Computing 22 (2010), 26-43.
Observe que existem muitas funções que são convexas no domínio de interesse, mas que não podem ser facilmente 'disciplinadas', ou seja, escritas em uma das formas exigidas pelos solucionadores de convexos estruturados, como o CVX .
fonte
Uma função pode ser não convexa sem ter múltiplos mínimos. Existem vários métodos de otimização que aplicam iterações de gradiente conjugado (linear ou não linear), truncadas quando uma norma negativa de operador é calculada. O valor negativo indica uma direção de curvatura negativa (o que não pode acontecer para funcionais convexos). Se a curvatura negativa raramente é encontrada, esses métodos convergem em um pequeno número de iterações de otimização. (Se um pré-condicionador de qualidade estiver disponível, as etapas internas também deverão convergir rapidamente.)
fonte