Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
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.
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}$.
