# Poly-time Algorithm for Non-Linear Optimization

As we know, linear programming is one of the most basic area of optimization theory, and computing an optimal solution can be excuted within poly-time. My question is about an extention of this notion.

Let $\vec{x}^T Q\vec{y} \geq \vec{d}$ be a system of multilinear constraints ,where $\vec{x},\vec{y} \in \mathbb{R}_{+}^n$

Question: Under some limitations on the matrix $Q$, can the task of minimizing(maximizing) a function $f(\vec{x},\vec{y})$, be solved within poly-time ,or is there any case where this optimization is NP-hard ?

• You should be able reformulate the problem to have one decision vector. Then see this. To some extent the complexity will depend on whether the problem is convex. – Austin Buchanan Apr 18 '13 at 2:06

The polynomial-time solvability of a nonlinear program depends on its convexity, which means that your matrix $Q\in R^{n\times n}$ should be positive semidefinite (i.e. $\forall x\in R^n,\,x^TQx\geq 0$). An easy way to check this in polynomial time is to check the sign of the smallest eigenvalue of $Q$. In the case of a convex quadratic program, you can simply deploy an interior-point algorithm for quadratic programming, which has a poly-time worst case complexity. These facts can be generalized for nonlinear programming.
As @Austin pointed, there's a way to convert your program to a Quadratically Constrained Quadratic Form. These problems are NP-Hard in general, but you can achieve an $\frac{4}{7}-$approximation of it's solution using an algorithm by Yinyu Ye, which solves an SDP-relaxation of the program.