I have follow optimization
$$\begin{array}{ll} \text{minimize} & f(\mathbf{X})= \| \mathbf{X} - \mathbf{A} \|_F^2\\ \text{subject to} & |\lambda_i(\mathbf{X}) - \lambda_{i+1}(\mathbf{X})| > c\\ &\mathbf{X} = \mathbf{X}^T \end{array}$$
where $\mathbf{A} \in R^{n \times n}$ is symmetric positive definite matrix. And $\mathbf{A}$ is the block diagoanl matrix. $\|\|_F^2$ is the matrix frobenius norm.
the $\lambda_i (\mathbf{X})$ is the $i$-th smallest eigenvalue of $\mathbf{X}$. $c$ and $i$ ($i \ll n$)are pre-defined constant number.
The constraint $|\lambda_i - \lambda_{i+1}| > c$ is the eigengap. The larger the eigengap is, the more stable of $\mathbf{X}$ when approximating the matrix $\mathbf{A}$.
The reason is here (page 17) http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/Luxburg07_tutorial_4488%5b0%5d.pdf
The motivation for this question is that: the $\mathbf{A}$ is usually partially observed and we want to recover the matrix $\mathbf{A}$ by obtain $\mathbf{X}$ with large eigengap. It can be regarded as a matrix completion problem.
my question is how to solve above optimization question under the constraint?
Taking off on Exodd's comment, since $A$ is symmetric, there is an orthogonal matrix $P$ such that $D = P^TAP$ is diagonal, with the eigenvalues in increasing order on the diagonal.
We solve the problem for $D$ instead of $A$. To solve it, if $d_{i+1\,i+1} - d_{ii} < c$, choose $x$ and let $y = c + d_{ii} + x - d_{i+1\,i+1}$. For any $j$, set $$d'_{jj} = \begin {cases} d_{jj} & d_{jj} \le d_{ii} - x\\ d_{ii} - x & d_{ii} - x < d_{jj} \le d_{ii}\\ d_{i+1\,i+1} + y & d_{i+1\,i+1} \le d_{jj} < d_{i+1\,i+1} + y\\ d_{jj} & d_{jj} \ge d_{i+1\,i+1} + y \end{cases}$$
Choose the value of $x$ that minimizes $\sum_j (d'_{jj} - d_{jj})^2$. The diagonal matrix $D'$ having $d'_{jj}$ as its diagonal elements is the solution to your problem in the special case when $A$ is diagonal. $X = PD'P^T$ is the solution to the general problem, since $\|D' - D\|_F = \|X - A\|_F$.
However, I doubt that algorithm will be of much use to you, since it requires knowing $A$, (and the rather difficult proposition of diagonalizing it). Unfortunately without knowing more about the problem (such as how you are calculating $\|X - A\|_F^2$ when you don't even know what $A$ is), I can't come up with an approach that would be useful.