Encontrar el punto más cercano, sujeto a restricciones de desigualdad lineal

Question

Dado un punto de $p\in \mathcal{R}^2$, quiero calcular el punto más cercano de la $x \in \mathcal{R}^2$, sujeto a la desigualdad lineal restricciones de $Ax \leq b$. Es decir,

$$\begin{array}{ll} \text{minimize} & \|x-p\|_2\\ \text{subject to} & A x \leq b\end{array}$$

Creo que esto se puede hacer con un off-the-shelf de programación cuadrática solver, pero me pregunto si hay un algoritmo más eficiente especializados para dos variables ($x \in \mathcal{R}^2$) y de la distancia Euclídea ($\min \|x - p\|$).

Creo que esta pregunta es un poco diferente a este debido a que no tienen una representación directa de la región factible, como una lista de vértices.

Answer 1

Esto se puede hacer en $O(N log(N))$ el tiempo, donde el $N$ es el número de filas en $A$.

La matriz de la desigualdad $Ax \leq b$ es equivalente a la mitad el plano de las desigualdades: $(a_i, x) \leq b_i, i = 1, \ldots, N$. Podemos obtener los vértices del polígono que es la intersección de estos la mitad de los aviones por el siguiente procedimiento:

1. Transformar las líneas de $\{(a_i, x) = b_i\} \mapsto d_i$ usando la dualidad de transformación: $\delta(\{a x + b y = 1\}) = (a, b)$.

2. Construir el casco convexo de $d_i$ usando uno de los algoritmos conocidos.

3. Mapa de los vértices y los lados de la obtenida casco convexo de vuelta al espacio primigenio: $\delta((a, b)) = \{a x + b y = 1\}$, $\delta(\{a x + b y = 1\}) = (a, b)$ y obtener el polígono $C_1 C_2 \ldots C_N$, que es este de la intersección de las iniciales de la mitad de los aviones.

4. Ahora que usted sabe todos los vértices del polígono y se pueden aplicar los citados métodos para su problema.

No estoy muy seguro de que esta es la mejor solución, sin embargo.

Si su tarea es repetible, es decir, usted tiene que repetir el problema para los diferentes $p$'s muchas veces, usted puede construir la dinámica convex hull y encontrar la distancia en $O(log(N))$ por cada consulta.