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

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

$\endgroup$
2
  • $\begingroup$ Just to be sure: does $E(y)=y'\otimes I_n$ mean that $E(y)x=(y_1 x_1+y_2 x_2+\dots +y_n x_n)$ where $x_i$ is the set of the successive entries of $x$ with indices from $(i-1)n+1$ to $in$ or something else? (that depends on how you split $x\in \mathbb R^{n^2}$ and you didn't specify that explicitly). $\endgroup$
    – fedja
    Commented Jul 26, 2023 at 16:34
  • $\begingroup$ Yes. $E(y)=[I_ny_1,\dots,I_ny_n]$. $x$ is basically 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 each row $i$ of the equality constraint is $\sum_j y_{j}z_{ji}=y_i-c_i.$ $\endgroup$ Commented Jul 26, 2023 at 16:46

1 Answer 1

4
$\begingroup$

Not necessarily as written in the generality you want. Suppose that we are in $\mathbb R^1$, there is no linear constraint, and $Q(y)$ is some positive function of $y$. Then $v(y)\equiv 0$, which is convex. Now add the condition $x<-1$. Then $v(y)=Q(y)$ and that can be absolutely anything.

On the other hand, you, probably, know that $v(y)$ is convex for some particular reason coming from certain properties of $Q,E,d$ (I'm not yet sure the ones you listed will suffice in higher dimensions, so you'd better tell the whole story of how you prove the convexity and what you use there) and we can certainly discuss whether in that particular situation restricting $x$ to a fixed convex polyhedron (not necessarily bounded) will preserve convexity or even the convexity proof.

Edit: With arbitrary $A$ and $b$ you are still in a bad shape. Indeed, let $n=2$, $x_1,x_2$ be the partition of $x$ into the vectors of length $2$, and suppose that $Ax\le b$ is equivalent to $x_1=x_2$. Let $c=0$. Then you have no choice but to take $x_1=x_2=\frac y{y_1+y_2}$. Now let $F_1=I_2, F_2=0$. Then $$ v(y)=y_1\frac{y_1^2+y_2^2}{(y_1+y_2)^2} $$ which on the interval $y_1=t, y_2=1-t$ ($0<t<1$) is $t[t^2+(1-t)^2]=2t^3-2t^2+t$, so it is obviously not convex near $0$. Thus, some restrictions on $A$ and $b$ should be added before we can hope for a positive answer. What can you offer?

Edit 2. In this restricted setting you are fine. Let $\Phi(x,y)=\sum_{i=1}^n y_i\langle F_i z_i, z_i\rangle$ (in your notation) be the objective function. Let $y',y''$ be any 2 vectors and $x',x''$ the corresponding minimizers. Then $x$ given by $z_i=\frac{y'_i}{y'_i+y''_i}z'_i+\frac{y''_i}{y'_i+y''_i}z''_i$ is still an admissible vector for $\frac{y'+y''}2$(what is really used here is that our linear restrictions on $z_i$ are totally separated from one another, so we can take different convex combinations for different $z_i$ without leaving the domain). However, by the convexity of $z\mapsto \langle Fz,z\rangle$ for a positive definite $F$, we have $$ \frac{y'_i+y''_i}2 \langle F_i z_i,z_i\rangle\le \frac 12 [y'_i \langle F_i z'_i,z'_i\rangle + y''_i \langle F_i z''_i,z''_i\rangle] $$ for each $i$, so $$ v(\tfrac{y'+y''}2)\le \Phi(x,\tfrac{y'+y''}2)\le \frac 12[\Phi(x',y')+\Phi(x'',y'')]=\frac 12[v(y')+v(y'')]\,. $$

$\endgroup$
9
  • $\begingroup$ Thanks for your comment. I have added more information about my particular case. $\endgroup$ Commented Jul 26, 2023 at 14:43
  • $\begingroup$ @user_lambda Still "Not necessarily". Your only hope is some extra properties of $A$ and $b$, so what can you say about them? $\endgroup$
    – fedja
    Commented Jul 26, 2023 at 17:54
  • $\begingroup$ Thanks that's very helpful. I've edited the question to add specific expressions for $A$ and $b$. $\endgroup$ Commented Jul 26, 2023 at 18:53
  • $\begingroup$ @user_lambda And you still want the entries of $x$ to be non-negative, but the entries of PD matrices $F_i$ are unrestricted, right? $\endgroup$
    – fedja
    Commented Jul 26, 2023 at 19:31
  • 1
    $\begingroup$ @user_lambda Then, unless I misunderstood you somewhere, you are in good shape. See my last edit :-) $\endgroup$
    – fedja
    Commented Jul 26, 2023 at 20:01

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.