Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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)?

share|improve this question
add comment

1 Answer 1

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.