Return to Question

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.

EDIT:

The inequality constraints I'm interested in are $0\leq x$ and $$ I_n\otimes 1_n' \leq \bar{x}, $$ where $\bar{x}$ is a $n\times 1$ column vector with elements $0<\bar{x_i}<1$ and $1_n$ is the $n\times 1$ column vector of ones.

If we think of $x$ as a $n^2\times 1$ column vector made of smaller $n\times 1$ vectors $z_j$ such that $x'=[z_1',\dots,z_n']$ then the last inequality constraint becomes $$ \sum_j z_{ij}\leq\bar{x}_i $$ for all $i$.

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.

EDIT:

The inequality constraints I'm interested in are $0\leq x$ and $$ (I_n\otimes 1_n')x \leq \bar{x}, $$ where $\bar{x}$ is a $n\times 1$ column vector with elements $0<\bar{x_i}<1$ and $1_n$ is the $n\times 1$ column vector of ones.

If we think of $x$ as a $n^2\times 1$ column vector made of smaller $n\times 1$ vectors $z_i$ such that $x'=[z_1',\dots,z_n']$ then the last inequality constraint becomes $$ \sum_j z_{ij}\leq\bar{x}_i $$ for all $i$.

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.

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.

EDIT:

The inequality constraints I'm interested in are $0\leq x$ and $$ I_n\otimes 1_n' \leq \bar{x}, $$ where $\bar{x}$ is a $n\times 1$ column vector with elements $0<\bar{x_i}<1$ and $1_n$ is the $n\times 1$ column vector of ones.

If we think of $x$ as a $n^2\times 1$ column vector made of smaller $n\times 1$ vectors $z_j$ such that $x'=[z_1',\dots,z_n']$ then the last inequality constraint becomes $$ \sum_j z_{ij}\leq\bar{x}_i $$ for all $i$.

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

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 positive definite.

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.

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.