Is there an Optimization tool like intlinprog that includes nonlinear constraints?

I have a program that uses the genetic algorithm in matlab to optimize the solution. Historically, I have used intlinprog before running the ga() to make sure a feasible solution exists (the solution is constrained to be binary and has linear constraints. So I would make a call like this:

    solvable = intlinprog(ones(1, nVars),1:nVars,A,b,[],[],zeros(1, nVars),ones(1, nVars));

However, now I need to include nonlinear constraints. Is there a similar solver to intlinprog or a way to include nonlinear constraints to check for a feasible solution?

(To be clear - I am not asking whether or not I can include nonlinear constraints in the genetic algorithm; I am aware that I can.)

Answer 1

[Matt J]

You could do a preliminary run of ga() with a constant, artificial fitness function like f(x)=0. That would be a way of scouting for a feasible solution without incurring the computational costs of your actual fitness function.

[Matt J]

Note, to implement this approach with maximum efficiency, you should employ the UseVectorized option.

[Matt J]

Doug Rank's response moved here

Interesting idea. Wouldn't it need a feasible population to start with though? Otherwise it might meander around the infeasible solution space for X minutes/generations and then claim there is no feasible solution?

[Matt J]

Of course there is that risk. But even if you knew for sure that the problem were feasible, you still run a similar risk that ga will fail to find a global minimum. There is no getting away from risks like that.

You could, of course, help the search by choosing the initial population, or part of it, in some educated way - a choice which, based on your knowledge of the problem heuristics has a good chance of lying near a solution, if one exists.

[Matt J]

Approach #2:

A related approach would be to pre-run ga with a fitness function which is the maximum of your nonlinear constraints,

x=ga( @(x) max(nonlcon(x)) , nvars,A,b,[],[],lb,ub,[],IntCon,options );

Note that any global optimum of this linearly-constrained pre-problem is feasible in your original problem. The chance of failing to find a feasible point is therefore no greater than the chance of ga failing to find a global solution in the case of "simple" constraints.

Note also that you do not necessarily have to let the above optimization run to completion. You can use an OutputFcn to terminate the iterations once the fitness function max(nonlcon(x)) drops below zero. This event occurs once a feasible solution to your original problem has been found.

Finally, note that the pre-problem has only linear constraints. If you wish, you could therefore apply your technique of seeding the initial population with an intlinprog result.

[Matt J]

Approach #3:

If your nonlinear constraints are smooth, a refinement to Approach #2 would be to use fminimax to minimize max(nonlcon(x)), ignoring for a moment the integer constraints.

   x1 = fminimax( @nonlcon,x0,A,b,Aeq,beq,lb,ub)

If and when an x1 satisfying max(nonlcon(x))<=0 is found, you then run ga() on the pre-problem as in Approach #2 to see if an integer feasible solution canbe found,

 x2=ga( @(x) max(nonlcon(x)) , nvars,A,b,[],[],lb,ub,[],IntCon,options );

except that now you would include round(x1) in the initial population. This would basically be a way of creating a more informed initial population for Approach #2.

[Doug Rank]

These are interesting and creative approaches. Unfortunately the nonlinear constraints are not smooth.

The ultimate goal is to save time for a user if the program is called with infeasible constraints instead of spending a few hours hunting for something that doesn't exist. Unfortunately, I cannot risk the check failing if a feasible solution does in fact exist.

Thank you for your interest and dedication to this challenge. I will keep these ideas in mind should I need something similar.

[Matt J]

Unfortunately, I cannot risk the check failing if a feasible solution does in fact exist.

Well, unfortunately, I don't think you'll be able to avoid that risk. There is no general and guaranteed way of finding a point that satisfies an arbitrary set of nonlinear (in)equalities or verifying if one exists. If there were, nonlinear equation solvers like fsolve wouldn't need an initial guess as input and would never be in danger of getting stuck in local minima.

If you describe the particulars of your nonlinear constraints, maybe the forum could suggest custom solutions for that particular family.