On Linear Relaxation of Standard Quadratic Programming

Question

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?

Answer 1

The LP you have shown has optimal objective value equal to the minimum element of $Q$, for any symmetric $Q$, regardless of its definiteness.

This can be seen as follows:

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.