Is this a convex program?

Question

I have a nonlinear optimization problem

$\min \sum_{i=1}^n \sum_{j=1}^n y_{i,j}$

• subject to $x_i- y_{i,j}x_j\leq 0$
• $0\leq x_i\leq 1$
• $y_{i,j}>0$

The question is whether this is a convex program?

If not, how can I find an efficient solution?

Answer 1

No, it is not convex. Let $x_i$, $y_{ij}$ and $x_j$ have the values $(0,1/2,0)$ and $(1,1,1)$ and both those points are feasible, but the midpoint $(1/2,3/4,1/2)$ is not.

However, by writing the constraint as $x_ix_j^{-1}y_{ij}^{-1} \leq 1$, you have a geometric program (which can be solved efficiently by recasting the problem as a convex program through a variable change). Of course this assumes your additional constraints don't destroy the geometric programming structure (I presume there are more constraints, otherwise the solution is trivially $x = 0$, $y$ arbitrarily close to $0$)