Date: Apr 9, 2013 8:55 AM
Author: Guest
Subject: Fmincon: nonlinear binary problem

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.*(x-1);

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','interior-point','MaxIter', 5000, ...
'MaxFunEvals', maxfunevals, 'Display','iter-detailed', 'Hessian', ...
'lbfgs', 'TolX', 1e-12, 'TolFun', 1e-12, 'TolCon', 1e-12);

[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.839672e-21.
> 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', 1e-12, 'TolFun', 1e-12, 'TolCon', 1e-12
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', 1e-6, 'TolFun', 1e-6, 'TolCon', 1e-6

Optimization completed: The final point is the initial point.
The first-order optimality measure, 1.036627e-11, is less than
options.TolFun = 1.000000e-06, and the maximum constraint
violation, 0.000000e+00, is less than options.TolCon = 1.000000e-06.
Result: same as x0 exitflag=1

I have seen the advice here: http://www.mathworks.com/help/optim/improving-results.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 1e-6 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