Soluções intermediárias para programas lineares

Existe um programa linear para o qual eu quero não apenas uma solução, mas uma solução que seja o mais central possível na face do politopo que assume o valor mínimo.

A priori, esperamos que a face minimizadora seja alta dimensionalmente por várias razões, incluindo que a função objetivo minimizada seja o máximo de muitas das restrições:

Minimize $\epsilon$ sujeito a com linear e para todos os e . $f_i(\bar x) \leq \epsilon < 0$ $f_i$ $x_i > 0$ $i$ $\sum_i x_i = 1$

Nós nunca obteríamos nenhuma propriedade semelhante à centralidade do algoritmo simplex, é claro. Algum dos algoritmos habituais de pontos interiores exibe essas propriedades? Existe alguma garantia de que eles evitarão vértices ou faces dimensionais mais baixas sempre que possível?

Na verdade, eu provavelmente estou contente com um programa quadrático fácil que encontra o ponto médio de todo o pólipo, uma vez que a centralidade importa mais que a minimalidade, apenas vagamente curiosa se outros algoritmos de programação linear oferecerem propriedades relevantes.

Atualização: reduzi o problema subjacente a um simples problema de minimização restrita solucionável com multiplicadores Lagrange, mas a pergunta acima permanece interessante de qualquer maneira.

ds.algorithms linear-algebra linear-programming Jeff Burdges
fonte

não exatamente sua pergunta, mas: calcular o centróide é difícil; Não sei ao certo qual é a melhor aproximação, mas, para algumas aplicações, colocar o politopo na posição isotrópica e tirar a média de polinomialmente muitas amostras uniformes do politopo (transformado) é suficiente. veja estas notas, Lema 15, por exemplo: cc.gatech.edu/~vempala/acg/notes.pdf

Sasho Nikolov

isso é mais uma questão teórica ou mais prática? talvez seja viável gerar todos os vértices da face ideal e depois usar alguma combinação convexa adequada deles.

anônimo

Respostas:

Tenho algumas observações que são longas demais para comentários. Aqui está um resumo.

Qualquer algoritmo para resolver exatamente o seu problema pode ser usado para resolver exatamente programas lineares (ou seja, "programação linear forte", que é usada na solução de Sariel e atualmente não possui um algoritmo de tempo polinomial).
O acompanhamento natural é se soluções aproximadas (isto é, "programação linear fraca") podem fornecer uma solução. Embora a resposta seja afirmativa, parece que a condição de parada para este procedimento requer quantidades que, até onde sei, não podem ser computadas em tempo polinomial. (ou seja, o algoritmo encontra algo bom, mas certificando isso é difícil.) Minha principal sugestão aqui é fazer uma definição significativa de um " solução -optimal" para o seu problema, caso em que esta abordagem é tratável. (Essa estratégia efetivamente lança pequenas faces do poliedro.) $\epsilon$

Em geral, enquanto pensava na sua declaração atual do seu problema, continuei analisando considerações de eficiência. Mas há uma intuição razoável nisso: os objetos que estamos jogando - vértices, faces etc. - são discretos e exponencialmente abundantes.

(1.) Suponha que tenhamos um algoritmo que resolva exatamente o seu problema. Observe que qualquer ponto exposto de qualquer face que contenha o ponto médio fornecido será uma solução exata para o programa linear original. Portanto, proceda da seguinte forma. Adicione uma nova restrição linear dizendo que o valor objetivo original deve ser igual ao valor ideal (que agora sabemos) e defina um novo objetivo dizendo para maximizar a primeira coordenada da solução. Repita este procedimento uma vez para cada dimensão, sempre adicionando uma restrição e escolhendo uma nova coordenada para maximizar. Esse processo reduzirá a dimensão da solução a cada vez; necessariamente, quando o processo é concluído, temos um conjunto afim de dimensão 0, significando um único ponto. Assim, com $\mathcal O(d)$ iterações do seu algoritmo de resolução de ponto médio (e apenas aumentando a descrição do problema em uma quantidade polinomial em cada vez), uma forte programação linear é resolvida. Isso mostra que, embora a solução de Sariel exija forte programação linear, uma solução exata para sua pergunta não pode evitá-la. ( Edit : note que minha prova supõe um poliedro compacto (um politopo) como entrada; caso contrário, ele tem que trabalhar um pouco mais para encontrar vértices.) $d$

(2.) Aqui está um esquema iterativo, usando um solucionador convexo completo em cada iteração, cujas soluções convergirão para uma noção moderada de solução de ponto médio. Escolha uma sequência positiva e decrescente de parâmetros de penalidade ; é razoável que estas desçam geometricamente, ie . Agora, para cada , minimize aproximadamente a função convexa $\{\lambda_i\}_{i=1}^\infty\downarrow 0$ $\lambda_i = 2^{-i}$ $i$

⟨ c, x ⟩ - λ_{Eu} \sum_{j = 1 1}^{m} em (⟨ {uma}_{j}, x ⟩ - b),

$\langle c,x\rangle - \lambda_i\sum_{j=1}^m \ln(\langle a_j,x\rangle - b),$

