A Minmax Chebyshev Approach to Optimal Binary Classification

Abstract

Linear programming (LP) techniques for optimal binary classification have inspired research studies in recent years; they pose an alternative to the quadratic programming (QP) approach, which is usually credited with having greater complexity. In this paper, we describe an LP approach that is based on the minmax Chebyshev criterion, for which we demonstrate that it can determine an optimal solution with competitive properties. The approach is then extended so that two of the most attractive properties of the traditional QP approach (the direct formulation of the optimal classifier in higher dimensions and the sparseness of its coefficients) are preserved. The proposed method demonstrates its capabilities to successfully address situations that have separable and inseparable classes.