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$

2 Answers 2

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$
3
  • $\begingroup$ Can you constrain a problem on Qx=av when a is not known? What do I miss? $\endgroup$
    – Uri Cohen
    Oct 12, 2014 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$ Oct 12, 2014 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$ Oct 13, 2014 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$
1
  • 2
    $\begingroup$ Maximizing a convex quadratic function is NP-hard, so you don't want to do that. $\endgroup$ Oct 15, 2014 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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