A nonconvex, piecewise linear optimization problem (Q2640447)

We assume that n points \(a^ 1,...,a^ n\in R^ m\) are given, and that \(p+1\) values \(f_{0j},f_{1j},...,f_{pj}\), are associated with each of the given points. We develop an algorithm to globally solve the problem: minimize \(\{f^ 0(x):\) \(f^ i(x)\leq b_ i\), \(i=1,...,p\}\), where each function \(f^ i\) \((i=0,...,p)\) is piecewise linear and continuous over the convex hull \({\mathbb{C}}\) of the points \(a^ 1,...,a^ n\). The definition of \(f^ i\) used is based on a ``Delaunay Decomposition'' of \({\mathbb{C}}\) into simplices and can be interpreted as the direct extension of the piecewise linear fit of a function of a single variable that agrees with given function values and interpolates between adjacent points for the others. This kind of approximation enjoys the property that the evaluation of any particular \(f^ i(x)\) entails the solution of a linear program. The overall problem becomes a ``two-stage'' problem. We develop a branch and bound algorithm, with linear programs defining the subproblems, to solve it.