[Math] Linear programming with one quadratic equality constraint

linear programmingnon-convex-optimizationoptimizationqclpquadratic programming

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

enter image description here

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.

Best Answer

Please see Martein & Schaible 1987 research on an iterative method to find solutions to linear objective with 1 quadratic constraint

Related Question