
Fmincon: nonlinear binary problem
Posted:
Apr 9, 2013 8:55 AM


Hello,
This is the first time I use Matlab's Optimization Toolbox. I'm trying to solve a binary problem but it's not linear and I use fmincon. I encounter several problems that I'll try to outline below.
The objective function is in the form myfun=SUM(i)SUM(j)SUM(k) x_ik*x_jk*p_ij
P is a parameter matrix, the variables X are binary and this is enforced through nonlinear equality constraints mycon ceq=x.*(x1);
On top of that lb is set to 0 and ub to 1 for all X.
It's important to note that X is divided into 2 subsets {X_1} and {X_2} and equality constraints concern only {X_1} which results in the columns dedicated to {X_2} being empty.
The objective function needs more parameters and hence the calling looks as follows:
f = @(x)myfun(x,w,c); % to pass more arguments to fmincon
options = optimset('Algorithm','interiorpoint','MaxIter', 5000, ... 'MaxFunEvals', maxfunevals, 'Display','iterdetailed', 'Hessian', ... 'lbfgs', 'TolX', 1e12, 'TolFun', 1e12, 'TolCon', 1e12);
[x,fval, exitflag] = fmincon(f,x0, A, b, Aeq, beq, lb, ub, 'mycon', options);
First of all, I get the warning Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 7.839672e21. > In C:\Program Files\MATLAB\R2012b\toolbox\optim\optim\private\backsolveSys.p>backsolveSys at 18 In C:\Program Files\MATLAB\R2012b\toolbox\optim\optim\private\solveKKTsystem.p>solveLbfgsKKTsystem at 49 In C:\Program Files\MATLAB\R2012b\toolbox\optim\optim\private\solveKKTsystem.p>solveKKTsystem at 18 In C:\Program Files\MATLAB\R2012b\toolbox\optim\optim\private\computeTrialStep.p>computeTrialStep at 67 In C:\Program Files\MATLAB\R2012b\toolbox\optim\optim\barrier.p>barrier at 354 In fmincon at 896
As far as I understand it is at the level of the Hessian matrix, is that correct? How can I prevent it? I changed the way Hessian is calculated and it seems to be less frequent but not eliminated. Due to the size of the objective function (about 2000 elements in the sum), I don't know how to provide the Hessian. In my A and Aeq matrices I removed all 0 rows and due to their size made these matrices sparse. I'm concerned it's caused by the equality constrains concerning only {X_1} since fmincon accepts a vector of all X, the columns of Aeq for set {X_2} are empty. Is there a way to eliminate that?
What is more, it complains that x0 is out of bounds, like below for a small example problem
x0 = 1 0 0 0 1 0 0 0 1 1 1 1
lb = 0 0 0 0 0 0 0 0 0 0 0 0
ub = 1 1 1 1 1 1 1 1 1 1 1 1
Your initial point x0 is not between bounds lb and ub; FMINCON shifted x0 to strictly satisfy the bounds.
For small problems it returns the x0 solution with exitflag 2. If I run it for bigger problems (size od X approximately 2000) the solution is not integral, despite the nonlinear mycon constraint, even though a heuristics finds one.
I changed the bounds by a very small number to 0.001 and 1.001 and it seems to accept it. Nevertheless, the solution I obtain is the one I feed as x0, as below depending on the tolerances
'TolX', 1e12, 'TolFun', 1e12, 'TolCon', 1e12 Result: same as x0 exitflag=2, I am sure that the solution I feed is feasible, as it's a result of a heuristic algorithm. If I feed it with a random feasible solution (worse than heuristics) it still returns what was fed with the same flag (2). I also tried running it with Multistart option to examine more points but the result is the same returned solution is the initial one.
'TolX', 1e6, 'TolFun', 1e6, 'TolCon', 1e6
Optimization completed: The final point is the initial point. The firstorder optimality measure, 1.036627e11, is less than options.TolFun = 1.000000e06, and the maximum constraint violation, 0.000000e+00, is less than options.TolCon = 1.000000e06. Result: same as x0 exitflag=1
I have seen the advice here: http://www.mathworks.com/help/optim/improvingresults.html, verified that the constraints and bounds are correct, tried to run for different points, same effect.
I have a trouble setting the tolerances and other parameters, as sometimes even 1e5 evaluations with TolX 1e6 seem not to be enough for big problems.
I would appreciate any comments and help on how to deal with nonlinear binary problems in Matlab.
Regards, Anna

