Programación lineal con una restricción cuadrática de igualdad

Question

Tengo un problema que se puede formular como un programa lineal con una restricción de igualdad cuadrática:

donde la variable $x$ es un $n$ -y el vector de la dimensión $H$ es una semidefinida positiva $n \times n$ matriz.

Sé que este problema de optimización siempre puede ser resuelto por cualquier programación semidefinida (SDP) o programación cuadrática restringida (QCQP). Sin embargo, sería muy lento utilizar un solucionador SDP general si $x$ es grande. Por lo tanto, me pregunto si hay alguna solución rápida que pueda aprovechar la única restricción de igualdad cuadrática.

Answer 1

Véase la investigación de Martein y Schaible de 1987 sobre un método iterativo para encontrar soluciones al objetivo lineal con una restricción cuadrática

Answer 2

Esta cuestión se aborda en detalle en el Apéndice C del informe de Schulman et al. Optimización de la política de regiones de confianza . No abordan la restricción lineal, pero se puede calcular el óptimo global sujeto a la restricción cuadrática, y si está en el lado equivocado de la restricción lineal la solución se encuentra en la intersección la restricción cuadrática, y el núcleo de $A$ que se reduce a su problema en una dimensión inferior.

Editar : Supongo que esto depende de lo que se entienda por $Ax\leq 0$ . Lo anterior supone que $A$ es un funcional lineal, pero en ese caso no estoy seguro de por qué no has dicho $a^Tx\leq 0$