<p>Your objective is to minimize the convex function $-\sum_{i=1}^n(x_i−a_i)y_i$ subject to a system of linear constraints on the continuous variables $x_i$ and $y_i$.</p>

<p>Such convex minimization problems are polynomially solvable by so-called interior point methods; see for instance the book by Stephen Boyd and Lieven Vandenberghe: "Convex Optimization"; free pdf copy at: <a href="http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf" rel="nofollow">http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf</a></p>

CC BY-SA 3.0
2017-03-12T08:30:54.043Z
I may be mistaken but are you sure that function is convex?  I think $x\,y$ is neither concave nor convex over $[0,1]^2$.  [plot here](https://www.google.com/search?q=graph+of+x*y&oq=graph+of+x*y&gws_rd=cr&ei=rAbFWLO4GIvZU--3nbAI#q=graph+of+x*y+from+zero+to+one&*)
Neal Young
CC BY-SA 3.0
2015-01-18T17:40:56.417Z
2015-01-18T17:40:56.417Z
Gamow
<p>Given $a_i, b_i, c_i, d_{ij}\in [0,1]$ for $i,j\in [n]$ and $i\neq j$ such that $\sum_{i\in [n]} a_i=1$ and $d_{ij}=d_{ji}$. </p>

<p>I have the following bilinear program:</p>

<p>max $\sum_{i=1}^n (x_i-a_i)y_i$</p>

<p>subject to    </p>

<ul>
<li>$b_i\leq x_i\leq c_i$   for each $i\in [n]$;  </li>
<li>$0\leq y_i\leq 1$   for each $i\in [n]$;  </li>
<li>$y_i-y_j\leq d_{ij}$ for $i,j\in [n], i\neq j$;</li>
<li>$\sum_{i\in [n]} x_i=1$</li>
</ul>

<p>Write $f$ to be the solution. The question is to decide whether $f\geq \theta$ for some given rational $\theta\in [0,1]$. </p>

<p>This question is known to be in NP. But is it NP-hard? </p>

<cc.complexity-theory><np-hardness><optimization><quadratic>
NP-hardness of a bilinear program?
user22166
# NP-hardness of a bilinear program?

(Asked by: username_0 on 2014-04-24)

Given $a\_i, b\_i, c\_i, d\_{ij}\in [0,1]$ for $i,j\in [n]$ and $i\neq j$ such that $\sum\_{i\in [n]} a\_i=1$ and $d\_{ij}=d\_{ji}$.

I have the following bilinear program:

max $\sum\_{i=1}^n (x\_i-a\_i)y\_i$

subject to

* $b\_i\leq x\_i\leq c\_i$ for each $i\in [n]$;
* $0\leq y\_i\leq 1$ for each $i\in [n]$;
* $y\_i-y\_j\leq d\_{ij}$ for $i,j\in [n], i\neq j$;
* $\sum\_{i\in [n]} x\_i=1$

Write $f$ to be the solution. The question is to decide whether $f\geq \theta$ for some given rational $\theta\in [0,1]$.

This question is known to be in NP. But is it NP-hard?

**Tags:** cc.complexity-theory, np-hardness, optimization, quadratic


---

## 1 answers

### Answer by username_1 on 2015-01-18. Score: 2

Your objective is to minimize the convex function $-\sum\_{i=1}^n(x\_i−a\_i)y\_i$ subject to a system of linear constraints on the continuous variables $x\_i$ and $y\_i$.

Such convex minimization problems are polynomially solvable by so-called interior point methods; see for instance the book by Stephen Boyd and Lieven Vandenberghe: "Convex Optimization"; free pdf copy at: <http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf>

> **Comments:**
> **username_2**: I may be mistaken but are you sure that function is convex?  I think $x\,y$ is neither concave nor convex over $[0,1]^2$.  [plot here](https://www.google.com/search?q=graph+of+x*y&oq=graph+of+x*y&gws_rd=cr&ei=rAbFWLO4GIvZU--3nbAI#q=graph+of+x*y+from+zero+to+one&*)  

---

