NP-hardness of a bilinear program?

Question

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?

Answer 1

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