```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 myconceq=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 fminconoptions = 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 warningWarning: 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 896As 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 problemx0 =     1     0     0     0     1     0     0     0     1     1     1     1lb =     0     0     0     0     0     0     0     0     0     0     0     0ub =     1     1     1     1     1     1     1     1     1     1     1     1Your initial point x0 is not between bounds lb and ub; FMINCONshifted 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-12Result: 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-6Optimization completed: The final point is the initial point.The first-order optimality measure, 1.036627e-11, is less thanoptions.TolFun = 1.000000e-06, and the maximum constraintviolation, 0.000000e+00, is less than options.TolCon = 1.000000e-06.Result: same as x0 exitflag=1I 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
```