Fairness in Machine Learning has become a concern, particularly if models are deployed in high-stakes decision-making. Most existing approaches aim to enforce fairness during training, but they face significant challenges for the scalability and the effectiveness of fairness enforcement. To address these limitations, we propose a method for training fair classifiers under multiple group and intersectional fairness constraints with high predictive performance. We combine an Augmented Lagrangian learning procedure with a tunable performance budget, which regulates the trade-off between fairness and utility. Experiments demonstrate that our method mitigates bias while scaling efficiently with increasing problem complexity. By adjusting the performance budget, we provide a flexible mechanism to balance fairness enforcement and predictive performance, offering a solution for real-world applications.