# 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,$$ where $$\preceq$$ denotes component-wise inequalities.

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}^m_{\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.

Value function without inequality constraints

Without the inequality constraint, the solution to this problem is given by

$$\left[\begin{array}{cc} Q & E'\\ E & 0 \end{array}\right]\left[\begin{array}{c} x\\ \lambda \end{array}\right]=\left[\begin{array}{c} 0\\ d \end{array}\right]$$ which can be inverted as $$\left[\begin{array}{cc} Q & E'\\ E & 0 \end{array}\right]^{-1}=\left[\begin{array}{cc} Q^{-1}-Q^{-1}E'\left(EQ^{-1}E'\right)^{-1}EQ^{-1} & Q^{-1}E'\left(EQ^{-1}E'\right)^{-1}\\ \left(EQ^{-1}E'\right)^{-1}EQ^{-1} & -\left(EQ^{-1}E'\right)^{-1} \end{array}\right]$$ Since $$Q$$ is positive definite it is invertible. Suppose that $$EQ^{-1}E'$$ is also invertible. Then $$x=Q^{-1}E'\left(EQ^{-1}E'\right)^{-1}d$$ and the objective function at the optimum is $$v(y)=d'\left(\left(EQ^{-1}E'\right)^{-1}\right)d$$

My particular problem

In my particular problem $$x\in{\Bbb R}_{\geq 0}^{n^2}$$ and $$y\in{\Bbb R}_{\geq 0}^{n}$$. The function $$E$$ and $$d$$ are $$E(y)=y'\otimes I_n,$$ and, $$d(y)=y-c,$$ where $$c$$ is a $$n\times 1$$ column vector such that $$0. The matrix $$Q(y)$$ is given by $$Q=\left[\begin{array}{ccc} y_{1}F_{1} & & 0\\ & \ddots\\ 0 & & y_{n}F_{n} \end{array}\right]$$ where $$F_i$$ is an $$n\times n$$ positive definite matrix.

Doing the matrix algebra, and using the expression for $$v$$ above, we find $$v(y)=\left(y-c\right)'\left(\sum_{i}y_{i}F_{i}^{-1}\right)^{-1}\left(y-c\right)$$ A proof of convexity for this function can be found here.

• Is $E$ additive (which would make it linear) or just homogeneous? A key issue is whether, given feasible $\hat{y}$ and $\tilde{y}$ and $\lambda\in (0,1),$ the constraint $E\left(\lambda \hat{y} + (1-\lambda)\tilde{y}\right)x=d\left(\lambda \hat{y} + (1-\lambda)\tilde{y}\right)$ has a solution in the polyhedron of feasible $x$ values.
– prubin
Jul 25, 2023 at 21:34
• @prubin Yes both $E$ and $d$ are additive. Jul 25, 2023 at 23:53
• Cross-posted: math.stackexchange.com/questions/4742218/… Jul 26, 2023 at 1:17
• You said $y$ has dimension $m$ and $c$ has dimension $n$. Is one of those a typo?
– prubin
Jul 26, 2023 at 15:27
• Yes! $c$ has dimension $m$. Thanks for pointing this out. Jul 26, 2023 at 15:29