Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Fmincon: nonlinear binary problem

Subject: Fmincon: nonlinear binary problem

From: Anna

Date: 9 Apr, 2013 12:55:06

Message: 1 of 11

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

Subject: Fmincon: nonlinear binary problem

From: Bruno Luong

Date: 9 Apr, 2013 13:26:07

Message: 2 of 11

"Anna" wrote in message <kk133a$9i6$1@newscl01ah.mathworks.com>...
> 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.

Never ever use fmincon for binary problem.

Bruno

Subject: Fmincon: nonlinear binary problem

From: Alan_Weiss

Date: 9 Apr, 2013 14:30:04

Message: 3 of 11

On 4/9/2013 9:26 AM, Bruno Luong wrote:
> "Anna" wrote in message <kk133a$9i6$1@newscl01ah.mathworks.com>...
>> 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.
>
> Never ever use fmincon for binary problem.
>
> Bruno

To expand on Bruno's answer, there is no Optimization Toolbox solver
capable of handling binary problems.
http://www.mathworks.com/help/optim/ug/choosing-a-solver.html#brhkghv-19

Your only choice among MATLAB solvers is ga from Global Optimization
Toolbox:
http://www.mathworks.com/help/gads/mixed-integer-optimization.html

Good luck,

Alan Weiss
MATLAB mathematical toolbox documentation

Subject: Fmincon: nonlinear binary problem

From: Anna

Date: 10 Apr, 2013 10:23:12

Message: 4 of 11

Thank you Bruno and Alan for the hints. I will also also thinking to linearize my objective so that I can use bintprog. I'd do it by introducing additional binary variable z_ij in such a way that:

myfun=SUM(i)SUM(j)z_ij*p_ij

with an additional constraint:
x_ik+x_jk=<z_ij+1

Would bintprog keep z_ij as 0 and enforce to 1 only if absolutely necessary?

Regards,
Anna

Alan_Weiss <aweiss@mathworks.com> wrote in message <kk18lc$smq$1@newscl01ah.mathworks.com>...
> On 4/9/2013 9:26 AM, Bruno Luong wrote:
> > "Anna" wrote in message <kk133a$9i6$1@newscl01ah.mathworks.com>...
> >> 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.
> >
> > Never ever use fmincon for binary problem.
> >
> > Bruno
>
> To expand on Bruno's answer, there is no Optimization Toolbox solver
> capable of handling binary problems.
> http://www.mathworks.com/help/optim/ug/choosing-a-solver.html#brhkghv-19
>
> Your only choice among MATLAB solvers is ga from Global Optimization
> Toolbox:
> http://www.mathworks.com/help/gads/mixed-integer-optimization.html
>
> Good luck,
>
> Alan Weiss
> MATLAB mathematical toolbox documentation

Subject: Fmincon: nonlinear binary problem

From: Johan Lofberg

Date: 11 Apr, 2013 06:25:09

Message: 5 of 11

You're almost there Anna, you just need two more constraints

This ensures z_ij is 1 if both x_ik and x_jk are 1
 x_ik+x_jk=<z_ij+1

Now you add the following to ensure z is zero if any x is zero
z_ij <= x_ik
z_ij <= x_jk

The linear model is now equivalent to the quadratic model

/johan

"Anna" wrote in message <kk3eig$mcn$1@newscl01ah.mathworks.com>...
> Thank you Bruno and Alan for the hints. I will also also thinking to linearize my objective so that I can use bintprog. I'd do it by introducing additional binary variable z_ij in such a way that:
>
> myfun=SUM(i)SUM(j)z_ij*p_ij
>
> with an additional constraint:
> x_ik+x_jk=<z_ij+1
>
> Would bintprog keep z_ij as 0 and enforce to 1 only if absolutely necessary?
>
> Regards,
> Anna
>
> Alan_Weiss <aweiss@mathworks.com> wrote in message <kk18lc$smq$1@newscl01ah.mathworks.com>...
> > On 4/9/2013 9:26 AM, Bruno Luong wrote:
> > > "Anna" wrote in message <kk133a$9i6$1@newscl01ah.mathworks.com>...
> > >> 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.
> > >
> > > Never ever use fmincon for binary problem.
> > >
> > > Bruno
> >
> > To expand on Bruno's answer, there is no Optimization Toolbox solver
> > capable of handling binary problems.
> > http://www.mathworks.com/help/optim/ug/choosing-a-solver.html#brhkghv-19
> >
> > Your only choice among MATLAB solvers is ga from Global Optimization
> > Toolbox:
> > http://www.mathworks.com/help/gads/mixed-integer-optimization.html
> >
> > Good luck,
> >
> > Alan Weiss
> > MATLAB mathematical toolbox documentation

