¿Cuáles son las mejores compensaciones de tiempo / error posibles para la solución aproximada de programas lineales?

Para concretar, considere el LP para resolver un juego de suma cero de dos jugadores donde cada jugador tiene acciones. Suponga que cada entrada de la matriz de pagos A es como máximo 1 en valor absoluto. Para simplificar, no hagamos suposiciones de escasez.$n$$A$

Supongamos que el tiempo de ejecución está disponible para aproximar el valor de este juego.$T$

Una técnica para aproximar este valor es el método de actualización multiplicativa (conocido como aprendizaje sin arrepentimiento en este contexto). Esto da un error de , donde ~ O cueros factores de registro.$\tilde O(\sqrt{n/T})$$\tilde O$

No sé exactamente cómo se ve el panorama de errores para el método de punto interior más conocido, pero supongo que el error es algo como .$O(\exp(-T/n^3))$

Los métodos de actualización multiplicativos dan error que es un polinomio inverso en . Métodos de punto interior dan error que es exponencialmente pequeña en T . El error del mejor de los dos, por lo tanto, disminuye lentamente durante un tiempo hasta que el punto interior se recupera, después de lo cual el error cae repentinamente de un acantilado. Mis instintos están en contra de las mejores compensaciones posibles de tiempo / error que se comportan de esta manera.$T$$T$

Mi pregunta :

¿Existe un algoritmo para la programación lineal aproximada que suaviza la esquina de la curva de compensación de tiempo / error? Es decir, un algoritmo que funciona al menos tan bien como el mejor de los dos para cualquier valor del parámetro de tiempo disponible y tiene una compensación de tiempo / error relativamente suave. Una forma más inteligente de combinar técnicas de actualización de puntos interiores y multiplicativas que tomar la mejor de las dos es una forma probable de obtener dicho algoritmo.

referencias :

Actualización multiplicativa en general:

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

Actualización multiplicativa para juegos de suma cero:

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

Actualización multiplicativa para cubrir / empacar LP:

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

El documento original del punto interior:

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

Punto interior desde una perspectiva matemática aplicada:

Programación no lineal de Bertsekas , sección 4.1.1.

Quizás esta referencia sea relevante para su pregunta.

Grigoriadis M., Khachiyan L. Un algoritmo de aproximación aleatorio sublineal para juegos de matriz // Oper. Res. Letón. 1995. V. 18. No 2. P. 53-58.

El algoritmo es 1) aleatorizado 2) el error es ADITIVO, pero 3) es sublineal (solo necesita verificar una pequeña fracción de la entrada para encontrar una solución con alta probabilidad).

Sergey