On finding global optima for the hinge fitting problem

C. Humes, J. Júdice and M. Queiroz

Abstract

This paper considers the data fitting of n given points in Rⁿ by a hinge fuction, as it appears in Breiman (IEEE Trans on Info Theory 1993; 39:999-1013) and Pucar & Sjoberg (IEEE Trans on Info Theory 1998; 44(3) 1310-1318). This problem can be seen as a mathematical programming problem with a convex objective function and equilibrium constraints. For the euclidean error, an enumerative approach is proposed, which is a polynomial method for the sample size n, for a fixed dimension m. An alternative formulation for the l1 error is also introduced, which is processed by a Sequential Linear Complementarity approach. Some numerical results with both algorithms are included to highlight the efficiency of those procedures.