Skip to main content
1 of 6

Does the value function of a quadratic program stay convex when adding constraints?

I am interested in the value function of a quadratic program of the form $$ v(y)=\min_x \frac{1}{2} x^\top Q(y) x, $$ subject to a linear equality constraint $$ E(y)x=d(y), $$ and a linear inequality constraint $$ A x \preceq b. $$ Notice that $Q$, $E$ and $d$ all depend on a parameter $y\in{\Bbb R}^m_{\geq 0}$. $Q(y)$ is positive definite for all $y$. Importantly, $A$ and $b$ do not depend on $y$.

For the particular problem I am interested in, I know $Q$, $E$, $d$, $A$ and $b$ but they are a bit complicated and I'm hoping that their specific structure is not important here.

I would like to show that $v$ is convex. Given my specific problem, I know that $v$ is convex if we remove the inequality constraint $A x \preceq b$. In that case the problem is simple and I can solve for $v$.

My question is: if $v$ is convex without the inequality constraint, does $v$ remain convex when we add the inequality constraint? Recall that this inequality constraint does not depend on $y$.

Notes:

  1. If that helps, in my specific problem $Q$ and $E$ are homogenous in the sense that $Q(\lambda y)=\lambda Q(y)$ and $E(\lambda y)=\lambda E(y)$ for any $\lambda\in{\Bbb R}$, and $d(y)=y-c$ where $c\in{\Bbb R}^n_{\geq 0}$. $E$ is also linear in $y$.
  2. I tried to compute $v$ using the dual approach but this seems intractable.
  3. I have looked at a few special cases and cannot find a counterexample.