Let $Q=(q_{ij})\in \mathbb{R}^{n\times n}$ be a symmetric positive definite matrix. Consider the following optimization problem: $$(P)\min_{\boldsymbol{x}} \boldsymbol{x}^{\top}Q^{-1}\boldsymbol{x}$$ $$ \text{subject to } \| \boldsymbol{x} \|_\infty = 1 $$ where $Q^{-1}$ is the inverse of $Q$.

Obtain the optimal solution of (P) and the minimum constant $C$ (independent of $\boldsymbol{x}$ such that $$ \| \boldsymbol{x} \|_\infty \le C\sqrt{\boldsymbol{x}^{\top}Q^{-1}\boldsymbol{x}} $$ holds for every $\boldsymbol{x} \in \mathbb{R}^n$.

  • $\begingroup$ What have you attempted ? $\endgroup$ – Jean Marie Aug 18 '16 at 23:24

Let $\|x\|^2_{Q^{-1}}=x^TQ^{-1}x$. Let $\{e_i\}$ be the standard basis for $\mathbb R^n$. For each $i$, let $$ \lambda_i=e_i^TQe_i. $$ Note that $\lambda_i>0$ since $Q$ is positive definite. Let $$ C_1=\min\left\{\|x\|^2_{Q^{-1}}\mid\|x\|_\infty=1\right\}, $$ $$ C_2=\min_i\frac1{\lambda_i}. $$ Then $C_1=C_2$. To see this, consider any $x\in\mathbb R^n$ and fix $i$. Let $\mu=e_i^Tx$. Then $$\begin{eqnarray*} \left\|x-\frac{\mu}{\lambda_i}Qe_i\right\|^2_{Q^{-1}} &=&\|x\|^2_{Q^{-1}}-2\frac{\mu}{\lambda_i}e_i^TQQ^{-1}x +\frac{\mu^2}{\lambda_i^2}e_i^TQQ^{-1}Qe_i\\ &=&\|x\|^2_{Q^{-1}}-2\frac{\mu^2}{\lambda_i} +\frac{\mu^2}{\lambda_i}\\ &=&\|x\|^2_{Q^{-1}}-\frac{\mu^2}{\lambda_i} \end{eqnarray*}$$ Thus $$ \|x\|^2_{Q^{-1}}=\frac{\mu^2}{\lambda_i}+\left\|x-\frac{\mu}{\lambda_i}Qe_i\right\|^2_{Q^{-1}}. $$ Now suppose $\|x\|_\infty=1$. Then $|e_i^Tx|=1$ for some $i$, so the above gives $$ \|x\|^2_{Q^{-1}}\geq\frac1{\lambda_i}\geq C_2 $$ Hence $C_1\geq C_2$. Conversely pick $i$ such that $C_2=\frac1{\lambda_i}$. Let $y=Qe_i$ and let $$ x=\frac y{\|y\|_\infty}. $$ Note that $e_i^Ty=\lambda_i$, so the above equation gives $$ \|y\|^2_{Q^{-1}}=\lambda_i+\|y-Qe_i\|^2_{Q^{-1}}=\lambda_i. $$ Finally $\|y\|_\infty\geq|e_i^Ty|=\lambda_i$, so $$ \|x\|^2_{Q^{-1}}=\frac{\|y\|^2_{Q^{-1}}}{\|y\|_\infty^2} \leq\frac1{\lambda_i}=C_2. $$ Hence $C_1\leq C_2$.

| cite | improve this answer | |

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.