Solving using Bmibnb and gurobi

[M.T]

Given a matrix P of 1000x2,  I have set the objective, constraints, variables and options as follows 

x = sdpvar(d,1);

c = sdpvar(1,d);
Constraints = [norm(P*x,1) <= 1, -1 <= c <= 1];
Objective = -c*x;
options = sdpsettings('solver','bmibnb');
sol = optimize(Constraints,Objective,options)

After running this code, i have received the following output:

* Starting YALMIP global branch & bound.

* Branch-variables : 4

* Upper solver     : QUADPROG

* Lower solver     : GUROBI

* LP solver        : GUROBI

 Node       Upper      Gap(%)       Lower    Open

quadprog: The problem is non-convex.

    1 :    0.000E+00     0.65     -6.544E-03   2    

* Finished.  Cost: 0 Gap: 0.65229

* Termination with relative gap satisfied 

* Timing: 1% spent in upper solver (1 problems solved)

*         1% spent in lower solver (9 problems solved)

*         98% spent in LP-based domain reduction (4012 problems solved)

The result i have got is the origin point, which is not the solution, as well as c being an origin point. How can i solve such point?

Please advise and thanks in advance. 

[M.T]

* such problem?

[Johan Löfberg]

You should absolutely not use bmibnb. You should (must) use a good MILP solver, such as gurobi/mosek/cplex

(weird though that it picks up a local minimu, will have to look into that)

[M.T]

When running gurobi as the solver, it states that 

Solver not applicable (gurobi)

Also, i am trying to find a point in norm(P*x,1) <=1 and c such it's ||c||_inf <= 1 such that the dot product c*x is maximized.  

[M.T]

I forgot to mention, when setting P to be 100x2, everything works well. Does it relate to the number of rows in P, meaning that norm(P*x,1)<=1 contains x's that their norm is pretty small, mostly as i have seen for the examples, is at max 3e-4. Maybe this is the reason?

[Johan Löfberg]

100 vs 1000 makes no difference

Is P complex or something, so that the 1-norm actually hides 2-norm. Supply a fully reproducible example

and now when I look at your code in the first post, why are you using a nonconvex solver? You are optimizing a linear objective over a polytope, nothing complicating at all in that code, it's an LP (I confused this with some post where norm was maximized or something)

[M.T]

Dear Professor Johan Löfberg,

The problem is when running gurobi or mosek, it immediately states that "Solver not applicable".
With regarding to maximizing the l1 norm, then yes, this is actually my attempt to linearlize that problem into making it an LP!
P is a real matrix, not complex. I have chosen P by doing 

P = rand(1000,2)

Is there a problem with what i am doing? How can it be solved if I may ask?

Thanks in advance.

[Mark L. Stone]

Objective is bilinear, as c and x are both sdpvar.

[M.T]

I am not that of an expert in this subject. Does this mean that it's solvable?

[Johan Löfberg]

That means it is non-convex and not immediately MILP (or MIQP) and requires a global solver bmibnb. 

1. The fact that you get ero is very strange (extremely poor numerics in P?), and you should supply the example you are solving so it can be tested. When I solve a random problem, it is solved correctly

2. As far as I can see, the optimal solution will always be c = sign(x), and thus you are maximizing norm(x,1), and should write the objective as such, as that is MILP representable bu YALMIP

[M.T]

P is attached. If the problem is MILP or MIQP or MICP (mixed integer convex programming), then it can be solved fast? 

[M.T]

i.e. in polynomial time in the dimensions of P and the variables?

[Johan Löfberg]

No, generically the I in MILP/MIQP/MISOCP etc mean exponential complexity (completely uninteresting if  you always have n=2 of course)

Solving it with the c'*x formulation instead of simply using -norm(x,1) is going to be horribly inefficient (not only exponential in the dimension of x, but you get more as branching is done in x and c, and then it will also do a lot of bound propagation and extra stuff in the 1000 variables modelling the norm(P*x,1) operator, and a general global solver is orders of magnitudes worse in terms of implementation compared to a state-of-the-art MILP solver

You matrix P leads to a solution x which is so close to zero, that the global solver simply stops as zero is close enough to global optimality for its tolerances. A MILP solver (gurobi) solves the norm(x,1) version in fractions of a second