Although halftone image watermarking technologies have been rapidly developing in the 21 century, the existing techniques lack a theoretical basis. In this paper, we tackle halftone image watermarking problems from a theoretical perspective. First, we propose a general optimization framework for Halftone Visual Watermarking (HVW), which is a certain category of halftone image watermarking techniques. Then two specific HVW problems, Single-sided Embedding Error Diffusion (SEED) and Double-sided Embedding Error Diffusion (DEED) are presented and solved by applying the proposed framework. With SEED and DEED obtained, both the theoretical solutions and experimental results indicate that our previous heuristic methods, Data Hiding by Conjugate Error Diffusion (DHCED) and Data Hiding by Dual Conjugate Error Diffusion (DHDCED), are special cases of SEED and DEED, respectively. We also demonstrate that DEED can achieve outstanding performance compared to DHDCED and other previous methods by selecting different parameters. With this paper, we essentially build a bridge between the theory and practical implementations of HVW problems.