Sequential Minimal Optimization Extended to General Quadratic Programming

William Brendel, Luis Marujo
Event ICPRAI 2018
Research Areas Data Mining, Data Science, Natural Language Processing

Abstract: Nearly two decades ago Platt introduced the sequential minimal optimization (SMO) algorithm to solve the Support Vector Machine (SVM) dual quadratic programming optimization problem. SMO belongs to the family of Sequential Quadratic Programming (SQP) algorithms, and specifically aims to reduce the quadratic programming (QP) problem to its minimum at every iteration. As a result, SQP can be solved analytically and leads to an algorithm with linear time and space complexity. In 2005, Fan et al. summarized most of the optimization strategies that can be applied to solve the SVM QP problem with SMO in the well known LIBSVM library. Presently, other QP problems with similar form as the SVM QP dual problem are solved using more time and space consuming algorithms than mobile computational requirements allow. This research strives to discern the conditions that allow SMO to be extended to other QP problems and its complexity of solving the minimal QP at each iteration.

Index Terms: Quadratic optimization, Support vector machines, Natural language processing