Untuk konkret pertimbangkan LP untuk menyelesaikan permainan zero-sum dua pemain di mana setiap pemain memiliki tindakan. Misalkan setiap entri dari matriks hasil A paling banyak 1 dalam nilai absolut. Untuk kesederhanaan, jangan membuat asumsi sparsity.
Misalkan runtime tersedia untuk memperkirakan nilai game ini.
Salah satu teknik untuk mendekati nilai ini adalah metode pembaruan multiplikatif (dikenal sebagai pembelajaran tanpa penyesalan dalam konteks ini). Ini memberikan kesalahan , di mana ˜ O menyembunyikan faktor log.
Saya tidak tahu persis seperti apa lanskap kesalahan untuk metode titik interior paling dikenal, tapi saya menduga kesalahannya adalah seperti .
Metode pembaruan perkalian memberikan kesalahan itu sebuah polinomial terbalik di . Metode titik interior memberikan kesalahan yang eksponensial kecil di T . Kesalahan yang terbaik dari keduanya karena itu perlahan-lahan menurun untuk sementara sampai titik interior menyusul, setelah itu kesalahan tiba-tiba jatuh dari tebing. Naluri saya menentang pengorbanan waktu / kesalahan terbaik yang berlaku dengan cara ini.
Pertanyaan saya :
Apakah ada algoritma untuk pemrograman linier perkiraan yang menghaluskan sudut kurva tradeoff waktu / kesalahan? Yaitu, suatu algoritma yang melakukan paling tidak sebaik yang terbaik dari keduanya untuk setiap nilai parameter waktu yang tersedia dan memiliki tradeoff waktu / kesalahan yang relatif mulus. Cara yang lebih cerdas untuk menggabungkan teknik pembaruan interior-poin dan multiplikasi daripada mengambil yang lebih baik dari keduanya adalah salah satu cara yang mungkin untuk mendapatkan algoritma seperti itu.
Referensi :
Pembaruan multiplikasi secara umum:
http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf
Pembaruan multiplikatif untuk game zero-sum:
http://dx.doi.org/10.1016/0167-6377(95)00032-0
Pembaruan berganda untuk menutupi / mengemas piringan hitam:
http://arxiv.org/PS_cache/arxiv/pdf/0801/0801.1987v1.pdf
Kertas titik interior asli:
http://math.stanford.edu/~lekheng/courses/302/classics/karmarkar.pdf
Interior-point dari perspektif matematika terapan:
Pemrograman Nonlinier Bertsekas , bagian 4.1.1.