Fitting piecewise linear continuous functions. (English) Zbl 1244.90166
Summary: We consider the problem of fitting a continuous piecewise linear function to a finite set of data points, modeled as a mathematical program with convex objective. We review some fitting problems that can be modeled as convex programs, and then introduce mixed-binary generalizations that allow variability in the regions defining the best-fit function’s domain. We also study the additional constraints required to impose convexity on the best-fit function.
MSC:
| 90C10 | Integer programming |
| 90C11 | Mixed integer programming |
| 90C20 | Quadratic programming |
| 65D10 | Numerical smoothing, curve fitting |
| 90C25 | Convex programming |
| 65K05 | Numerical mathematical programming methods |
| 41A30 | Approximation by other special function classes |
Keywords:
integer programming; quadratic programming; data fitting/regression; piecewise linear functionReferences:
| [1] | Abhishek, K.; Leyffer, S.; Linderoth, J., FilMINT: An outer approximation-based solver for convex mixed-integer nonlinear programs, INFORMS Journal on Computing, 22, 555-567 (2010) · Zbl 1243.90142 |
| [2] | Balas, E., Disjunctive programming: Properties of the convex hull of feasible points, Discrete Applied Mathematics, 89, 3-44 (1998) · Zbl 0921.90118 |
| [3] | Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wächter, A., Branching and bounds tightening techniques for non-convex MINLP, Optimization Methods and Software, 24, 597-634 (2009) · Zbl 1179.90237 |
| [4] | Bertsekas, D.; Tsitsiklis, J., Neuro-Dynamic Programming (1996), Athena Scientific · Zbl 0924.68163 |
| [5] | Bertsimas, D.; Shioda, R., Classification and regression via integer optimization, Operations Research, 55, 252-271 (2007) · Zbl 1167.90593 |
| [6] | Bienstock, D., Eigenvalue Techniques for Convex Objective, Nonconvex Optimization Problems, (Proceedings of the 14th International Conference on Integer Programming and Combinatorial Optimization, Lausanne, Switzerland, June 9-11. Proceedings of the 14th International Conference on Integer Programming and Combinatorial Optimization, Lausanne, Switzerland, June 9-11, Lecture Notes in Computer Science, Vol. 6080 (2010), Springer), 29-42 · Zbl 1285.90038 |
| [7] | Bonami, P.; Biegler, L.; Conn, A.; Cornuéjols, G.; Grossmann, I.; Laird, C.; Lee, J.; Lodi, A.; Margot, F.; Sawaya, N.; Wächter, A., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optimization, 5, 186-204 (2008) · Zbl 1151.90028 |
| [8] | Bot, R.; Lorenz, N., Optimization problems in statistical learning: Duality and optimality conditions, European Journal of Operational Research, 213, 395-404 (2011) · Zbl 1222.90079 |
| [9] | Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge University Press · Zbl 1058.90049 |
| [10] | Carnicer, J.; Floater, M., Piecewise linear interpolants to Lagrange and Hermite convex scattered data, Numerical Algorithms, 13, 345-364 (1996) · Zbl 0870.65004 |
| [11] | de Farias, I.; Zhao, M.; Zhao, H., A special ordered set approach for optimizing a discontinuous separable piecewise linear function, Operations Research Letters, 36, 234-238 (2008) · Zbl 1163.90758 |
| [12] | Ferrari-Trecate, G.; Muselli, M.; Liberati, D.; Morari, M., A learning algorithm for piecewise linear regression, (Marinaro, M.; Tagliaferri, R., Neural Nets: WIRN VIETRI-01, 12th Italian Workshop on Neural Nets (2001), Springer: Springer Germany) |
| [13] | Geißler, B.; Martin, A.; Morsi, A.; Schewe, L., Using piecewise linear functions for solving MINLPs, (Lee, J.; Leyffer, S., Mixed Integer Nonlinear Programming: The IMA Volumes in Mathematics and its Applications, Vol. 154 (2012), Springer: Springer Newyork), 287-314 · Zbl 1242.90132 |
| [14] | Gonin, R.; Money, A., Nonlinear \(L_p\) Norm Estimation (1989), CRC Press · Zbl 0569.62055 |
| [15] | Holmes, C.; Mallick, B., Bayesian regression with multivariate linear splines, Journal of the Royal Statistical Society, Series B, 63, 3-17 (1999) · Zbl 0979.62010 |
| [16] | Jeroslow, R.; Lowe, J., Modeling with integer variables, Mathematical Programming Study, 22, 167-184 (1984) · Zbl 0554.90081 |
| [17] | Jiang, Y., Klabjan, D., 2009. A branch-and-price algorithm for clusterwise linear regression. In: Presentation at the 20th International Symposium on Mathematical Programming.; Jiang, Y., Klabjan, D., 2009. A branch-and-price algorithm for clusterwise linear regression. In: Presentation at the 20th International Symposium on Mathematical Programming. |
| [18] | Lau, K.-N.; Leung, P.-L.; Tse, K.-K., A mathematical programming approach to clusterwise regression model and its extensions, European Journal of Operational Research, 116, 640-652 (1999) · Zbl 0993.62052 |
| [19] | Leyffer, S., Sartenaer, A., Wanufelle, E., 2008. Branch-and-Refine for Mixed-Integer Nonconvex Global Optimization. Technical report, Mathematics and Computer Science Division, Argonne National Laboratory. Preprint ANL/MCS-P1547-0908.; Leyffer, S., Sartenaer, A., Wanufelle, E., 2008. Branch-and-Refine for Mixed-Integer Nonconvex Global Optimization. Technical report, Mathematics and Computer Science Division, Argonne National Laboratory. Preprint ANL/MCS-P1547-0908. |
| [20] | Magnani, A.; Boyd, S., Convex piecewise-linear fitting, Optimization and Engineering, 10, 1-17 (2009) · Zbl 1273.65086 |
| [21] | Nemhauser, G.; Wolsey, L., Integer and Combinatorial Optimization (1999), John Wiley & Sons Inc. · Zbl 0944.90001 |
| [22] | Novoa, C.; Storer, R., An approximate dynamic programming approach for the vehicle routing problem with stochastic demands, European Journal of Operational Research, 196, 509-515 (2009) · Zbl 1163.90782 |
| [23] | Papadaki, K.; Powell, W., Exploiting structure in adaptive dynamic programming algorithms for a stochastic batch service problem, European Journal of Operational Research, 142, 108-127 (2002) · Zbl 1081.90605 |
| [24] | Pardalos, P.; Kundakcioglu, O., Classification via mathematical programming (survey), Applied and Computational Mathematics, 8, 23-35 (2009) · Zbl 1188.90289 |
| [25] | Pottmann, H.; Krasauskas, R.; Hamann, B.; Joy, K.; Seibold, W., On piecewise linear approximation of quadratic functions, Journal for Geometry and Graphics, 4, 31-53 (2000) · Zbl 0961.65011 |
| [26] | Powell, W., Approximate Dynamic Programming: Solving the curses of dimensionality (2007), John Wiley & Sons Inc · Zbl 1156.90021 |
| [27] | Queyranne, M.; Wang, Y., On the convex hull of feasible solutions to certain combinatorial problems, Operations Research Letters, 11, 1-11 (1992) · Zbl 0764.90070 |
| [28] | Rockafellar, R., Convex Analysis (1970), Princeton University Press · Zbl 0193.18401 |
| [29] | Ruppert, D.; Wand, M.; Carroll, R., Semiparametric Regression (2003), Cambridge University Press · Zbl 1038.62042 |
| [30] | Strikholm, B., 2006. Determining the number of breaks in a piecewise linear regression model. Technical report, Department of Economic Statistics and Decision Support, Stockholm School of Economics. SSE/EFI Working Paper Series in Economics and Finance, No. 648.; Strikholm, B., 2006. Determining the number of breaks in a piecewise linear regression model. Technical report, Department of Economic Statistics and Decision Support, Stockholm School of Economics. SSE/EFI Working Paper Series in Economics and Finance, No. 648. · Zbl 1106.62091 |
| [31] | Toriello, A.; Nemhauser, G.; Savelsbergh, M., Decomposing inventory routing problems with approximate value functions, Naval Research Logistics, 57, 718-727 (2010) · Zbl 1202.90021 |
| [32] | Vielma, J.; Keha, A.; Nemhauser, G., Nonconvex, lower semicontinuous piecewise linear optimization, Discrete Optimization, 5, 467-488 (2008) · Zbl 1190.90149 |
| [33] | Vielma, J.; Ahmed, S.; Nemhauser, G., Mixed-integer models for nonseparable piecewise linear optimization: Unifying framework and extensions, Operations Research, 58, 303-315 (2010) · Zbl 1226.90046 |
| [34] | Williams, H., Model Building in Mathematical Programming, fourth ed. (2007), John Wiley & Sons Ltd. |
| [35] | Wilson, D. 1998. Polyhedral Methods for Piecewise-Linear Functions. Ph.D thesis, University of Kentucky.; Wilson, D. 1998. Polyhedral Methods for Piecewise-Linear Functions. Ph.D thesis, University of Kentucky. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
