2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you constrain a problem on Qx=av when a is not known? What do I miss? $\endgroup$ – Uri Cohen Oct 12 '14 at 20:59
  • $\begingroup$ @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. $\endgroup$ – Geoff Oxberry Oct 12 '14 at 21:23
  • $\begingroup$ 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$). $\endgroup$ – Johan Löfberg Oct 13 '14 at 7:30
0
$\begingroup$

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}$.

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

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.