# Nonlinear bad constraints

I have an optimization problem with linear objective function. The constraints are in two different groups. The first set of constraints are linear while the second set is nonlinear. The nonlinear constraints are in the form: $ab-cd \geq 0$.

-The optimization problem should be an instance of a convex optimization problem. right? - Is it polynomial solvable? - Is it possible to transformed it to a semidefinite optimization problem (SDP)?

-

## 1 Answer

No, constraints of the form $ab-cd\geq 0$ are not convex.

We can prove this by showing that the set $$\mathcal{C}\triangleq \{(a,b,c,d)\,|\,ab-cd\geq 0\}$$ fails the standard midpoint test for convex sets. That is, given any two points $(a_1,b_1,c_1,d_1)$ and $(a_2,b_2,c_2,d_2)$ in $\mathcal{C}$, the midpoint $$(a_3,b_3,c_3,d_3)=(a_1+a_2,b_1+b_2,c_1+c_2,d_1+d_2)/2$$ must be in $\mathcal{C}$ as well. Let us choose $$(a_1,b_1,c_1,d_1)=(2,2,1,1) \quad \text{and} \quad (a_2,b_2,c_2,d_2)=(-2,-2,1,1).$$ Since $a_ib_i-c_id_i=4-1=3\geq 0$ in both cases, both points are in $\mathcal{C}$. But the midpoint $$(a_3,b_3,c_3,d_3)=(0,0,1,1)$$ does not, since $a_3b_3-c_3d_3=0-1=-1\not\geq 0$. So the set is not convex.

Thus your problem is not a convex optimization problem. This necessarily means that it cannot be represented using semidefinite programming, either.

Unless you can somehow create a new, convex model for your application, you will not be able to solve it using convex methods.

-
Additional nonnegativity constraints on the variables might be enough to make the feasible set convex. If the original poster could provide more detail, it's possible that we could find an SDP formulation of his problem. –  Brian Borchers Apr 19 '13 at 20:53
Perhaps, though I don't quite see it. That said, after I wrote this I took a look at the poster's other questions, and I think it's clear that a more fundamental understanding of convexity is needed. –  Michael Grant Apr 19 '13 at 21:29