Problem using CVX with gurobi


(Nora) #1

I want to maximize the number of unique elements I get from the array vector S. while choosing only K of these vectors.

so I wrote this:

function [x] = linearSolverCVX(actions, S, K)
n = length(actions);
lowerBound=zeros(n,1);
upperBound=ones(n,1);
cvx_begin
    variable x(n)
    maximize(length(unique(vertcat(S{1,[find(x)]})))) 
    subject to
        lowerBound <= x <= upperBound
        sum(x) == K
cvx_end
disp(x)
end

In my (testing data) I have S containing 14 vectors and in each of these vectors 3 or 4 numbers from 1 to 14.
when I run the code and print x it appears that it selected K indices which means that it did satisfy the second condition and all the value of x are either zero or one which (I think) indicate that the gurobi is working.
However the optimal solution is not correct.


(Mark L. Stone) #2

find(cvx_expression) does not do what you think/want.

variable x(n)
find(x)

produces the column vector (1:n)'
so your objective function is a constant, and CVX is solving a feasibility problem, which of course is not the problem you wish to solve.

help cvx/find

Disciplined convex/geometric programming information for find:
When used in CVX models, find cannot deduce the numeric value of a
CVX variable. So it returns the indices of elements that are
“structurally” nonzero; i.e., that are not identically zero.
This is similar to the concept of structural nonzeros in sparse
matrix factorizations. To illustrate the distinction, consider:
variable x(3);
x(2) == 0;
y = [x(1);0;x(3)];
In this case, find(x) returns [1;2;3] even though x(2) has been set
to zero in an equality constraint. (After all, the overall model may
be infeasible, in which case x(2) is arguably not zero.) However,
find(y) will return [1;3], because y(2) is identically zero.

When X is a CVX variable, the first two outputs of [I,J,V]=find(X) 
are constant, and the third is a CVX variable containing the 
structural nonzeros of X.

find(X) places no convexity restrictions on its argument.

You ought o be able to do what you want using binary variables, making use of CVX’s MIDCP capability with gurobi. I leave the details to you.

In the future, instead of posting images of code, please copy and paste code into your post, and use Pre-fomatted text icon. That will allow forum readers to copy and paste your code into their own MATLAB session.


(Nora) #3

Thank you for your reply!
is there any other function that does find the which indices of x should take values?
I mean… I guess is there a way to try every combination then it.
I am not sure how to approach the problem with out find function (the way I though it worked).


(Mark L. Stone) #4

if you study the binary variables section 2 of https://www.artelys.com/uploads/pdfs/Xpress/mipformref-1.pdf , you should be able to figure out how to formulate your problem. In CVX, you have to do all the logic stuff yourself, whereas some other modeling tools offer higher level logic which might make things easier. If there are a small enough number of choices, you could solve by explicit enumeration (evaluate each combination) in MATLAB without using an optimizer.


(Nora) #5

Thank you for your answers.