In http://groups.google.com/group/knitro/browse_thread/thread/a1785c5c6f64b62e/ we see the following constructs being used in an NLP model:
c6.. y1*(y1-1) =e= 0;
c7.. y2*(y2-1) =e= 0;
c8.. y3*(y3-1) =e= 0;
This is not really a good idea. These constraints essentially say: y1,y2 and y3 can assume the values 0 or 1, i.e. they are binary variables.
If you really want to use binary variables in an NLP, form a proper MINLP model. If this idea of using non-convex constraints to model binary variables was really so hot, then we would no longer need a MIP solver and just use an NLP solver.
It looks a bit that this poster is attempting to run before (s)he can walk. It would be much better if you have some knowledge about NLP modeling before before actually working on “stochastic global optimization”. May be the advisor or teacher should play a more constructive role here.
Notes:
- in general NLP solvers don’t “understand” the functions you give them. They merely sample points, function values and derivatives as they go along. One exception is the global solver Baron: this solver really tries to work with and understand the functional form of the NL functions.
- although in general it is better to model binary decisions as binary variables in an MINLP (or MIP if the rest is linear), there are some attempts to use nonlinear programming techniques to solve integer models:
- W. Murray and K. M. Ng, “An Algorithm for Nonlinear Optimization Problems with Binary Variables,” Computational Optimization and Applications, Vol. 47, No. 2, 2008, pp. 257-288
- Roohollah Aliakbari Shandiz, Nezam Mahdavi-Amiri, “An Exact Penalty Approach for Mixed Integer Nonlinear Programming Problems”, American Journal of Operations Research, 2011, 1, 185-189
If you take a look at the graph that the "y * (1 - y) = 0" give you, you can have a good picture of why this doesn't work out very well:
ReplyDeletehttp://www.wolframalpha.com/input/?i=plot+y1*%28y1-1%29+%3D+0
Quite the opposite. Actually I think the function and the graph look quite well-behaved. The problem is that you need a global solver to make the optimal selection between y=0 and y=1.
ReplyDeleteI think there is a trend, facilitated by the widespread availability of optimization software, to "democratize" optimization. Once upon a time, the sole entry point was courses in optimization theory and algorithms. Now we push the use of optimization into application area courses (such as supply chain management), where the users learn something about modeling but treat the solvers as black boxes. In one sense this is reasonable: I can drive a car fairly effectively without knowing either the chemistry of gasoline or the mechanics of the internal combustion engine. At the same time, it invites the creation of models that adhere to the syntax rules of a modeling language but will cause a solver to choke -- something the modeler cannot know, since they have not been trained on the algorithms used by the solver.
ReplyDeleteAlthough well behaved, the quadratic growth and, more importantly, the GAP between feasible values seems like a daunting task for a solver to deal with, imo.
ReplyDeleteThat's what I mean.
I think the main problem with these constraints (and complementary constraints in general) is that they ensure that constraint qualificaiton (LICQ or MFCQ) fail on all feasible points, i.e. Lagrange multiplier unicity and boundedness is not ensured.
ReplyDeleteThat being said, some authors have had success invoking such constraints in applications.
See for example chapter 11 of Lorenz Biegler's book: Nonlinear Programming: Concepts, Algorithms, and Applications to Chemical Processes.
Typos: "complementary" = "complementarity", "qualificaiton" = "qualification"
Delete