# Solve the optimization problem min $\boldsymbol{x}^{\top}Q^{-1}\boldsymbol{x}$ subject to $\| \boldsymbol{x} \|_\infty = 1$

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

• What have you attempted ? – 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$.