Optimize over multiple variables with linear objective and convex constraints gives quad_form error

Nonconvex
1

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?

2

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.

3

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?

4

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

  1. 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

  1. 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.
1 Like