Qual é a diferença entre programação geométrica e programação convexa?

10

Qual é a diferença entre programação geométrica (generalizada) e programação convexa geral?

Um programa geométrico pode ser transformado em um programa convexo e normalmente é resolvido por um método de ponto interior. Mas qual é a vantagem de formular diretamente o problema como um programa convexo e resolvê-lo por um método de ponto interior?

A classe de programas geométricos constitui apenas um subconjunto da classe de programas convexos que podem ser resolvidos de maneira especialmente eficiente por métodos de pontos interiores? Ou a vantagem é simplesmente que um programa geométrico geral pode ser facilmente especificado na forma legível por computador.

Por outro lado, existem programas convexos que não podem ser aproximados razoavelmente bem por programas geométricos?

optimization convex-optimization Thomas Klimpel
fonte

5

Na verdade, nunca tinha ouvido falar em programação geométrica até essa pergunta. Aqui está um artigo de revisão de Stephen Boyd et al. (Vandenberghe também é coautor) que é um tutorial sobre programação geométrica.

Programas geométricos como originalmente expressos não são convexos. Por exemplo, é um posinômio e não é convexo; portanto, programas geométricos não são um subconjunto estrito de programação convexa. $x^{1/2}$

A vantagem de transformar um programa geométrico em um programa convexo é que o programa geométrico original não é necessariamente convexo. Se você resolveu o programa geométrico como um programa não linear (PNL), seria necessário usar métodos de otimização não convexa para garantir uma solução ótima global. Esses métodos são mais caros do que os métodos de otimização convexos, exigem mais ajustes algorítmicos e requerem estimativas iniciais.

Além disso, se você usar um algoritmo de NLP não convexa, precisará especificar seu conjunto viável como um conjunto compacto em ; em programas geométricos, é uma restrição válida. $\mathbb{R}^{n}$ $x > 0$

Não está claro se o conjunto de programas geométricos é mapeado (por meio da transformação log-exponencial) para um conjunto de programas convexos que resolve de maneira particularmente eficiente. Não vejo vantagens na programação geométrica além da transformação em programas convexos.

Quanto à sua última pergunta, não acho que o conjunto de programas geométricos seja isomórfico ao conjunto de programas convexos; portanto, suspeito que existam programas convexos que não podem ser expressos como programas geométricos e, desses programas, suspeito que exista são alguns que não podem ser aproximados razoavelmente bem por programas geométricos. No entanto, não tenho uma prova ou um contra-exemplo.

Geoff Oxberry
fonte

Parece que o capítulo 8 do seu artigo de revisão vinculado tenta responder à minha pergunta. No entanto, depois de uma primeira análise superficial, tenho a impressão de que qualquer programa convexo pode ser aproximado por um programa geométrico (logaritmicamente transformado, é claro ...). No entanto, como qualquer programa linear é "obviamente" também um programa geométrico, isso também pode ser apenas uma variante da afirmação de que qualquer programa convexo pode ser aproximado por um programa linear, mas isso não seria o que quero dizer com "aproximado razoavelmente" bem".

Thomas Klimpel

Quando surgiu o termo programação geométrica, não era fácil resolver programas convexos gerais, e a estrutura especial poderia ser explorada. Agora, é claro, uma vez que se reconhece que um programa é geométrico, o transforma em um programa convexo e o resolve por métodos de pontos internos.

Arnold Neumaier

3

$f(x) \leq 1$ $f(x)$ $-x-y \leq 1$ $-x-y$ $-x^2-y^2\leq 1$

Optar
fonte

A programação geométrica não é um subconjunto estrito da programação convexa; no entanto, sob a transformação log-exponencial, programas geométricos transformados são programas convexos.

Geoff Oxberry

Sim, era isso que eu queria dizer. Resposta editada para maior clareza.

Opte

Qual é a diferença entre programação geométrica e programação convexa?

Respostas: