Optimizing \(n\)-variate \((n+k)\)-nomials for small \(k\) (Q633624)

Let be \(a_j= (a_{1j},\dots, a_{nj})\), \(x= (x_1,\dots, x_n)\), \(x^{a_j}= x^{a_{1j}}_1\cdots x^{a_{nj}}_n\) and \(c_j\in\mathbb{R}^*\). A function \(f(x)= \sum^m_{j=1} c_j x^{a_j}\) is called a real \(n\)-variate \(m\)-nomial. Maximizing or minimizing of such polynomial functions is a central problem in science and engineering. A main result of the paper is the theorem: One can efficiently optimize \(n\)-variate \((n+k)\)-nomials over \(\mathbb{R}^n_+\) for \(k\leq 2\). Efficient algorithms are described. If \(k\) is a slowly growing function of \(n\), then the optimizing of \(n\)-variate \((n+k)\)-nomials is \(\text{NP}_{\mathbb{R}}\)-complete. In the proofs Viro diagrams are used as technical tools. For the case \(k= 2\) the nomials with integer exponents, the log of a certain condition number is sub-quadratic in the sparse size. Some illustrative examples and figures complete the paper.