A region linear model optimization system optimizes a region linear model, and includes: a linear model setting unit 81 for setting for a partition a linear model to be applied to one of regions representing subspaces divided by the partition, the partition being an indicator function dividing an input space into two portions; and a region model calculation unit 82 for representing a model of each of the regions in the region linear model as a linear combination of the linear models to be applied to the respective regions.