On Linear Relaxation of Standard Quadratic Programming

Consider the following StQO problem where matrix $$Q$$ is indefinite: \begin{align*} \text{minimize} \quad & x^\top Qx \\ \text{subject to} \quad & e^\top x = 1, \\ & x \geq 0. \end{align*} Here, $$x$$ is a vector, $$Q$$ is a symmetric matrix, and $$e$$ is the vector of all ones.

Linear Relaxation of the StQO Problem:

Linear relaxation defined as: \begin{align*} z^*=\text{minimize} \quad & \text{tr}(QX) \\ \text{subject to} \quad & e^\top x = 1, \\ & e^\top X = x^\top, \\ & x, X \geq 0, \end{align*} where $$\text{tr}(QX):=\sum_{i,j}Q_{ij}X_{ij}$$.

Question: Is the optimal value of the above problem the minimum entry of matrix $$Q$$, i.e., $$z^*=\displaystyle\min_{1\leq i,j\leq n}~Q_{ij}$$? If not, could you provide an example demonstrating why this is not the case?

• Just to clarify, you are using "tr()" to denote trace, correct? (Many people use it to denote transpose.)
– prubin
Commented Jul 10 at 16:30
• @prubin I am quite sure tr means trace in this context. Commented Jul 10 at 17:07
• @prubin see the question please. Commented Jul 10 at 19:17

The LP you have shown has optimal objective value equal to the minimum element of $$Q$$, for any symmetric $$Q$$, regardless of its definiteness.
Sum over all elements of $$X$$ is 1. That is because by summing the 2nd constraint over all columns, the left-hand side is the sum of all elements of $$X$$; and the right-hand-side is the sum of all elements of $$x$$, which per the first constraint equals $$1$$. Therefore, the sum over all elements of $$X$$ is $$1$$.
Objective function of LP can be reformulated. Because $$Q$$ is symmetric, $$\text{trace}(QX) = \Sigma \Sigma (Q \odot X)$$ for any $$X$$, where $$\odot$$ denotes Hadamard (element-wise) product, and the double summation is over all elements (see 3rd bullet of Properties section of Wikipedia entry for Hadamard product) Therefore this holds for the optimal $$X$$.
It can easily be seen that because all elements of $$X$$ are nonnegative and sum to $$1$$, there must be an optimal solution for $$\Sigma \Sigma (Q \odot X)$$ and therefore optimal solution of the LP, consisting of $$X$$ being all zeros, except for $$1$$ in the element corresponding to a minimum element of $$Q$$. Therefore, the minimum element of $$Q$$ is the optimal objective value of the LP.