Linear programming with one quadratic equality constraint

Question

I have a problem that can be formulated as a linear program with one quadratic equality constraint:

where variable $x$ is an $n$-dimensional vector and $H$ is a positive semidefinite $n \times n$ matrix.

I know this optimization problem can always be solved by any semidefinite programming (SDP) or quadratically constrained quadratic programming (QCQP) solver. However, it would be very slow to use a general SDP solver if $x$ is large. Therefore, I am wondering whether there is any fast solution that can take advantage of the one quadratic equality constraint.

Answer 1

This issue is addressed in detail in Appendix C of Schulman et al.'s Trust Region Policy Optimization. They do not address the linear constraint, but you can compute the global optimum subject to the quadratic constraint, and if that is on the wrong side of the linear constraint the solution lies on the intersection the quadratic constraint, and the kernel of $A$, which reduces to their problem in a lower dimension.

Edit: I guess this depends on what you mean by $Ax\leq 0$. The above assumes that $A$ is a linear functional, but in that case I'm not sure why you didn't say $a^Tx\leq 0$