Non-linear optimization programming

Question

How many methods do we have for non-linear optimization problems, which the target function is linear but constrains are polynomial shape? Are there methods which can solve most of them? Or what conditions we should have on constrains? Any easy short reference also can be useful.

Answer 1

One approach that should completely cover your case and far beyond as long as you can provide an initial bounding box is interval analysis. Hansen and Walter have a fairly comprehensive book on this, but a more targeted paper by Eldon Hanson from 1980 is Global optimization using interval analysis — the multi-dimensional case (CiteseerX PDF). There are many more resources out there. As an outline of the method, quoted from the above paper:

Our algorithm is composed of four separate parts. One part uses an interval version of Newton's method to find stationary points. A second part eliminates points of $X^{(0)}$ where $f$ is greater than the smallest currently known value $\bar f$.

A third part of our algorithm tests whether $f$ is monotonic in a sub-box $X$ of $X^{(0)}$. If so, we delete part or all of $X$ depending on whether $X$ contains boundary points of $X^{(0)}$.

A fourth part checks for convexity of $f$ in a sub-box $X$ of $X^{(0)}$. If $f$ is not convex, anywhere in $X$, there cannot be a stationary minimum of $f$ in $X$.

The key, of course, is interval arithmetic, where each time we do an arithmetic operation we keep a conservative lower and upper bound thus maintaining an interval which is guaranteed to contain the correct result.

---

As mentioned in my comment, the constraints or objective function being linear or not is not so important as them being convex or not. When the objective function and constraints are convex, the space of efficient and ergonomic optimization approaches explodes. I'm not aware of a non-convex optimization approach that is specialized to polynomial constraints. The interval analysis approach above, for example, only requires twice differentiable functions. The real dividing line tends to be around convex or not, and the particular form of the objective/constraint functions tends to be less critical.