A nonconvex, piecewise linear optimization problem (Q2640447): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Two algorithms for constructing a Delaunay triangulation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4760292 / rank | |||
Normal rank |
Revision as of 14:31, 21 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A nonconvex, piecewise linear optimization problem |
scientific article |
Statements
A nonconvex, piecewise linear optimization problem (English)
0 references
1991
0 references
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.
0 references
linear interpolation
0 references
Delaunay Decomposition
0 references
branch and bound
0 references