Subject: Fmincon: nonlinear binary problem

From: Anna

Date: 11 Apr, 2013 08:42:05

Message: 6 of 11

Thank you very much, Johan!

Anna

Subject: Fmincon: nonlinear binary problem

From: Torsten

Date: 11 Apr, 2013 09:44:08

Message: 7 of 11

"Anna" wrote in message <kk5t0t$c4i$1@newscl01ah.mathworks.com>...
> Thank you very much, Johan!
>
> Anna

Because you substitute x_ik*x_jk = min(x_ik,x_jk) , I think you will need z_ijk:
z_ijk <= x_ik
z_ijk <= x_jk
z_ijk >= x_ik + x_jk - 1

Best wishes
Torsten.

Subject: Fmincon: nonlinear binary problem

From: Anna

Date: 11 Apr, 2013 10:55:07

Message: 8 of 11

I was just thinking that all these 3 constraints can be written as one

x_ik+x_jk>=2*z_ijk, right?

"Torsten" wrote in message <kk60l8$l9i$1@newscl01ah.mathworks.com>...
> Because you substitute x_ik*x_jk = min(x_ik,x_jk) , I think you will need z_ijk:
> z_ijk <= x_ik
> z_ijk <= x_jk
> z_ijk >= x_ik + x_jk - 1

Good point Torsten. Theoretically, I would need to index z over k but from other constraints I also know that there may be at most one k for which z_ijk=1 and I don't need to know the detailed information which k it is, but only the indication whether it happens at all. Would indexing z_ij be correct in that case? It's important to me to limit the size of the variables as well.

Regards,
Anna

Subject: Fmincon: nonlinear binary problem

From: Torsten

Date: 12 Apr, 2013 06:58:07

Message: 9 of 11

"Anna" wrote in message <kk64qb$2ig$1@newscl01ah.mathworks.com>...
> I was just thinking that all these 3 constraints can be written as one
>
> x_ik+x_jk>=2*z_ijk, right?
>

This condition does not exclude the case that z_ijk=0 although both x_ik and x_jk are equal to 1. So z_ijk is not equal to x_ik*x_jk. It depends on your objective function if z_ijk will automatically be chosen to be 1 if x_ik=1 and x_jk = 1.

> "Torsten" wrote in message <kk60l8$l9i$1@newscl01ah.mathworks.com>...
> > Because you substitute x_ik*x_jk = min(x_ik,x_jk) , I think you will need z_ijk:
> > z_ijk <= x_ik
> > z_ijk <= x_jk
> > z_ijk >= x_ik + x_jk - 1
>
> Good point Torsten. Theoretically, I would need to index z over k but from other constraints I also know that there may be at most one k for which z_ijk=1 and I don't need to know the detailed information which k it is, but only the indication whether it happens at all. Would indexing z_ij be correct in that case? It's important to me to limit the size of the variables as well.

I don't think that this is possible. Imagine there are indices k1 and k2 such that, for fixed i and j, x_ik1*x_jk1 = 1 and x_ik2*x_jk2 = 0. Then, if you only introduce z_ij, your problem becomes infeasible.
To save some variables, note that x_ik*x_jk = x_jk*x_ik. Thus z_ijk = z_jik.

>
> Regards,
> Anna

Best wishes
Torsten.

Subject: Fmincon: nonlinear binary problem

From: Anna

Date: 12 Apr, 2013 10:16:06

