I want to solve a nonlinear least squares problem on the following form \begin{equation} \begin{array}{l} \min_{\theta,\phi} J(\theta,\phi) &=& \min_{\theta,\phi} \sum_{i=1}^k ([p_0(a_i^T\phi), p_1(a_i^T\phi),\ldots, p_l(a_i^T\phi)]\theta-y_i)^2,\\ \end{array} \end{equation} where $\theta\in \Re^l$, $\phi\in \Re^m$. $a_i\in\Re^m$ and satisfy $a_i\succeq 0$. The constraints are \begin{equation} \begin{array}{lcl} \theta &\succeq& 0\\ \phi &\succeq& 0\\ \sum_{j=1}^m \phi_j &=& K \mbox{ (positive constant)}\\ \end{array} \end{equation} The last constraint implies that $a_i\phi\in[0,1]\, \forall i\in[1,k]$.

The one dimensional polynomials $p_i$ (derived from Bernstein polynomials) satisfy $p_i(0)=0$, $p_i(u)>0,\, u\in(0,1]$, $p_i^\prime(u),\, p_i^{\prime\prime}(u)\geq 0,\, u\in[0,1]$.

I think that I can solve this problem using some standard local optimization algorithm, and in most cases the solution $p^*$ will be close to the global optima. Now, I would like to find a condtion to verify that I have found the global optima. Unfortunately, the overall problem is large: $l\approx 7$ and $m\approx 8$. I have been looking at algorithms that finds all roots for multivariate polynomials, but they do not seem to handle this large problems. Another way to state the problem is that I want to verify that $J(\theta,\phi)-p^*$ is a positive polynomial in the feasible set. I have not found suitable algorithms for doing this either.

Perhaps, there is some smart way of doing this, considering the particular form of the polynomial $J$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.