A $\sqrt{5}/2$-approximation algorithm for optimal piecewise linear approximations of bounded variable products

We investigate the optimal piecewise linear approximation of the bivariate product $ xy $ over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the approximation, while respecting a prescribed approximation error. First, we show how to construct optimal triangulations consisting of up to five simplices. Using … Read more

On Piecewise Linear Approximations of Bilinear Terms: Structural Comparison of Univariate and Bivariate Mixed-Integer Programming Formulations

Bilinear terms naturally appear in many optimization problems. Their inherent nonconvexity typically makes them challenging to solve. One approach to tackle this difficulty is to use bivariate piecewise linear approximations for each variable product, which can be represented via mixed-integer linear programming (MIP) formulations. Alternatively, one can reformulate the variable products as a sum of … Read more


A direct search method for the class of problems considered by Lewis and Torczon [\textit{SIAM J. Optim.}, 12 (2002), pp. 1075-1089] is developed. Instead of using an augmented Lagrangian method, a simplicial approximation method to the feasible set is implicitly employed. This allows the points our algorithm considers to conveniently remain within an \textit{a priori} … Read more