What is the maximizer of $\max\frac{1}{2}\|U\|_F^2$ over ${0 \preceq U \preceq I,\text{Tr}(U) \leq k} $?

126 Views Asked by At

Suppose we have the following problem:

$$ \max_{0 \preceq U \preceq I,\text{Tr}(U) \leq k}\frac{1}{2}\|U\|_F^2 $$ where $U$ is a positive semi-definite matrix in $\mathbb{R}^{n \times n}$, $ k \leq n$, and $\|\cdot\|_F$ is the Frobenius norm.

What is the maximizer of this problem?

Note: The constraint set is bounded and convex, the objective function is also continuous so the problem has a global maximizer.

1

There are 1 best solutions below

7
On BEST ANSWER

$U$ is a symmetric matrix with eigenvalues $\lambda_1, \ldots, \lambda_n$ in $[0, 1]$.

One can also show that for such a matrix, $$\text{tr}(U) = \sum_{i=1}^n |\lambda_i|$$ $$\|U\|^2_F = \sum_{i=1}^n \lambda_i^2.$$

Thus the optimization problem can be restated purely in terms of the eigenvalues.

$$\max_{\lambda_i \in [0, 1], \sum_i |\lambda_i| \le k} \frac{1}{2} \sum_{i=1}^n \lambda_i^2.$$

Once we solve this problem, any matrix with the optimal eigenvalues will be a maximizer (so there is not a unique maximizer of the original problem).


I purposely left the rest of the problem for you to solve..., but since I am sitting in my room alone on Christmas I suppose I'll spell the rest out.

I will assume $k \in \{1, \ldots, n\}$. In the comments, JimmyK4542 has produced a feasible set of eigenvalues such that $\sum_{i=1}^n \lambda_i^2 = k$.

It remains to show that no other feasible set of eigenvalues can do better. Such eigenvalues satisfy $\lambda_i^2 \le \lambda_i$ for each $i$, so we have $\sum_{i=1}^n \lambda_i^2 \le \sum_{i=1}^n \lambda_i \le k$.

Thus, any permutation of $(\lambda_1, \ldots, \lambda_n) = (\underbrace{1, \ldots, 1}_k, 0, \ldots, 0)$ will be a solution. The solution to this optimization problem is also not unique.