Multiple Kernel Support Vector Machine Problem Is NP-Complete

摘要

In this work a polynomial-time reduction to the NP-complete subset sum problem is followed in order to prove the complexity of Multiple Kernel Support Vector Machine decision problem. The Lagrangian function of the standard Support Vector Machine in its dual form was considered to derive the proof. Results of this derivation allow researchers to properly justify the use of approximate methods, such as heuristics and metaheuristics, when working with multiple kernel learning algorithms.