Analytically finding the maximizer of a trace optimization problem

Question

$A \in \mathbb{R}^{m \times n}$ is an arbitrary data matrix. Moreover, $w \in \mathbb{R}^m$ is a data vector which is a probability vector, i.e., $w\succeq 0, \sum_{i=1}^m w_i = 1$.

I have a symmetric matrix variable $V \in \mathbb{S}^{m \times m}$ and I am solving:

\begin{align*} \begin{array}{cll} \max \limits_{V \in \mathbb{S}^{n\times n}} & \mathrm{tr}(A^\top V A) & \\ \mathrm{s.t.}& \sum \limits_{j=1}^m V_{ij} = \sum\limits_{j=1}^m V_{ji} = w_i, & i=1,\ldots,m \\[0.2cm] & \sum\limits_{i=1}^m \sum\limits_{j=1}^m V_{ij} =1 &\\ & V_{i,j} \geq 0, & i=1,\ldots,m, j=1,\ldots,m. \end{array} \end{align*} So we can see that the $i$-th row and column of $V$ should sum to $w_i$ from the first constraint. The second constraint also implies that the elements of $V$ should sum to $1$. Last constraint says the elements of $V_{i,j}$ are nonnegative.

The thing is, in my various numerical experiments, I always have $V = \mathrm{Diag}(w)$, i.e., $V$ is a diagonal matrix where $i$-th diagonal element is $w_i$. Is this also observable from this maximization problem above (without any assumptions on $A$)?

The MATLAB code to observe this with various data (thanks to the improvement of Mark L. Stone) is:

n = 5;
m = 5;
A = rand(m,n)2; $generate whatever you like
w = [0.1;0.3;0.5;0.05; 0.05]; %sums to 1
V = sdpvar(m); %symmetric
Objective = trace(A'*V*A);
Constraints = [V(:) >= 0, sum(V(:)) == 1];
Constraints = [Constraints, sum(V,2)==w]; 
soltn = optimize(Constraints, -Objective, sdpsettings('solver', 'cplex'))
V = value(V)
w = value(w)

My attempt:

\begin{align} \mathrm{tr}(A^\top V A) = \mathrm{tr}( (AA^\top) V) = \sum_{i=1}^m \sum_{j=1}^m (AA^\top)_{i,j}V_{i,j} \end{align}

and if I can show that the coefficient of $V_{ii}$ which is $(AA^\top)_{ii}$ is larger than $(AA^\top)_{ij}$ for any $j$ then I guess we are done.

Edit: I proved it. It is a bit tedious, but I will type it soon.

Answer 1

Consider a feasible matrix $V$ for which $V \neq \text{Diag}(w)$. Then there exist indices $i \neq j$ such that $V_{ij} = V_{ji} > 0$.

Now construct a new matrix $W$ which is equal to $V$, except for the following four elements:

• $W_{ij} = W_{ji} = 0$,
• $W_{ii} = V_{ii} + V_{ij}$,
• $W_{jj} = V_{jj} + V_{ij}$.

It is straightforward to verify that $W$ is feasible.

By changing $V$ to $W$, the change in objective value is $$-2 (AA^\top)_{ij} + (AA^\top)_{ii} + (AA^\top)_{jj}.$$ Because $AA^\top$ is positive semi-definite, this value is non-negative, and the solution $W$ is not worse than $V$. By repeating this argument, it follows that $\text{Diag}(w)$ is optimal.