Changes between Version 24 and Version 25 of OfficialTolArchiveNetworkBysSamplerRandWalkInPolytope

Timestamp:

Feb 2, 2011, 9:30:06 AM (16 years ago)

Author:

Víctor de Buen Remiro

Comment:

--

OfficialTolArchiveNetworkBysSamplerRandWalkInPolytope

@@ -4 +4 @@
 == Descripción del problema ==
 Tenemos que generar una cadena de Markov de muestras que se distribuyan con cierta función de la 
-que se conoce su log-densidad salvo una constante, a la par que cumplen un conjunto de restricciones 
+que se conoce su log-densidad salvo una constante, 
+
+  [[LatexEquation( \ln \pi \left( x \right) )]]
+
+
+a la par que cumplen un conjunto de restricciones 
 de desigualdad lineal 
 
-[[LatexEquation( A x \le a \wedge x\in\mathbb{R}^{n} )]]
-
-[[LatexEquation( x\in\mathbb{R}^{n} )]]
-
-[[LatexEquation( a\in\mathbb{R}^{r} )]]
-
-[[LatexEquation( A\in\mathbb{R}^{r\times n} )]]
+  [[LatexEquation( A x \le a \wedge x\in\mathbb{R}^{n} )]]
+
+  [[LatexEquation( x\in\mathbb{R}^{n} )]]
+
+  [[LatexEquation( a\in\mathbb{R}^{r} )]]
+
+  [[LatexEquation( A\in\mathbb{R}^{r\times n} )]]
 
 
@@ -79 +84 @@
 Dado un punto [[LatexEquation(x)]] estrictamente interior al politopo 
 
-[[LatexEquation(A x < a)]]
+  [[LatexEquation(A x < a)]]
 
 la distancia al [[LatexEquation(i)]]-ésimo hiperplano viene dada por la fórmula
 
-[[LatexEquation( \left\langle x,\mathcal{H}\left(A_i,a_i\right)\right\rangle  = \frac{\left|\left(\overset{n}{\underset{j=1}{\sum}}A_{ij}x_{j}\right)-a_{i}\right|}{\overset{n}{\underset{j=1}{\sum}}A_{ij}^{2}}  \forall i=1\ldots r)]]
+  [[LatexEquation( \left\langle x,\mathcal{H}\left(A_i,a_i\right)\right\rangle  = \frac{\left|\left(\overset{n}{\underset{j=1}{\sum}}A_{ij}x_{j}\right)-a_{i}\right|}{\overset{n}{\underset{j=1}{\sum}}A_{ij}^{2}}  \forall i=1\ldots r)]]
 
 Llamaremos distancia de un punto a la frontera del politopo a la menor de las distancias a cada uno de sus hiperplanos, la cual por ser el punto interior ha de ser forzosamente positiva
 
-[[LatexEquation( \left\langle x,\mathcal{P}\left(A,a\right)\right\rangle =  \underset{i=1\ldots r}{min}\left\{ \left\langle x,\mathcal{H}\left(A_i,a_i\right)\right\rangle \} > 0 )]]
+  [[LatexEquation( \left\langle x,\mathcal{P}\left(A,a\right)\right\rangle =  \underset{i=1\ldots r}{min}\left\{ \left\langle x,\mathcal{H}\left(A_i,a_i\right)\right\rangle \} > 0 )]]
 
 Obsérvese que los hiperplanos inactivos nunca darán la distancia mínima para un punto factible por lo 
@@ -94 +99 @@
 será responsabilidad del analista no introducir demasiadas.
 
