Entanglement detection is one of the most conventional tasks in quantum information processing. While most experimental demonstrations of high-dimensional entanglement rely on fidelity-based witnesses, these are powerless to detect entanglement within a large class of entangled quantum states, the so-called unfaithful states. In this Letter, we introduce a highly flexible automated method to construct optimal tests for entanglement detection given a bipartite target state of arbitrary dimension, faithful or unfaithful, and a set of local measurement operators. By restricting the number or complexity of the considered measurement settings, our method outputs the most convenient protocol which can be implemented using a wide range of experimental techniques such as photons, superconducting qudits, cold atoms, or trapped ions. With an experimental quantum optics setup that can prepare and measure arbitrary high-dimensional mixed states, we implement some three-setting protocols generated by our method. These protocols allow us to experimentally certify two- and three-unfaithful entanglement in four-dimensional photonic states, some of which contain well above 50% of noise.