Various constrained problem formulations for the optimization of an electro-thermal wing anti-icing system in both running-wet and evaporative regimes are presented. The numerical simulation of the system is performed by solving the conjugate heat transfer (CHT) problem between the fluid and solid domains. The optimization goal is to reduce the energy use and power demand of the anti-icing system while ensuring a safe protection. The formulations are carefully proposed from the physical and mathematical viewpoints; their performance is assessed by means of several numerical test cases to discern the most promising for each regime. The design optimization is conducted using the Mesh Adaptive Direct Search (MADS) algorithm using quadratic or statistical surrogate models in the search step. The influence of the models on the convergence rate and the quality of the obtained design solutions is investigated.