+=== Búsqueda de un punto inicial estrictamente interior ===
+
+Para encontrar un punto estrictamente interior hay que encontrar un punto que cumpla las restricciones 
+artificialmente aumentadas 
+
+  [[LatexEquation(A x \le a-\delta \wedge \delta>0 )]]
+
+que producirán un politopo reducido estrictamente interior al original.
+ç
+Es posible configurar el vector [[LatexEquation(\delta )]] para que la distancia mínima a la frontera 
+sea mayor que una cota mínima [[LatexEquation(\rho_0 )]] predefinida por el usuario
+
+  [[LatexEquation(\delta_i = \rho_0 {\overset{n}{\underset{j=1}{\sum}}A_{ij}^{2}} )]]
+  
+De esta forma si un punto está en el [[LatexEquation(i)]]-ésimo hiperplano del politopo reducido
+
+  [[LatexEquation(A_i x \le a_i-\delta_i = 0 )]]
+  
+entonces la distancia al politopo original será  
+
+  [[LatexEquation(\frac{\delta_i}{{\overset{n}{\underset{j=1}{\sum}}A_{ij}^{2}}} = \rho_0 )]]
+  
+Si se cuenta con un mecanismo capaz de optimizar la función de log-densidad con restricciones de desigualdad
+
+  [[LatexEquation( \min \ln \pi \left( x \right) )]]
+  [[LatexEquation(A x \le a-\delta \wedge \delta>0 )]]
+  
+
 === Paseo aleatorio hiperesférico ===
 Se propone en primer lugar utilizar un generador con distribución uniforme en una hiperesfera centrada 
@@ -99 +132 @@
 radio es menor que la distancia del punto a la frontera:
 
-[[LatexEquation( \begin{array}{c} y=x + h u\\ A y \leq a\\ \left\Vert u\right\Vert = 1 \\ 0 < h \le \rho < \left\langle x,\mathcal{P}\left(A,a\right)\right\rangle \end{array}  )]]
+  [[LatexEquation( \begin{array}{c} y=x + h u\\ A y \leq a\\ \left\Vert u\right\Vert = 1 \\ 0 < h \le \rho < \left\langle x,\mathcal{P}\left(A,a\right)\right\rangle \end{array}  )]]
 
 Al igual que se hace con los generadores simétricos habituales es necesario fijar un tamaño de paso 
@@ -106 +139 @@
 De esta forma se podría definir el radio de la hiperesfera como
 
-[[LatexEquation(\rho=\rho\left(x; s, \lambda\right)=min\left\{ s,\left\langle x, \lambda \mathcal{P}\left(A,a\right)\right\rangle \right\}  \wedge 0<\lambda<1)]]
+  [[LatexEquation(\rho=\rho\left(x; s, \lambda\right)=min\left\{ s,\left\langle x, \lambda \mathcal{P}\left(A,a\right)\right\rangle \right\}  \wedge 0<\lambda<1)]]
 
 Para poder muestrear puntos cercanos a la frontera sería conveniente que [[LatexEquation(\lambda)]] 
@@ -120 +153 @@
 La densidad del generador será porporcional al inverso del volumen de la hiperesfera y su logaritmo será, salvo una constante
 
-[[LatexEquation( \ln Q\left(x,y\right) = n \ln \rho\left(x; s, \lambda\right))]]
+  [[LatexEquation( \ln Q\left(x,y\right) = n \ln \rho\left(x; s, \lambda\right))]]
 
 La densidad depende por tanto del radio, el cual depende de la posición del punto de partida respecto
@@ -174 +207 @@
 uniforme en dicho intervalo
 
- [[LatexEquation( y = x + h u )]]
+  [[LatexEquation( y = x + h u )]]
  
- [[LatexEquation(u \wedge \left\Vert u\right\Vert = 1)]]
+  [[LatexEquation(u \wedge \left\Vert u\right\Vert = 1)]]
  
- [[LatexEquation(h \sim U\left[h^{-},h^{+}\right] \wedge h^{-} \le 0 \le h^{+}  )]]
+  [[LatexEquation(h \sim U\left[h^{-},h^{+}\right] \wedge h^{-} \le 0 \le h^{+}  )]]
 
 [[Image(source:/tolp/OfficialTolArchiveNetwork/BysSampler/doc/image/RandWalk.InPolytope.chart.726488582_c.png)]]
@@ -207 +240 @@
 
 Para evitar intervalos demasiado pequeños se puede relajar la condición del cuarto paso a que su 
-longitud sea mayor que cierto valor positivo predefinido
-
-[[LatexEquation( h^{+} - h^{-} > h_0 > 0)]],
+longitud sea mayor que la cota mínima predefinida
+
+  [[LatexEquation( h^{+} - h^{-} > \rho_0 > 0)]],