A nonconvex, piecewise linear optimization problem
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.
- Global optimization of separable objective functions on convex polyhedra via piecewise-linear approximation
- Piecewise-Linear Approximation Methods for Nonseparable Convex Optimization
- A geometric approach to global optimization
- An efficient algorithm for minimizing a multivariate polyhedral function along a line
- Maximin Problem and a Duality Theorem for Mixed‐Integer Quadratic Programming
- The MIN PFS problem and piecewise linear model estimation
- Piecewise linear methods for nonlinear equations and optimization
- A geometric approach to global optimization
- Linearly constrained global optimization via piecewise-linear approximation
- Global minimization via piecewise-linear underestimation
- Optimistic optimization for continuous nonconvex piecewise affine functions
- Enumerating Delaunay partitions and global optimization
- An algorithm for piece-wise indefinite quadratic programming problem
- Piecewise-convex maximization problems.
- Linear-programming approach to nonconvex variational problems
This page was built for publication: A nonconvex, piecewise linear optimization problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2640447)
