Quais são as melhores compensações possíveis de tempo / erro para solução aproximada de programas lineares?

19

Para concretização, considere o LP para resolver um jogo de soma zero para dois jogadores em que cada jogador tem ações. Suponha que cada entrada da matriz de pagamento tenha no máximo 1 em valor absoluto. Para simplificar, não vamos fazer suposições de escassez.AnUMA

Suponha que o tempo de execução esteja disponível para aproximar o valor deste jogo.T

Uma técnica para aproximar esse valor é o método de atualização multiplicativa (conhecido como aprendizado sem arrependimentos neste contexto). Isso dá um erro de , onde ˜ O oculta fatores de log.O~(n/T)O~

Eu não sei exatamente como é o cenário de erros do método de ponto interior mais conhecido, mas acho que o erro é algo como .O(exp(-T/n3))

Os métodos de atualização multiplicativos dar erro que é um polinomial inversa em . Métodos de pontos interiores dar erro que é exponencialmente pequeno em T . O erro do melhor dos dois, portanto, diminui lentamente por um tempo até o ponto interior se aproximar, após o que o erro cai subitamente de um penhasco. Meus instintos são contra as melhores compensações possíveis de tempo / erro que se comportam dessa maneira.TT

Minha pergunta :

Existe um algoritmo para programação linear aproximada que suaviza o canto da curva de troca de tempo / erro? Ou seja, um algoritmo que funciona tão bem quanto o melhor dos dois para qualquer valor do parâmetro de tempo disponível e possui uma troca relativamente suave de tempo / erro. Uma maneira mais inteligente de combinar técnicas de atualização multiplicativa e de ponto interior do que tirar o melhor dos dois é uma maneira provável de obter esse algoritmo.

Referências :

Atualização multiplicativa em geral:

http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf

Atualização multiplicativa para jogos de soma zero:

http://dx.doi.org/10.1016/0167-6377(95)00032-0

Atualização multiplicativa para cobertura / embalagem de LPs:

http://arxiv.org/PS_cache/arxiv/pdf/0801/0801.1987v1.pdf

O papel de ponto interior original:

http://math.stanford.edu/~lekheng/courses/302/classics/karmarkar.pdf

Ponto interior de uma perspectiva matemática aplicada:

Programação Não Linear de Bertsekas , seção 4.1.1.

Warren Schudy
fonte

Respostas:

2

Talvez essa referência seja relevante para sua pergunta.

Grigoriadis M., Khachiyan L. Um algoritmo de aproximação aleatória sublinear para jogos de matriz // Oper. Res. Lett. 1995. V. 18. Não 2. P. 53-58.

O algoritmo é 1) randomizado 2) o erro é ADITIVO, mas 3) é sublinear (você precisa verificar apenas uma fração minúscula da entrada para encontrar um soluto com alta probabilidade).

Sergey

Sergey
fonte
Na verdade, esse papel é bastante relevante. É o segundo link fornecido na seção de referências da minha pergunta.
Warren Schudy
Perdão. Eu negligenciei que a referência já existe. Assim, meu comentário deve ser removido ou considerado como uma revisão de um dos textos da sua lista. Alguns resultados adicionais da mesma natureza, mas através de uma estrutura mais geral, podem ser encontrados em Juditsky, A., Lan, G., Nemirovski, A., Shapiro, A. Abordagem de aproximação estocástica à programação estocástica - SIAM Journal on Optimization 19: 4 (2009), 1574-1609. Sergey
Sergey