I want to solve the problem \min_{a \in A, b \in B} \langle a, b \rangle where A and B are non-empty compact convex sets. If I just ignore the constraints for now, the code I have is
n = 10;
cvx_begin
variable a(n);
variable b(n);
minimize( a’*b );
cvx_end
and the error I get is
Error using cvx/quad_form (line 203)
The second argument must be positive or negative semidefinite.
Error in cvx/mtimes (line 262)
[ z2, success ] = quad_form( xx, P, Q, R );
Error in test (line 5)
minimize( a’*b );
I also get the same error for any constraints, for example, norm(a) <= 1 and norm(b, 1) <= 1. Any ideas what may be wrong?
Your objective is not linear, and is not convex. Hence the error, although the exact error message may not be particularly informative. If only one of a and b were a CVX variable, with the other being a MATLAB variable, then your objective would be linear. However, given that you mention constraints on both a and b, I presume that that is not your intention.
I don’t know why norm(a) <= 1 or norm(b, 1) <= 1 would produce an error, unless it was a carryover or cascading effect from an earlier error.
OK, it is not linear in a and b but it linear for a given b and b given a.
I get the same error when adding the constraints to that problem. Is there any way to approximate the original problem with a convex formulation with which we can use cvx?
What you are describing is a bilinear function, which is not linear.
I don’t see how you can handle it with CVX, other than
- Some scheme along the lines of fixing b at some initial value, then optimize with respect to b, then fix a at its just found “optimum”, and optimize over b, etc. I have no reason to believe this will work well or at all.
or
- Formulate a Mixed Integer DCP using techniques described in section 7.7 of http://mixedintegerprogramming.weebly.com/uploads/1/4/1/8/14181742/integer_programming_tricks_-_aimms_modeling_guide.pdf if you can. I’ll leave it to you to determine whether this is possible in your case.
