We report an optimization approach to restore degraded binary images by using positive semidefinite programming when the point spread function (PSF) is known. The approach takes advantage of the combinatorial nature of the problem, considering not only local similarity and spatial context but also the relationship between individual pixel values and the PSF. Numerical experiments confirm the superiority of the approach.