# NP-hardness of a bilinear program?

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?

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$.
• 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 – Neal Young Mar 12 '17 at 8:30