Imperfect detection and misclassification errors are often ignored in the context of invasive species management. Here we present an approach that combines spatially explicit models and an optimization technique to design optimal search and destroy strategies based on noisy monitoring observations. We focus on two invasive plants, melaleuca (Melaleuca quinquenervia) and Old World climbing fern (Lygodium microphyllum), which continue to cause important damages to the Everglades ecosystem. We present a methodological framework that combines Hidden Markov Random Field (HMRF, initially developed for image analysis) and linear programming to optimally search for invasive species. A benefit of this approach is that it accounts for the spatial structure of the system by using a spatially explicit modeling approach (i.e. HMRF), and does not require repeated visits to model the probability of occurrence of species. We found on simulated cases that our approach can lead to substantial improvements in control efficiency when compared to state of the art model-free approaches. For example, in the case of the old world fern, simulations showed that the optimal strategy would allow managers to control up to 34% more sites than with model-free approaches that ignored misclassification and imperfect detection. For melaleuca it was possible to control up to 20% more sites. The vast increase in imagery data obtained from different sources (e.g. unmanned aerial systems, and satellite) provides great opportunities to improve management of natural resources by applying modern computational methods such as the one we present. Our approach can substantially increases the efficiency of invasive species control by accounting for imperfect detection, misclassification error and the spatial structure of the system. Our approach is applicable to other systems and problems, for example it could be applied to the control of plant pathogens, or optimal extraction of resources (e.g. minerals or biological resources).