Extremal Covariance Duality Given real vectors $v$ and $r$ of the same size, what are the following? 


*

*$\inf\{v'R^{-1}v ~  \colon ~  R>0 \, , \, \text{diag}(R)= r\}$ 

*$\sup\{v'Rv ~ \colon  ~ R>0\, , \, \text{diag}(R)= r\}$


Note: $R > 0$ denotes positive definiteness, $x'$ denotes transpose, $\text{diag}(R)$ is the vector of the diagonal entries of matrix $R$.
 A: First, let us answer question 2. Write $R=Q'Q$, where $Q=[q_1,\dots,q_n]$, a square matrix with columns $q_1,\dots,q_n$. Let $v_i$ and $r_i$ denote the coordinates of the vectors $v$ and $r$. Then the problem can be rewritten as follows: maximize $\|Qv\|=\|\sum_i v_iq_i\|$ given $\|q_i\|^2=r_i$ for all $i$. Clearly, $\|Qv\|\le\sum_i |v_i|\,\|q_i\|=\sum_i|v_i|\,\sqrt{r_i}$. On the other hand,
$\|Qv\|=\sum_i\|v_i\|\,\sqrt{r_i}$ and $\|q_i\|^2=r_i$ for all $i$ if $q_i=(\text{sgn}\,v_i)\sqrt{r_i}u$ for all $i$, where $u$ is any unit vector, and $\text{sgn}\,v$ is defined as $1$ if $v\ge0$ and as $-1$ if $v<0$. So,
\begin{align}
 \sup\{v'Rv\colon R>0, \text{diag}(R)= r\} 
 &=\sup\{\|Qv\|\colon Q=[q_1,\dots,q_n], \|q_i\|^2=r_i\ \forall i\}^2 \\ 
 &=\Big(\sum_i|v_i|\,\sqrt{r_i}\Big)^2. 
\end{align}
Now let us answer question 1. Again, write $R=Q'Q$, where $Q=[q_1,\dots,q_n]$. Then $v'R^{-1}v=a'a=\|a\|^2$, where $a:=(Q')^{-1}v$, so that $Q'a=v$ or, equivalently, $a\cdot q_i=v_i$ for all $i$, where $\cdot$ denotes the dot product. Then the problem can be rewritten as follows: minimize $\|a\|^2$ given that $a\cdot q_i=v_i$ and $\|q_i\|^2=r_i$ for all $i$. Introducing vectors $u_i:=q_i/\sqrt{r_i}$, let us further rewrite the problem as this: 
$$\text{minimize $\|a\|^2$ given the conditions $a\cdot u_i=s_i$ and $\|u_i\|=1$ for all $i$, }$$
where $s_i:=v_i/\sqrt{r_i}$. 
Under these conditions, for each $i$ we have $\|a\|^2\ge(a\cdot u_i)^2=s_i^2$ and hence $\|a\|^2\ge\max_i s_i^2=:s^2$. Without loss of generality, $s^2=s_1^2$, so that $s_i^2\le s_1^2=s^2$ for all $i$. 
On the other hand, take any unit vector $u_1$ and let $a=s_1u_1$, so that condition $a\cdot u_1=s_1$ holds. Clearly, $\{a\cdot u\colon\|u\|=1\}=\{s_1u_1\cdot u\colon\|u\|=1\}=[-|s_1|,|s_1|]$. Since $s_i\in[-|s_1|,|s_1|]$ for all $i$, it follows that for each $i=2,\dots,n$ there is a unit vector $u_i$ such that condition $a\cdot u_i=s_i$ holds. Also, then we have $\|a\|^2=s_1^2\|u_1\|^2=s_1^2=s^2$. Thus, 
\begin{align}
 &\inf\{v'R^{-1}v\colon R>0, \text{diag}(R)= r\} \\ 
 &=\inf\{\|a\|^2\colon \text{ $a\cdot u_i=s_i$ and $\|u_i\|=1$ for all $i$}\} \\ 
 &=s^2=\max_i s_i^2=\max_i (v_i^2/r_i). 
\end{align}
A: Here is a solution inspired by Losif Pinelis, but addresses the existence of non-singular matrices (see comment to last answer).
First consider part 1, and for this first consider the case where $diag(R)= 1_N$, the "all ones vector", and $|v_1| > |v_2| > ... > |v_N|$.  Let $\{e_1,...,e_N\}$ be the natural basis, $q_i= (v_i/v_1 )e_1 + \sqrt{1-(v_i/v_1)^2} e_i$, $1\leq i\leq N$, $Q_0= [q_1, q_2, ..., q_N]$, $R_0= Q_0'Q_0$.  Note that by construction $||q_i||= 1$, $Q_0$ is upper-triangular with positive diagonal entries, and thus is non-singular.  Also note, $e_i'Q_0e_1= v_i/v_1$, so $Q_0^{-T}v= v_1e_1$, and thus, $v'R_0^{-1}v= v'Q_0^{-1}Q_0^{-T}v= ||Q_0^{-T}v||^2= ||v_1e_1||^2= v_1^2= ||v||_\infty^2$.  But given any non-singular $R$ with $R=R'$, and $diag(R)=1_N$, there exists a Cholesky factorization, $R= Q'Q$, and by the Cauchy-Schwartz Lemma, $v'R^{-1}v= ||Q^{-T}v||^2 >= (q_1'Q^{-T}v)^2=(e_1'Q^T Q^{-T}v)^2= v_1^2= ||v||_\infty^2$; so, $R_0$ is a global minimum; and $\min\{v'R^{-1}v\}= ||v||_\infty^2$.  Note, that in the above argument, the only critical property of $v$ is that it's elements are distinct, thus $\min\{v'R^{-1}v\}= ||v||_\infty^2$ holds for any distinct $v$, regardless of it's ordering.
Now consider the case where we still have $diag(R)= 1_N$, and $v$ sorted, but $v$'s entries are not distinct.  The $Q_0$ as constructed above is singular, but since $v'R^{-1}v$ is a continuous function of $R$ on a bounded set, it can be extended to $\inf\{v'R^{-1}v\}= ||v||_\infty^2$, where R is taken over the set of positive semi-definite matrices (not just positive definite matrices).
Finally, consider the more general case.  Let $\Lambda= diag(r)^{-1/2}$, and $w= \Lambda v$.  Also, for each $R$, let $G= \Lambda R \Lambda$, so $diag(G)= 1_N$.  Then, $\inf\{v'R^{-1}v\}= \inf\{v'\Lambda \Lambda^{-1} R^{-1} \Lambda^{-1} \Lambda v\}= \inf\{w'G^{-1}w\}= ||w||_\infty^2=||diag(r)^{-1/2}v||_\infty^2$.  This proves $\inf\{v'*R^{-1}v\}= ||diag(r)^{-1/2}v||_\infty^2$.
Now consider the second problem.  Let $w= diag(r)^{1/2}sign(v)$, and $R_0= ww'$.  So, $v'R_0 v= \sum{v_i v_j R_0[i,j]}= \sum{v_i v_j \sqrt{r_i} sign(v_i) \sqrt{r_j} sign(v_j)}= ||diag(r)^{1/2}v||_1^2$.  But given $R>0$, $|\sum{v_i v_j R[i,j]}|\leq \sum{|v_i v_j R_{i,j}|}\leq\sum{|v_i v_j \sqrt{r_i} \sqrt{r_j}|}= ||diag(r)^{1/2}v||_1^2$; so, $R_0$ is a global maximizer.  This proves $\sup{v'Rv}= ||diag(r)^{1/2}v||_1^2$.
Juxtaposing our solutions for parts 1 and 2, we have the following.
$\inf\{v'R^{-1}v:R>0, diag(R)=r\}= ||diag(r)^{-1/2}v||_\infty^2$
$\sup\{v'Rv:R>0, diag(R)=r\}= ||diag(r)^{1/2}v||_1^2$
which agrees with Losif Pinelis' answer, and when expressed this way, exhibits a shocking duality.  Is this a coincidence, or a hint at something deeper?
