1
$\begingroup$

I posted the question before show the quadratic function is quasi-concave. But I can not understand the only answer, and the author delated his account already. I rephrase my question and show my second attempt here. I have a quadratic function $W(x_1,x_2,\ldots,x_n)=A\sum_{i} x_i^2+ \sum_{i\neq j} x_ix_j$, with $x_i$ nonnegative and $A \in[0,1)$. And w.l.o.g. we can normalize $x_i's$ to between 0 and 1. In quadratic form, it is $W(x_1,x_2,\ldots,x_n)=X^TMX$, where $$M=\begin{bmatrix} A & 1 & 1 & \dots & 1 \\ 1 & A & 1 & \dots & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \dots & A \end{bmatrix}.$$ I want to show it is quasi-concave. First I checked $W$ is not concave or convex as $M$ is indefinite. A sufficient condition for (strictly) quasi-concavity of $W$ is that $$(-1)^kH_k(x)>0$$ for $k=1,2...,n.$ Where $H_k(x)$ is the $k-th$ order leading principal minor of the bordered Hessian matrix of $W(x)$:$$H(x)=\begin{bmatrix} 0 & 2A+2\sum_{i\neq1}x_i & 2A+2\sum_{i\neq2}x_i & \dots & 2A+2\sum_{i\neq n}x_i \\ 2A+2\sum_{i\neq1}x_i & 2A & 2 & \dots & 2 \\ 2A+2\sum_{i\neq 2}x_i & 2 & 2A & \dots & 2\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 2A+2\sum_{i\neq n}x_i & 2 & 2 & \dots & 2A \end{bmatrix}.$$ The determinant of this juggernaut (and all its leading principle minors) can be decomposed. $$H_k(x)=\begin{bmatrix} 0 & 2A+2\sum_{i\neq1}x_i & 2A+2\sum_{i\neq2}x_i & \dots & 2A+2\sum_{i\neq k}x_i \\ 2A+2\sum_{i\neq1}x_i & 2A & 2 & \dots & 2 \\ 2A+2\sum_{i\neq 2}x_i & 2 & 2A & \dots & 2\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 2A+2\sum_{i\neq k}x_i & 2 & 2 & \dots & 2A \end{bmatrix}.$$ Let the first row except leading 0 to be $D$, the first column except leading 0 to be $C$, denote the inner $k*k$ sub-matrix to be$$B=\begin{bmatrix} 2A & 2 & 2 & \dots & 2 \\ 2 & 2A & 2 & \dots & 2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 2 & 2 & 2 & \dots & 2A \end{bmatrix}.$$ Which turns out to be 2 times of matrix $M$. Then $$det(H_k(x))=det(B)det(0-DB^{-1}C).$$ I know the pattern of $det(B).$ to know whether the sufficient condition is satisfied, I just need to know the sign of $-DB^{-1}C$ which is a number. But as $B$ is indefinite, $B^{-1}$ is indefinite also, and I actually tried to write out $-DB^{-1}C$ but it is long, and I can not see a easy answer. Is the fact $2A+2\sum_{i\neq j}x_i<2n$ for any $j$ helpful?

Can anyone explain the answer in the original post? Or help me to find a way out here? Checking the bordered Hessian is a standard textbook method, but economist normally find shortcut specific to the context, however I am not able to find one.

This is my 3rd attempt: enter image description here But it seems we can not say $XY >=Y^2$ because we do not know the shape of $W(X)=W(Y)=C$, we are yet to prove it. It is possible the projection of $X$ onto $Y$ is shorter than $Y$ even though we assume $X$ is longer than $Y$.

$\endgroup$
0
$\begingroup$

We have with $\alpha=1-A\in (0,1]$: $$ M = -\alpha \ 1_n + e e^T$$ where $e^T=[1\ 1 \ ... \ 1]$. We set $$B(x,y)= x^T M y= -\alpha x^T y + (e^Tx)(e^Ty)\ \ \ \mbox{and} \ \ \ W(x)=B(x,x).$$

We wish to show that $W(x)$ is strictly quasi-concavity on $\Omega={\Bbb R}_+^n$. We note that $W$ is positive on $\Omega$. It suffices to show that if the conditions $x\neq y\in \Omega$ and $1=W(x)=W(y)$ hold then for all $t\in (0,1)$: $W(tx+(1-t)y)- 1=2t(1-t)(B(x,y)-1)>0$. So assume these conditions. We have (for $x_i,y_i\geq 0$): $$ 2x^T y < x^Tx + y^T y \ \ \mbox{and} \ \ (x^T y)^2 \leq (x^Tx) \ (y^T y)$$ which implies the inequality: $$ (e^T x)^2 (e^T y)^2 =(1 + \alpha x^T x) (1+ \alpha y^Ty) > (1 + \alpha x^T y)^2 $$ And from this we have: $$ (e^Tx)(e^Ty) > 1+ \alpha x^Ty \ \ \mbox{or} \ \ B(x,y)>1 $$ which is what we wanted to show.

$\endgroup$
  • $\begingroup$ thanks for help. I am not sure why you define $X^k_{+/-1}$, so I can not see why goes to infinite is incompatible. A function $W$ on a convex set $U\in R^n$ is strictly quasi-concave if for all $x,y\in U$, and all $t\in (0,1)$, $W(x)>W(y)$ implies $W(tx+(1-t)y)>W(y)$. The intuition is, mix between two points should be higher than the lower one. $\endgroup$ – Bob Aug 31 '16 at 23:20
  • $\begingroup$ in other words, why do we need the path $X^{k}_t$? $\endgroup$ – Bob Sep 1 '16 at 0:35
  • $\begingroup$ I defined the segment from $t=-1$ to $t=1$ but you may simply look at $x=-ke$ and $y=ke$. Then $W(1/2 x + 1/2 y) = 0$ which is strictly smaller than $W(x)=W(y)=k^2((A-1)n + n^2)$ (the value at end-points), which violates the condition for quasi-concavity $\endgroup$ – H. H. Rugh Sep 1 '16 at 0:39
  • $\begingroup$ Oh, i got it. But my domain is $[0,1]$, so this problem would not happen. I am at the positive orthant. $\endgroup$ – Bob Sep 1 '16 at 1:11
  • $\begingroup$ @Bob OK, sorry. I had missed that condition. Indeed it seems likely that you are right then. I'll think of why... $\endgroup$ – H. H. Rugh Sep 1 '16 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.