chosing a solver for my optimization problem

[Maryam Bodaghi]

Hi every;

I have a problem and trying to solve it in yilmap, but I don't know which solver is appropriate?

clc

clear all

close all

%% DATA

n=3;    % number of consumers

K=2;    % number of UCs

Beta=[1 1 1 1 1]';

Alpha=[1 1 1 1 1]';

C_n=[5 10 15 20 25];  %Budget of consumers

P_k=[10 15 20]';   %Available power of UCs

sigma=40;

aa=0.1;

y=[3 4];

B_min=1;

B_max=4;

B_in=1;

R_min=1;

R_max=2;

D_max=3;

x=sdpvar(3,2)

d=sdpvar(3,3)

a=sdpvar(1,3)

b=sdpvar(1,3)

Constraints = [ x(1,1)*y(1)+x(1,2)*y(2)+aa*b(1)+a(3)*d(1,3)+a(2)*d(1,2)<=C_n(1)...

    , x(2,1)*y(1)+x(2,2)*y(2)+aa*b(2)+a(3)*d(2,3)+a(1)*d(2,1)<=C_n(2)...

    , x(3,1)*y(1)+x(3,2)*y(2)+aa*b(3)+a(2)*d(3,2)+a(1)*d(3,1)<=C_n(3)...

    , B_min<=B_in+b(1)+b(2)+b(3)-d(1,3)-d(1,2)-d(2,1)-d(2,3)-d(3,1)-d(3,2)-d(1,1)-d(2,2)-d(3,3)<=B_max...

    , 0<=d(1,3)+d(1,2)+d(2,1)+d(2,3)+d(3,1)+d(3,2)+d(1,1)+d(2,2)+d(3,3)<=D_max...

    , R_min<=b(1)+b(2)+b(3)<=R_max...

    , x(1,1)+x(1,2)>=b(1)...

    , x(2,1)+x(2,2)>=b(2)...

    , x(3,1)+x(3,2)>=b(3)]

p=(log(1+x(1,1))+log(1+x(1,1))+log(1+x(1,2))+log(1+x(2,1))+log(1+x(2,2))+log(1+x(3,1))+...

    log(1+x(3,2))+log(1+d(1,1))+log(1+d(1,2))+log(1+d(1,3))+log(1+d(2,1))+log(1+d(2,2))+...

    log(1+d(2,3))+log(1+d(3,1))+log(1+d(3,2))+log(1+d(3,3))+log(1+b(1))+log(1+b(2))+...

    log(1+b(3)));

F = [Constraints, x>=0, b>=0, d>=0, a>=0];

solvesdp(F,-p)

[Johan Löfberg]

My first question would be: Do you really want d to be a symmetric matrix which you constrain to be positive semidefinite

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.Basics

[Johan Löfberg]

BTW, I hope you know you don't have to scalarize everything. Standard MATLAB applies to YALMIP variables. Looks like you are typing out some very simple matrix operations.

For instance , the last constraints in the first block are simply

    , R_min<=sum(b)<=R_max...
    , sum(x,2) >= b']

etc

[Maryam Bodaghi]

that's right dear Johan.

as you can see this is my fist try and I wrote in this way too be able decide about parameters.

but now, this is not majority, I don't know about solver.

[Johan Löfberg]

Do you mean d was meant to be a fully parameterized matrix and thus simply constrained to have non-negative elements. With that change, it is a standard nonconvex nonlinear program, which you can solve (locally) using e.g. fmincon or ipopt. For a globally optimal solution, you might try the built-in solver bmibnb (seems to work fairly good, gap below 1% in  a couple of seconds. You have to add upper bounds on all variables though for it to work as no bounds can be deived otherwise, i.e., your search space is unbounded)

BTW, I suspect you objective is wrong. You add log(1+x(1,1)) twice. Write as matrix operation instead, much more compact and lower probability of copy-paste error


(and using solvemoment makes no sense)

[Maryam Bodaghi]

thank you so much.

I fixed it:

x=sdpvar(3,2,'full')

d=sdpvar(3,3,'full')

a=sdpvar(1,3,'full')

b=sdpvar(1,3,'full').

and thanks for your help.

after solving the problem, could I see assigned variables, I mean quantity of "a,b,x,d" ??

[Johan Löfberg]

Obtaining computed values is explained in the tutorial I linked.

This is the model I think you want to solve, here solved using globally using bmibnb thus added upper bounds

Constraints = [ x*y' + aa*b' + d*[0 1 1;1 0 1;1 1 0]*a' <= C_n(1:3)',
B_min<=B_in+sum(b)-sum(sum(d))<=B_max,
0<=sum(sum(d))<=D_max,
R_min<=sum(b)<=R_max,
sum(x,2) >= b']
p=sum(sum(log(1+x)))+sum(sum(log(1+d)))+sum(sum(log(1+b)))
F = [Constraints, 100>=x>=0, 100>=b>=0, 100>=d>=0, 100>=a>=0];
solvesdp(F,p,sdpsettings('solver','bmibnb'))

[Johan Löfberg]

'full' is redundant on matrices where the number of rows and columns differ (it can never be symmetric)

[Maryam Bodaghi]

Thanks indeed for your time and kindly help.

[Maryam Bodaghi]

Dear Mr. Johan;

Thank you for your helps and time. I have some other questions. would you please help me?

As in this way gap is more than 1%, the answer is correct? Can I change "maximum iteration" or "time"?

 Also in "solvebilevel", just two sets of objective and variable could be solved? I mean I have a game with two sides, one of them has 3 player and the other 5,can I use "solvebilevel" in this problem?

[Johan Löfberg]

The gap between found solution, and the lowest possible if a better exist is at most 1% (where gap is defined as (upper-lower)/(1+abs(upper))

Options in bmibnb are altered through sdpsettings as with any other solver
http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Commands.sdpsettings

solvebilevel (try to) solves problems with inner convex QPs, and the number of variables in outer vs inner problems are arbitrary (except that it gets harder of course). Many times it is better to formulate the problem manually using the KKT operator and use a fast MIQP solver, as explained in the Wiki

[Maryam Bodaghi]

thanks so much.

when I change the solver, and  this error occurs:

Warning: Solver not applicable (sparsepop)

Is that mean this solver is not appropriate, or its not found or etc? 

Also, # of my variables in real problem is about 450. which solver do you offer whit this objective (I mean logarithmic)?

[Johan Löfberg]

sparsepop makes no sense here. sparsepop is for sparse polynomial programming.

You have a general nonlinear program, hence you use fmincon, ipopt, snopt or knitro, or any of those in combination with the internal global solver bmibnb, or the other global solvers scip and baron

[Maryam Bodaghi]

Dear Mr. Johan;

thanks indeed for your kindly help.

[Maryam Bodaghi]

Excuse me for taking your time.

I've read a paper on solving non-convex bilevel programming and it suggested below approach. What do you think about it?

[Johan Löfberg]

Don't have too high hopes...Nonconvex programming simply extremely hard. Don't expect anything to work.

[Maryam Bodaghi]

So, why did you advise some solutions to solve my non-convex problem before? Is my answer wrong for it? and it does not make sense for being used as follower problem in a stackelberg game?  

[Johan Löfberg]

Those solvers are applicable and can "solve" nonconvex programs. With "solve" I mean they accept the problem form and try to compute something reasonable, hopefully a locally optimal point, but one can never assume that it will work without problems. Nonconvex nonlinear programs are hard.