<p>In general, even approximating a global optimum of a quadratic program, the simplest case of a nonlinear program, is NP-Hard (<a href="http://web.cs.ucdavis.edu/~rogaway/papers/qp.pdf" rel="nofollow">http://web.cs.ucdavis.edu/~rogaway/papers/qp.pdf</a>), not to mention finding an exact solution of it (<a href="http://www.sciencedirect.com/science/article/pii/002001909090100C" rel="nofollow">http://www.sciencedirect.com/science/article/pii/002001909090100C</a>). </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-01-16T12:22:14.863Z
2016-01-16T12:50:50.520Z
2016-01-16T12:50:50.520Z
Kapoios
<p>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.</p>

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

<p>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 ?</p>

CC BY-SA 3.0
2013-04-18T02:06:58.200Z
You should be able reformulate the problem to have one decision vector. Then [see this](http://en.wikipedia.org/wiki/Quadratically_constrained_quadratic_program). To some extent the complexity will depend on whether the problem is convex.
Austin Buchanan
<ds.algorithms><optimization><convex-optimization><polynomial-time>
Poly-time Algorithm for Non-Linear Optimization
echuly
# Poly-time Algorithm for Non-Linear Optimization

(Asked by: username_0 on 2013-04-16)

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 ?

**Tags:** ds.algorithms, optimization, convex-optimization, polynomial-time
> **Comments:**
> **username_1**: You should be able reformulate the problem to have one decision vector. Then [see this](http://en.wikipedia.org/wiki/Quadratically_constrained_quadratic_program). To some extent the complexity will depend on whether the problem is convex.  

---

## 1 answers

### Answer by username_2 on 2016-01-16. Score: 2

In general, even approximating a global optimum of a quadratic program, the simplest case of a nonlinear program, is NP-Hard (<http://web.cs.ucdavis.edu/~rogaway/papers/qp.pdf>), not to mention finding an exact solution of it (<http://www.sciencedirect.com/science/article/pii/002001909090100C>).

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.


---

