Some optimization problems with extremal operations (Q3347667)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3891134
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Some optimization problems with extremal operations |
scientific article; zbMATH DE number 3891134 |
Statements
Some optimization problems with extremal operations (English)
0 references
1984
0 references
L-infinity-approximation
0 references
nonconvex optimization
0 references
ordered algebraic structures
0 references
polynomial threshold algorithms
0 references
0.8915643
0 references
0.8840665
0 references
In a totally ordered, commutative, radicable group \((G,+,\leq)\) the absolute value \(| \alpha |:=\max (\alpha,-\alpha)\) is well- defined. For \(b_ i,a_{ij},\ell_ j,u_ j\in G\), \(1\leq i\leq n\), \(1\leq j\leq m\), an \(L_{\infty}\)-approximation problem is \[ \min_{1\leq x\leq u}\max_{1\leq i\leq n}| \max_{1\leq j\leq m}(a_{ij}+x_ j)- b_ i|. \] A genuine polynomial threshold algorithms is developed. Each addition, subtraction, comparison or square root evaluation, i.e. solving \(r+r=t\) for \(t\in G\), is counted as one basic operation. The algorithm determines a solution x in \(n(m-1)+m\) iterations where each iteration involves at most \(2n+6m-4\) additions/subtractions, \(2n+6m+8\) comparisons and m-1 square root evaluations.
0 references