onde é o seu objectivo inicial, e intervalos ao longo dos constrangimentos originais, agora colocado no objectivo através de barreiras logarítmicas (nota, este é o padrão). Agora, se pensarmos na face minimizadora (de maior dimensão) do seu poliedro, observe que, para tolerância suficientemente pequenas para sua caixa preta de opção convexa, o valor aproximado ideal estará próximo a esta face, no entanto, as barreiras a empurrarão. o mais longe possível das outras restrições. Disse outra maneira, como $\langle c,x\rangle$ $j$ $m$ $\lambda_i$ $\tau$ $\lambda_i$ diminui, o objetivo linear original acabará por dominar algumas barreiras exigentes que o mantiveram da face apropriada, mas não afetará as barreiras que o afastam de outras fronteiras, em particular as da face alvo.

Em um mundo perfeito, nos sentávamos e determinávamos analiticamente um valor perfeito , ou pelo menos um tempo de parada, para que você não precise resolver muitos problemas infinitamente. Infelizmente, isso parece difícil. Uma idéia é, por exemplo, determinar a menor largura de qualquer face com dimensão maior que 0; esse é um problema de minimização bem definido com ótimo positivo, porque há muitas faces finitas (e a largura é calculada em relação a cada uma). Com isso, podemos definir pequeno o suficiente para que a influência das barreiras seja pequena no centro de cada face. Infelizmente, pode haver exponencialmente muitas faces, portanto, calcular essa quantidade é um absurdo. $\lambda$ $\lambda$

Todas as condições de parada que eu pude apresentar tiveram esses tipos de dificuldades computacionais. (Além disso, muitos poderiam novamente ser usados para transformar isso em um forte solucionador de programação linear.)

$\epsilon$ $\lambda$ $\tau$ $\epsilon$

(Alguns comentários finais.) Parece que a noção de "ponto médio" é crucial; O comentário de Sasho aponta que o centróide (centro de massa?) É um problema extremamente difícil, ao passo que é fácil encontrar, por exemplo, a maior bola inscrita. As barreiras logarítmicas que sugeri acima, em geral, não serão consistentes com nenhuma dessas noções do ponto médio. Por outro lado, para as barreiras e a bola, você pode derivar um limite inferior na distância do centróide até o limite relativo da face; talvez isso seja mais útil para você?

Por fim, a partir de sua descrição, acredito que você quis dizer que a "face alvo" teria a maior dimensão possível? Isso está bem definido, no entanto, também existem faces de solução para todas as possíveis dimensões menores. De qualquer forma, a abordagem de Sariel e a abordagem de barreira acima funcionarão com a face de maior dimensão.

matus
fonte

\sum_{i} f_{i} (x)^{2} + \sum_{j} x_{j}^{2}

$\sum_i f_i(x)^2 + \sum_j x_j^2$

\sum_{j} x_{j} = 1

$\sum_j x_j = 1$

x

$x$

ϵ

$\epsilon$

ϵ

$\epsilon$ minimizado para ajudar as restrições a evoluir mais rapidamente. Obrigado embora! :)

Jeff Burdges

x

$x$

Não entendo o ponto sobre "programação linear forte" e nunca ouvi essa expressão antes. não se sabe como resolver um LP em tempo polinomial forte. mas resolver um polinômio de tempo no LP na descrição da entrada (isto é, tempo polinomial fraco) é obviamente bem conhecido. se o OP quiser um algoritmo rodando em tempo polinomial fraco, a solução de Sariel + um algoritmo de ponto interior com polivalência fará o trabalho, não?

Sasho Nikolov 20/03/2012

τ

$\tau$

τ

$\tau$

@SashoNikolov, agora que penso nisso, a mesma noção de otimização (com os mesmos problemas) pode ser trabalhada na solução de Sariel, por exemplo, tratando restrições que estão dentro de uma pequena tolerância para realmente serem rígidas e ajustando esse valor adequadamente. Vou atualizar minha solução hoje à noite.

matus

Primeiro, encontre a solução ideal, depois adicione a restrição linear de que a solução deve ter um valor igual ao ideal que você deseja e reajuste seu LP como aquele que procura a maior bola dentro da região viável. Resolva este LP modificado e você terá o que deseja.

Por que o segundo problema pode ser resolvido usando LP é um problema fofo padrão em Geometria Computacional ...

==============

$h \equiv cx = \alpha$ $\min c x$ $P$ $P \cap h$

$v$ $v$ $v$ $\alpha$

Então, para o verão: (A) resolva o LP para descobrir o valor ideal. (B) Calcule o menor subespaço dimensional que contém a solução viável com o valor ideal. (C) Reescreva o LP original nesse subespaço afim (ou seja, diminuindo todas as dimensões irrelevantes), adicione uma variável e transforme-o em um LP para encontrar a maior bola dentro desse polítopo.

Sariel Har-Peled
fonte

O que se entende por "bola maior" em um poliedro não de dimensão total?

Kristoffer Arnsfelt Hansen 18/03/12

@KristofferArnsfeltHansen o poliedro certamente é um conjunto convexo situado em um subespaço afim de alguma dimensão.

Sasho Nikolov 19/03/2012

para que isso funcione, você precisará especificar uma restrição que limita as faces encontradas na primeira etapa. Você também precisaria saber que a solução foi constante em toda esta face (slackness presumivelmente complementar iria revelar este)

Suresh Venkat

Existe alguma maneira de executar as etapas após a otimização inicial no tempo polinomial? Como está escrito, parece exigir a consideração de todos os vértices na face do alvo, dos quais pode haver muitos exponencialmente.

matus

d

$d$

v

$v$