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.A
Suponha que o tempo de execução esteja disponível para aproximar o valor deste jogo.
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.
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 .
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.
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.