Message: 10 of 11

> > I was just thinking that all these 3 constraints can be written as one
> >
> > x_ik+x_jk>=2*z_ijk, right?
> >
>
> This condition does not exclude the case that z_ijk=0 although both x_ik and x_jk are equal to 1. So z_ijk is not equal to x_ik*x_jk. It depends on your objective function if z_ijk will automatically be chosen to be 1 if x_ik=1 and x_jk = 1.

True!

>
> > "Torsten" wrote in message <kk60l8$l9i$1@newscl01ah.mathworks.com>...
> > > Because you substitute x_ik*x_jk = min(x_ik,x_jk) , I think you will need z_ijk:
> > > z_ijk <= x_ik
> > > z_ijk <= x_jk
> > > z_ijk >= x_ik + x_jk - 1
> >
> > Good point Torsten. Theoretically, I would need to index z over k but from other constraints I also know that there may be at most one k for which z_ijk=1 and I don't need to know the detailed information which k it is, but only the indication whether it happens at all. Would indexing z_ij be correct in that case? It's important to me to limit the size of the variables as well.
>
> I don't think that this is possible. Imagine there are indices k1 and k2 such that, for fixed i and j, x_ik1*x_jk1 = 1 and x_ik2*x_jk2 = 0. Then, if you only introduce z_ij, your problem becomes infeasible.

The original nonlinear objective was
obj=sum(i) sum (j) sum(k) x_ik*x_jk*p_ij

Maybe my explanation was not clear, I intend to replace sum(k) x_ik*x_jk=z_ij for every i and j. Would that be fine? It seems to me that all the previously proposed constraints should hold. Thank you for all your comments.

Regards,
Anna

Subject: Fmincon: nonlinear binary problem

From: Torsten

Date: 12 Apr, 2013 11:07:06

Message: 11 of 11

"Anna" wrote in message <kk8mt6$svi$1@newscl01ah.mathworks.com>...
> > > I was just thinking that all these 3 constraints can be written as one
> > >
> > > x_ik+x_jk>=2*z_ijk, right?
> > >
> >
> > This condition does not exclude the case that z_ijk=0 although both x_ik and x_jk are equal to 1. So z_ijk is not equal to x_ik*x_jk. It depends on your objective function if z_ijk will automatically be chosen to be 1 if x_ik=1 and x_jk = 1.
>
> True!
>
> >
> > > "Torsten" wrote in message <kk60l8$l9i$1@newscl01ah.mathworks.com>...
> > > > Because you substitute x_ik*x_jk = min(x_ik,x_jk) , I think you will need z_ijk:
> > > > z_ijk <= x_ik
> > > > z_ijk <= x_jk
> > > > z_ijk >= x_ik + x_jk - 1
> > >
> > > Good point Torsten. Theoretically, I would need to index z over k but from other constraints I also know that there may be at most one k for which z_ijk=1 and I don't need to know the detailed information which k it is, but only the indication whether it happens at all. Would indexing z_ij be correct in that case? It's important to me to limit the size of the variables as well.
> >
> > I don't think that this is possible. Imagine there are indices k1 and k2 such that, for fixed i and j, x_ik1*x_jk1 = 1 and x_ik2*x_jk2 = 0. Then, if you only introduce z_ij, your problem becomes infeasible.
>
> The original nonlinear objective was
> obj=sum(i) sum (j) sum(k) x_ik*x_jk*p_ij
>
> Maybe my explanation was not clear, I intend to replace sum(k) x_ik*x_jk=z_ij for every i and j. Would that be fine? It seems to me that all the previously proposed constraints should hold. Thank you for all your comments.
>
> Regards,
> Anna

Assume there exists a k1 with x_ik1*x_jk1 = 1 and x_ik*x_jk = 0 for all k not equal to k1.
Then z_ij should be equal to 1 according to your definition.
But then at least one of the inequalities
z_ij <= x_ik
z_ij <= x_jk
for k not equal to k1 is then violated - constraints you intended to impose on the z_ij.
Or do I miss something ?

Best wishes
Torsten.

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us