Convexidade e algoritmos eficientes.

[Editar em 21 de julho de 2011: editei a pergunta para pedir mais exemplos]

Esta pergunta está solicitando uma discussão documentada de ou mais exemplos de uma observação heurística.

Alguns problemas matemáticos que admitem algoritmos eficientes parecem ter natureza convexa. Estou pensando em programas lineares e semi-definidos e em vários problemas combinatórios que se reduzem a esses.

Primeiro, existem outras famílias de problemas que admitem algoritmos eficientes para o caso convexo / conjuntivo? (Eu ficaria particularmente grato por exemplos de procedimentos de decisão para teorias lógicas). Segundo, eu gostaria de receber sugestões de artigos ou seções de artigos que discutem uma opinião como "espreitar sob muitos algoritmos eficientes é uma estrutura convexa".

[Editar, 21 de julho de 2011: adicionado o seguinte.]

Eu gostaria de acrescentar alguns esclarecimentos. Me desculpe por não incluí-los antes. Estou interessado em problemas de decisão lógica. Parece-me que existem procedimentos de decisão eficientes para o fragmento conjuntivo de vários problemas lógicos. Aqui estão dois exemplos.

Os solucionadores eficientes para teorias de primeira ordem sem quantificadores (como solucionadores SMT para igualdade, igualdade com funções não interpretadas, aritmética das diferenças etc.) geralmente têm um solucionador eficiente para o fragmento conjuntivo e usam várias técnicas para lidar com disjunção e negação. Na análise estática de programas, as abstrações comumente usadas (e eficientes) são baseadas em intervalos inteiros, igualdades afins, octógonos ou poliedros. Na abstração baseada em predicados e na verificação do programa, existe algo chamado abstração cartesiana, que é intuitivamente sobre ter conjunções de predicados em vez de combinações booleanas arbitrárias. Todos esses casos parecem-me obter ganhos de eficiência, explorando o fragmento conjuntivo do problema.

O fragmento conjuntivo da teoria de primeira ordem da aritmética linear real pode expressar poliedros convexos. Foi por isso que perguntei originalmente sobre programação convexa.

Estou interessado em conhecer outros problemas ou exemplos em que soluções eficientes (no sentido teórico ou prático) se baseiam em um subproblema convexo ou conjuntivo. Se houver outra condição geral (Suresh mencionou a submodularidade), mencione-a e os problemas cujas soluções exploram essa condição.

Em relação à pergunta 1.

Os exemplos que você deu, programas lineares e SDPs (que são programas lineares sobre cones convexos), podem ser generalizados para programas convexos: minimização de uma função convexa em um conjunto viável convexo. Como você está procurando "outras famílias de problemas" que sejam eficientes, graças à presença de convexidade, a coisa natural a ser descartada é a parte da função convexa, e apenas observe os conjuntos convexos. Este é o domínio da geometria convexa, e aqui existem muitos algoritmos.

Um dos favoritos padrão é:

Martin Dyer, Alan Frieze, Ravi Kannan. Algoritmo de tempo polinomial aleatório para a aproximação do volume de corpos convexos .

A dificuldade aqui é que a dimensão é (deveria ser) uma parte da entrada; por outro lado, um algoritmo ingênuo faz amostragem de pontos na grade, que adere a dimensão no expoente do tempo de execução. A razão pela qual a convexidade ajuda é intuitiva: a convexidade fornece resultados de separação, coisas como o lema de Farkas, que diz que um ponto está em um cone convexo fechado ou você pode separá-los com um hiperplano. A relevância aqui é dizer que você sabe que algum ponto está no corpo convexo, enquanto que uma constelação de pontos ao redor dele não está no corpo: a partir daqui, você pode cortar uma grande parte da entrada e nunca se incomodar em amostrá-la. Talvez eu deva esclarecer que o artigo acima faz a estimativa produzindo um bom algoritmo de amostragem dentro do corpo (os quais são úteis). Última vez que verifiquei, ainda não existe um análogo determinístico disso; Acabei de pesquisar no Google para ver se o status mudou (não parece) e recebi essas anotações com algumas referências que podem lhe interessar:http://www.cs.berkeley.edu/~sinclair/cs294/n16.pdf . Eu nunca participei dessa aula e apenas olhei brevemente; portanto, peço desculpas se houver alguns problemas, mas as referências ali parecem ter valor para você.

Para mais exemplos de algoritmos que exploram a geometria convexa, um lugar para procurar são as subseções 'Bibliografia e observações' que concluem cada seção (de cada capítulo!) Do livro de Jiri Matousek, "Lectures on Discrete Geometry", de Jiri Matousek.

Outra coisa que é muito citada, e que parece ter tópicos para você (mas nunca fui além do índice; Matousek, por outro lado, é .. na minha outra mão), é "Algoritmos geométricos e combinatórios otimização "por Grotschel, Lovasz e Schrijver. (Sim, esse Lovasz.)

Acho que essas referências têm muito para você, então passarei à próxima pergunta.

Em relação à questão 2.

Embora seja definitivamente verdade que a convexidade é poderosa, não vi um comentário como o que você procura e acho que as pessoas têm muito cuidado em comunicar esse sentimento.

Eu tenho uma anedota sobre isso. Uma maneira de as pessoas injetarem a convexidade nos problemas é simplesmente .. aproximar / modelá-las com algo convexo. (Por exemplo: substituindo restrições de classificação por normas na matriz, substituindo números inteiros (não convexos e nem conectados) por conjuntos convexos de reais.) Um texto de referência para esse material é a "Otimização Convexa" de Boyd & Vandenberghe. Mas uma vez eu estava assistindo os vídeos de Boyd, e alguém lhe deu a pergunta "é convexa = eficiente", e ele imediatamente disse SVD. Observe que o SVD pode ser gravado como um problema de minimização com restrição de classificação. Enfim, meu argumento é que até Boyd é muito rápido em corrigir um comentário como esse.

Dito isto, desejo compartilhar dois lugares em que fui pessoalmente surpreendido por estruturas convexas (especialistas podem revirar os olhos e cochilar aqui). Os primeiros são os chamados problemas de 'soma dos quadrados', que são problemas de minimização em relação a polinômios não - convexos . Graças às propriedades de interpolação dos polinômios, você pode reescrevê-las como SDPs. Existem algumas notas bonitas do curso sobre este tópico de Pablo Parrilo; você pode encontrar isso e mais informações em sua página da Web e outras informações nesta publicação do MO de Noah Stein: /mathpro/32533/is-all-non-convex-optimization-heuristic/32634#32634 .

Outro lugar bonito é em famílias exponenciais. Agora, tudo isso é "óbvio" quando você percebe que essas são soluções para a entropia máxima (um problema de otimização convexa), mas é incrível o quanto a estrutura convexa informa o comportamento das famílias exponenciais (uma referência que eu gosto aqui é o livro de Wainwright e Jordan sobre gráficos). modelos). Por sua vez, isso justifica algumas das coisas que as pessoas fazem com esse tipo de modelagem.