2
$\begingroup$

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<c_i<1$. 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.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – prubin
    Jul 25, 2023 at 21:34
  • $\begingroup$ @prubin Yes both $E$ and $d$ are additive. $\endgroup$ Jul 25, 2023 at 23:53
  • $\begingroup$ Cross-posted: math.stackexchange.com/questions/4742218/… $\endgroup$
    – RobPratt
    Jul 26, 2023 at 1:17
  • $\begingroup$ You said $y$ has dimension $m$ and $c$ has dimension $n$. Is one of those a typo? $\endgroup$
    – prubin
    Jul 26, 2023 at 15:27
  • $\begingroup$ Yes! $c$ has dimension $m$. Thanks for pointing this out. $\endgroup$ Jul 26, 2023 at 15:29

0

Your Answer

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