585. Mathematical programs with complementarity constraints and application to hyperparameter tuning for nonlinear support vector machines
Invited abstract in session MC-7: Bilevel Optimization in Data Science, stream Bilevel and multilevel optimization.
Monday, 14:00-16:00Room: B100/5015
Authors (first author is the speaker)
| 1. | Samuel Ward
|
| School of Mathematical Sciences, University of Southampton |
Abstract
We consider the Mathematical Program with Complementarity Constraints (MPCC). One of the main challenges in solving the problem is the systematic failure of standard Constraint Qualifications (CQs). The Mangasarian Fromovitz Constraint Qualification (MFCQ), for instance, does not hold for the MPCC when the problem is viewed from the lens of a standard optimisation problem with equality and inequality constraints. Carefully accounting for the combinatorial nature of the complementarity constraints, tractable versions of MPCC-tailored MFCQ have been designed and widely studied in the literature. In this presentation, we look closely at two such MPCC-tailored MFCQs and their influence in the convergence analysis of the sequential partial penalisation and Scholtes relaxation algorithms. Moreover, we go a step further and look at how these CQs would behave for the problem of tuning hyperparameters in a Support Vector Machine (SVM), a fundamental problem for classification algorithms in machine learning. Additionally, we present robust implementations and comprehensive numerical experimentation on real-world data sets, which show that the sequential partial penalisation method for the MPCC reformulation of the hyperparameter optimisation of a nonlinear SVM can outperform both the Scholtes relaxation technique and the state-of-the-art algorithms from the machine learning literature.
Keywords
- Complementarity and variational problems
- Multi-level optimization
- Optimization for learning and data analysis
Status: accepted
Back to the list of papers