Skip to main content
added 1402 characters in body
Source Link
Iosif Pinelis
  • 127.8k
  • 8
  • 107
  • 229

This is anFirst, let us answer to 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}

This is an answer to 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}

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}

edited body
Source Link
Iosif Pinelis
  • 127.8k
  • 8
  • 107
  • 229

This is an answer to 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} \max\{v'Rv\colon R>0, \text{diag}(R)= r\} &=\max\{\|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}\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}

This is an answer to 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} \max\{v'Rv\colon R>0, \text{diag}(R)= r\} &=\max\{\|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}

This is an answer to 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}

Source Link
Iosif Pinelis
  • 127.8k
  • 8
  • 107
  • 229

This is an answer to 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} \max\{v'Rv\colon R>0, \text{diag}(R)= r\} &=\max\{\|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}