4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I was within a couple of seconds of posting a counterexample, which has some negative elements in V. $\endgroup$ – Mark L. Stone Apr 7 at 19:52
  • $\begingroup$ 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 for $V = 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) $\endgroup$ – independentvariable Apr 7 at 19:54
  • $\begingroup$ 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). $\endgroup$ – Mark L. Stone Apr 7 at 20:06
  • $\begingroup$ @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? $\endgroup$ – independentvariable Apr 7 at 20:12
  • 1
    $\begingroup$ Good, you passed the pop quiz I embedded in the previous comment. $\endgroup$ – Mark L. Stone Apr 7 at 21:07
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Really good answer! Thanks for this. I did the same, but I had to expand the matrices in open form. This is shorter, nicer. $\endgroup$ – independentvariable Apr 8 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.