9
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ The Martein & Schaible paper refers to quadratic inequality constraints (i.e. a convex QCQP), and does not address the user's question about a quadratic equality constraint. $\endgroup$ – emunsing Jan 5 '16 at 19:03
  • $\begingroup$ Any $x$ s.t. $x^THx<c$ can be scaled by $\lambda>1$ to achieve equality, increasing the magnitude of $f^Tx$. $\endgroup$ – Alex Coventry Jun 3 '17 at 22:58
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.