# Analytically finding the maximizer of a trace optimization problem

$$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. • I was within a couple of seconds of posting a counterexample, which has some negative elements in V. Apr 7 '20 at 19:52 • So sorry Mark! I hate it when I steal someone's time, and apparently I just did... This problem kills me though, I checked many example and these are all optimized forV = diag(w)$. Example: n = 5; m = 5; A = rand(m,n); w = [0.1;0.3;0.5;0.05; 0.05]; %sums to 1 V = sdpvar(m); Objective = trace(A'*V*A); Constraints = [V(:) >= 0, sum(V(:)) == 1]; for i=1:m Constraints = [Constraints, sum(V(:,i))==w(i)]; end soltn = optimize(Constraints, -Objective, sdpsettings('solver', 'cplex')) V = value(V) w = value(w) Apr 7 '20 at 19:54 • A little tip, instead of for loop, you can just do sum(V,2)==w,sum(V,1)==w'. And of course, sum(V(:)) == 1 is redundant (which the LP presolve should recognize). Apr 7 '20 at 20:06 • @MarkL.Stone Very nice, yes you are right. also since$V$is symmetric only$ \operatorname{sum}(V,2)==w\$ is enough. Do you think what I want to prove is easy? Apr 7 '20 at 20:12
• Good, you passed the pop quiz I embedded in the previous comment. Apr 7 '20 at 21:07

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.

• Really good answer! Thanks for this. I did the same, but I had to expand the matrices in open form. This is shorter, nicer. Apr 8 '20 at 0:58