Finding projection of a matrix on to a convex set

Question

I have a convex set $A$ defined as the set of symmetric matrices with entries containing values [-1,1].

I want to find the projection of another matrix $X$ on to $A$. Can anyone suggest a method to do it ?.

Answer 1

You want to find $Y \in A$ which is the solution of the following optimization problem:

\begin{align} \min & \quad \sum_{i,j} (X_{ij} - Y_{ij})^2 \\ \text{s.t.} & \quad -1 \le Y_{ij} \le 1, \quad \forall i,j \\ & \quad Y_{ij} = Y_{ji}, \quad \forall i,j. \end{align}

For the case $i=j$ it is simply $$ Y_{ii} = \begin{cases} 1, & \text{ if $X_{ii} > 1$}, \\ X_{ii}, & \text{ if $X_{ii} \in [-1, 1]$ }, \\ -1, & \text{ if $X_{ii} < 1$}. \end{cases} $$

For the case $i \ne j$, $Y_{ij} = Y_{ji}$ is the solution of the following $ \min_{Y_{ij} \in [-1, 1]} \ (X_{ij} - Y_{ij})^2 + (X_{ji} - Y_{ij})^2$, using method of Lagrange multiplier, we have $$ Y_{ij} = \begin{cases} 1, & \text{ if $X_{ij} + X_{ji} > 2$}, \\ \frac{X_{ij} + X_{ji}}{2}, & \text{ if $X_{ij} + X_{ji} \in [-2, 2]$}, \\ -1, & \text{ if $X_{ij} + X_{ji} < -2$}. \end{cases} $$