Invisible Digital watermarks have been proposed as a method for discouraging illicit copying and distribution of copyright material. In recent years it has been recognized that embedding information in a transform domain leads to more robust watermarks. In particular, several approaches based on the Wavelet Transform have been proposed to address the problem of image watermarking. The advantage of the wavelet transform relative to the DFT or DCT is that it allows for localized watermarking of the image. A major di culty, however, in watermarking in any transform domain lies in the fact that constraints on the allowable distortion at any pixel are speci ed in the spatial domain. In order to insert an invisible watermark, the current trend has been to model the Human Visual System (HVS) and specify a masking function which yields the allowable distortion for any pixel. This complex function combines contrast, luminance, color, texture and edges. The watermark is then inserted in the transform domain and the inverse transform computed. The watermark is nally adjusted to satisfy the constraints on the pixel distortions. However this method is highly suboptimal since it leads to irreversible losses at the embedding stage because the watermark is being adjusted in the spatial domain with no care for the consequences in the transform domain. The central contribution of the paper is the proposal of an approach which takes into account the spatial domain constraints in an optimal fashion. The main idea is to structure the watermark embedding as a linear programming problem in which we wish to maximize the strength of the watermark subject to a set of linear constraints on the pixel distortions as determined by amasking function. We consider the Haar wavelet and Daubechies 4-tap filter in conjunction with a masking function based on a non-stationary Gaussian model, but the algorithm is applicable to any combination of transform and masking functions. Our results indicate that the proposed approach performs well against lossy compression such as JPEG and other types of filtering which do not change the geometry of the image.