×

Mathematical programming formulations for piecewise polynomial functions. (English) Zbl 1453.90164

Summary: This paper studies mathematical programming formulations for solving optimization problems with piecewise polynomial (PWP) constraints. We elaborate on suitable polynomial bases as a means of efficiently representing PWPs in mathematical programs, comparing and drawing connections between the monomial basis, the Bernstein basis, and B-splines. The theory is presented for both continuous and semi-continuous PWPs. Using a disjunctive formulation, we then exploit the characteristic of common polynomial basis functions to significantly reduce the number of nonlinearities, and to suggest a bound-tightening technique for PWP constraints. We derive several extensions using Bernstein cuts, an expanded Bernstein basis, and an expanded monomial basis, which upon a standard big-M reformulation yield a set of new MINLP models. The formulations are compared by globally solving six test sets of MINLPs and a realistic petroleum production optimization problem. The proposed framework shows promising numerical performance and facilitates the solution of PWP-constrained optimization problems using standard MINLP software.

MSC:

90C30 Nonlinear programming
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balas, E., Disjunctive programming and a hierarchy of relaxations for discret optimization problems, SIAM J. Algebraic Discrete Methods, 6, 3, 466-486 (1985) · Zbl 0592.90070
[2] Beale, EML; Tomlin, JA, Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables, OR, 69, 447-454, 99 (1970)
[3] Beaumont, N., An algorithm for disjunctive programs, Eur. J. Oper. Res., 48, 3, 362-371 (1990) · Zbl 0744.90062
[4] Biegler, L.T.: Simultaneous methods for dynamic optimization. In: Nonlinear Programming: Concepts, Algorithms, and Applications to Chemical Processes, Chap. 10, pp. 287-324. SIAM, New York (2010) · Zbl 1207.90004
[5] Bragalli, C.; D’Ambrosio, C.; Lee, J.; Lodi, A.; Toth, P., On the optimal design of water distribution networks: a practical MINLP approach, Optim. Eng., 13, 2, 219-246 (2012) · Zbl 1293.76045
[6] Ceria, S.; Soares, J., Convex programming for disjunctive convex optimization, Math. Program., 86, 3, 595-614 (1999) · Zbl 0954.90049
[7] Chen, X., Smoothing methods for nonsmooth, nonconvex minimization, Math. Program., 134, 1, 71-99 (2012) · Zbl 1266.90145
[8] Conn, AR; Mongeau, M., Discontinuous piecewise linear optimization, Math. Program., 80, 3, 315-380 (1998) · Zbl 0901.90163
[9] Curry, HB; Schoenberg, IJ, On Pólya frequency functions IV: the fundamental spline functions and their limits, J. d’Anal. Math., 17, 1, 71-107 (1966) · Zbl 0146.08404
[10] Dantzig, GB, On the significance of solving linear programming problems with some integer variables, Econometrica, 28, 1, 30-44 (1960) · Zbl 0089.16101
[11] Demeulenaere, B.; Pipeleers, G.; De Caigny, J.; Swevers, J.; De Schutter, J.; Vandenberghe, L., Optimal splines for rigid motion systems: a convex programming framework, ASME J. Mech. Des., 131, 10, 101004-101004-11 (2009)
[12] Eilers, PH; Marx, BD, Flexible smoothing with B-splines and penalties, Stat. Sci., 11, 2, 89-102 (1996) · Zbl 0955.62562
[13] Farouki, RT, The Bernstein polynomial basis: a centennial retrospective, Comput. Aided Geom. Des., 29, 6, 379-419 (2012) · Zbl 1252.65039
[14] Grimstad, B., A MIQCP formulation for B-spline constraints, Optim. Lett., 12, 4, 713-725 (2018) · Zbl 1423.90154
[15] Grimstad, B.; Foss, B.; Heddle, R.; Woodman, M., Global optimization of multiphase flow networks using spline surrogate models, Comput. Chem. Eng., 84, 237-254 (2016)
[16] Grimstad, B.; Sandnes, A., Global optimization with spline constraints: a new branch-and-bound method based on B-splines, J. Glob. Optim., 65, 3, 401-439 (2016) · Zbl 1372.90074
[17] Grimstad, B., et al.: SPLINTER: a library for multivariate function approximation with splines (2015). http://github.com/bgrimstad/splinter. Accessed 16 May 2015
[18] Hargraves, C.; Paris, SW, Direct trajectory optimization using nonlinear programming and collocation, J. Guid. Control Dyn., 10, 4, 338-342 (1987) · Zbl 0634.65052
[19] Hasan, MMF; Karimi, I., Piecewise linear relaxation of bilinear programs using bivariate partitioning, AIChE J., 56, 7, 1880-1893 (2010)
[20] Hastie, T.; Tibshirani, R.; Friedman, J., The Elements of Statistical Learning, Springer Series in Statistics (2009), New York: Springer, New York · Zbl 1273.62005
[21] Hiriart-Urruty, JB; Lemarechal, C., Convex Analysis and Minimization Algorithms \(II\)—Advanced Theory and Bundle Methods (1993), Berlin: Springer, Berlin · Zbl 0795.49002
[22] Hofmann, T.; Schölkopf, B.; Smola, AJ, Kernel methods in machine learning, Ann. Stat., 36, 3, 1171-1220 (2008) · Zbl 1151.30007
[23] Höllig, K., Finite Element Methods with B-Splines (2003), Philadelphia: Society for Industrial and Applied Mathematics, Philadelphia · Zbl 1020.65085
[24] Holmberg, K., Solving the staircase cost facility location problem with decomposition and piecewise linearization, Eur. J. Oper. Res., 75, 1, 41-61 (1994) · Zbl 0809.90093
[25] Jahanshahi, E., Grimstad, B., Foss, B.: Spline fluid models for optimization. In: Proceedings of the IFAC Symposium on DYCOPS, pp. 400-405, Trondheim (2016)
[26] Jeroslow, RG, Representability in mixed integer programming, I: characterization results, Discrete Appl. Math., 17, 223-243 (1987) · Zbl 0618.90069
[27] Jeroslow, RG, Representability of functions, Discrete Appl. Math., 23, 2, 125-137 (1989) · Zbl 0684.90066
[28] Keha, AB; de Farias Jr, IR; Nemhauser, GL, A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization, Oper. Res., 54, 5, 847-858 (2006) · Zbl 1167.90589
[29] Knudsen, BR; Foss, B., Shut-in based production optimization of shale-gas systems, Comput. Chem. Eng., 58, 54-67 (2013)
[30] Li, W., A conjugate gradient method for the unconstrained minimization of strictly convex quadratic splines, Math. Program., 72, 1, 17-32 (1996) · Zbl 0851.90088
[31] Lorentz, GG, Bernstein Polynomials (2013), New York: American Mathematical Soc., New York
[32] Luo, Y.: Simulation-based optimization over discrete sets with noisy constraints. Ph.D. Thesis, University of Miami (2011)
[33] Martinez, N.; Anahideh, H.; Rosenberger, JM; Martinez, D.; Chen, VC; Wang, BP, Global optimization of non-convex piecewise linear regression splines, J. Glob. Optim., 68, 3, 563-586 (2017) · Zbl 1377.90068
[34] Mercy, T.; Jacquod, N.; Herzog, R.; Pipeleers, G., Spline-based trajectory generation for CNC machines, IEEE Trans. Ind. Electron., 66, 8, 6098-6107 (2019)
[35] Misener, R.; Floudas, CA, GloMIQO: global mixed-integer quadratic optimizer, J. Glob. Optim., 57, 1, 3-50 (2013) · Zbl 1272.90034
[36] Misener, R.; Floudas, CA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 2, 503-526 (2014) · Zbl 1301.90063
[37] Natali, JM; Pinto, JM, Piecewise polynomial interpolations and approximations of one-dimensional functions through mixed integer linear programming, Optim. Methods Softw., 24, 4-5, 783-803 (2009) · Zbl 1180.90209
[38] Nesterov, Y., Smooth minimization of non-smooth functions, Math. Program., 152, 127-152 (2005) · Zbl 1079.90102
[39] Padberg, M., Approximating separable nonlinear functions via mixed zero-one programs, Oper. Res. Lett., 27, 1, 1-5 (2000) · Zbl 0960.90065
[40] Park, J.; Kim, Y.; Eom, I.; Lee, K., Economic load dispatch for piecewise quadratic cost function using Hopfield neural network, IEEE Trans. Power Syst., 8, 3, 1030-1038 (1993)
[41] Patrinos, P.; Sarimveis, H., Convex parametric piecewise quadratic optimization: theory, algorithms and control applications, Automatica, 47, 8, 1770-1777 (2011) · Zbl 1228.90121
[42] Piegl, LA; Tiller, W., The NURBS Book (1997), Berlin: Springer, Berlin · Zbl 0868.68106
[43] Posa, M., Kuindersma, S., Tedrake, R.: Optimization and stabilization of trajectories for constrained dynamical systems. In: 2016 IEEE International Conference on Robotics and Automation (ICRA), pp. 1366-1373 (2016)
[44] Prandoni, P.; Vetterli, M., Approximation and compression of piecewise smooth functions, Philos. Trans. Math. Phys. Eng. Sci., 357, 1760, 2573-2591 (1999) · Zbl 0941.94010
[45] Royset, JO, Approximations and solution estimates in optimization, Math. Program., 170, 479-506 (2018) · Zbl 1410.90241
[46] Sahinidis, NV, BARON: a general purpose global optimization software package, J. Glob. Optim., 8, 2, 201-205 (1996) · Zbl 0856.90104
[47] Scholtes, S., Nonconvex structures in nonlinear programming, Oper. Res., 52, 3, 368-383 (2004) · Zbl 1165.90597
[48] Schramm, H.; Zowe, J., A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results, SIAM J. Optim., 2, 1, 121-152 (1992) · Zbl 0761.90090
[49] Schumaker, LL, Spline Functions: Basic Theory (2007), Cambridge: Cambridge University Press, Cambridge · Zbl 1123.41008
[50] Sherali, HD, On mixed-integer zero-one representations for separable lower-semicontinuous piecewise-linear functions, Oper. Res. Lett., 28, 4, 155-160 (2001) · Zbl 0992.90049
[51] Shukla, R.; Dragotti, PL; Do, MN; Vetterli, M., Rate-distortion optimized tree structured compression algorithms for piecewise smooth images, IEEE Trans. Image Process., 14, 3, 343-359 (2005)
[52] Stubbs, RA; Mehrotra, S., A branch-and-cut method for 0-1 mixed convex programming, Math. Program., 86, 515-532 (1999) · Zbl 0946.90054
[53] Vecchietti, A.; Lee, S.; Grossmann, IE, Modeling of discrete/continuous optimization problems: characterization and formulation of disjunctions and their relaxations, Comput. Chem. Eng., 27, 3, 433-448 (2003)
[54] Vielma, JP, Mixed integer linear programming formulation techniques, SIAM Rev., 57, 1, 3-57 (2015) · Zbl 1338.90277
[55] Vielma, JP; Ahmed, S.; Nemhauser, G., Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions, Oper. Res., 58, 2, 303-315 (2010) · Zbl 1226.90046
[56] Vielma, JP; Nemhauser, GL, Modeling disjunctive constraints with a logarithmic number of binary variables and constraints, Math. Program., 128, 1-2, 49-72 (2011) · Zbl 1218.90137
[57] Vigerske, S.; Gleixner, A., SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework, Optim. Methods Softw., 33, 1-31 (2017)
[58] Vu, KK; D’Ambrosio, C.; Hamadi, Y.; Liberti, L., Surrogate-based methods for black-box optimization, Int. Trans. Oper. Res., 24, 3, 393-424 (2017) · Zbl 1366.90196
[59] Wang, W.; Pottmann, H.; Liu, Y., Fitting B-spline curves to point clouds by curvature-based squared distance minimization, ACM Trans. Graph., 25, 2, 214-238 (2006)
[60] Wechsung, A.; Barton, PI, Global optimization of bounded factorable functions with discontinuities, J. Glob. Optim., 58, 1, 1-30 (2014) · Zbl 1311.90114
[61] Wegman, EJ; Wright, IW, Splines in statistics, J. Am. Stat. Assoc., 78, 382, 351-365 (1983) · Zbl 0534.62017
[62] Womersley, RS; Fletcher, R., An algorithm for composite nonsmooth optimization problems, J. Optim. Theory Appl., 48, 3, 493-523 (1986) · Zbl 0562.90077
[63] Yuan, Y.; Fan, W.; Pu, D., Spline function smooth support vector machine for classification, J. Ind. Manag. Optim., 3, 3, 529-542 (2007) · Zbl 1166.90361
[64] Zang, I., Discontinuous optimization by smoothing, Math. Oper. Res., 6, 1, 140-152 (1981) · Zbl 0496.90069
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.