¿Cuál es la complejidad computacional de resolver un programa cuadrático con restricciones de desigualdad lineal?

Question

Soy consciente de varios métodos de solución y tengo varios solucionadores a mi disposición, pero no puedo, por mi vida, encontrar un análisis de la complejidad. En particular, estoy interesado en la complejidad de resolver el siguiente problema:

$$ \begin{aligned} & \underset{ x }{ \text{ minimize} } && || x_q - x || \\ & \text{subject to} && r_i^\intercal x \le c_i & i=1 \ldots n \end {alineado} $$

Dónde $x,x_q \in \mathbb{R}^d$. Lo que es, en palabras "encontrar el punto más cercano en un politopo a algún punto$x_q$". Un colega me dijo que es$O(n^3)$, pero no está seguro de eso. Además, ¿cómo se escala la complejidad con la dimensión? Lo es $O(d n^3)$?

Answer 1

El problema es usualmente denotado como la proyección de un punto en un polytope, y es una cuadrática convexa problema de optimización solucionable en el polinomio tipo. La complejidad es de alrededor de $O(n^3)$, pero revise los detalles, por ejemplo aquí

http://www.stanford.edu/~boyd/cvxbook/

Existen algunas especializadas algoritmo para las proyecciones, como por ejemplo en el caso en el que las desigualdades lineales realmente definir un simplex. Yo sugeriría usted para buscar en la internet para que.

Answer 2

El método de la fuerza bruta es la construcción de la polytope dado por las desigualdades lineales y, a continuación, encontrar el punto más cercano, para el punto dado, para cada cara de la polytope. Para el método de la fuerza bruta de la complejidad $O(n^3)$ parece razonable. Al parecer, el uso de programación cuadrática para tales cálculos de distancia es mal visto, porque me preguntó recientemente una muy similar pregunta y consiguió '(uso) de programación cuadrática para encontrar la distancia mínima es de acabar con las moscas con un martillo.' como respuesta. Tengo la idea de informática distancias con programación cuadrática de Dave Eberlys geométrica de herramientas'. Por ejemplo leer este significado de su. Él no dice nada acerca de la complejidad por desgracia.