# Solving a minimization problem with “scaled” equality constraint

Given a symmetric positive semi-definite matrix $Q\in\mathbb{R}^{n\times n}$, a vector $v\in\mathbb{R}^n$, a matrix $A\in\mathbb{R}^{m\times n}$ and a vector $b\in \mathbb{R}^m$ I'd like to solve the following optimization problem: $\min_x x^TQx\ \ \text{s.t.}\ \ Qx=(x^TQx)\, v\ ,\ Ax\ge b$

That is, we have a scaled equality constraint $Qx=av$ where $a=x^TQx$. Is there a name to such optimization problem? Are there solvers which can handle it?

Write it as the nonconvex quadratically constrained program $\min x^TQx$ s.t. $Qx = av, Ax \geq b, x^TQx = a$. When $Qx=av$ the constraint $a = x^TQx$ simplifies to $a = x^Tav$, i.e, $1 = x^Tv$ or $a=0$ Hence, you can solve the convex quadratic program $\min x^TQx$ s.t. $Qx = av, Ax \geq b, 1=x^Tv$, and another linear programming feasibility problem where you constrain $x$ to the nullspace of $Q$ (which would lead to $a=0$ and optimal objective $0$) $\min 0$ s.t. $Qx = 0, Ax \geq b$ and then you pick the best out of those two solutions.

• Can you constrain a problem on Qx=av when a is not known? What do I miss? – Uri Cohen Oct 12 '14 at 20:59
• @UriCohen: In the convex quadratic program Johan is proposing, let $a$ be another decision variable; the constraint $a = x^{T}Qx$ should be satisfied by construction. When $a$ is not known, $Qx = av$ for known $v$ is just a linear equality constraint. – Geoff Oxberry Oct 12 '14 at 21:23
• A general QP is given by $\min \frac{1}{2}z^T Qz+c^Tz$ subject to $Az\leq b, Ez = f$ so, as Geoff says, the addition of $Qx=av$ is just adding a linear equality (the decision variables are $z=(x,a)$ so you have $\begin{bmatrix}Q & -v \end{bmatrix} z=0$). – Johan Löfberg Oct 13 '14 at 7:30

I thought of the following approach: Denoting $a=x^TQx$ we may define $y=x/a$ and thus $a=x^TQx$ becomes $a=1/y^TQy$ and we have a constraint of $Qy=v$ so that

$\min_x x^TQx\ \ \text{s.t.}\ \ Qx=(x^TQx)\, v\ ,\ Ax\ge b$

will become now:

$\max_y y^TQy\ \ \text{s.t.}\ \ Qy=v\ ,\ (A-bv^T)y\ge \vec{0}$

where in the last them we use the fact that $1/a=y^TQy=v^Ty$ and thus we have inequality constraint $Ay\ge bv^Ty$ which can be written $(A-bv^T)y\ge \vec{0}$.

• Maximizing a convex quadratic function is NP-hard, so you don't want to do that. – Johan Löfberg Oct 15 '14 at 7:17