1
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Austin Buchanan Apr 18 '13 at 2:06
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.