  This paper proposes a method for solving multivariate regression and
classification problems using piecewise linear predictors over a polyhedral
partition of the feature space. The resulting algorithm that we call PARC
(Piecewise Affine Regression and Classification) alternates between (i) solving
ridge regression problems for numeric targets, softmax regression problems for
categorical targets, and either softmax regression or cluster centroid
computation for piecewise linear separation, and (ii) assigning the training
points to different clusters on the basis of a criterion that balances
prediction accuracy and piecewise-linear separability. We prove that PARC is a
block-coordinate descent algorithm that optimizes a suitably constructed
objective function, and that it converges in a finite number of steps to a
local minimum of that function. The accuracy of the algorithm is extensively
tested numerically on synthetic and real-world datasets, showing that the
approach provides an extension of linear regression/classification that is
particularly useful when the obtained predictor is used as part of an
optimization model. A Python implementation of the algorithm described in this
paper is available at http://cse.lab.imtlucca.it/~bemporad/parc .
