Tengo un cuadrática programa de la forma: \begin{align} \text{minimize} \quad & x^T Q x \\ \text{subject to} \quad & A x \leq b \\ & Cx = d \end{align} Me gustaría muestra del conjunto de posibles soluciones casi óptimas, es decir, $$ \{ x : \|x - x^\estrellas\|_p \text{ pequeños},\ Ax \leq b\ Cx = d\} $$ donde $p = 1$ o $p = 2$ son aceptables. No hay un límite en $\|x- x^\star\|_p$, pero lejana muestras no será casi seguramente útil para mi aplicación.
Respuesta
¿Demasiados anuncios?
Bey
Puntos
126
He aquí un simple aceptación-rechazo del algoritmo.
Tenga en cuenta que $Cx=d$ define un plano y $Ax\leq b$ define un convexo polytope.
Podemos expresar el espacio $V:= \{x:Cx=d\}$ en una base ortogonal $B$ y definir una distribución en base a esto (por ejemplo, multivariante de Gauss). A continuación, inicie la generación de puntos de $q$$V$, cada vez que la comprobación de si $\|q - x^\star\|_p <\epsilon$ $\ Ax \leq b$ algunos $\epsilon > 0$
Uno de los problemas con esto es que si la región factible, tiene una muy pequeña probabilidad dada su base y distribución elegida sobre esa base, entonces usted va a terminar el rechazo de una gran cantidad de puntos antes de aceptarlas.
Probablemente, usted puede mejorar su tasa de aceptación por centrar el modo de su distribución (asumiendo que es unimodal) en el punto óptimo.
Una alternativa es implementar la Cadena de Markov Monte Carlo de muestreo, lo que hará más fácil para evitar el cruce de la restricción de los límites. Hay un buen programa llamado Stan , que hace que este relativamente sencillo.
