This page is intended to provide engineers, scientists, designers and applied mathematicians updated information about Normal-Boundary Intersection (NBI), a proven technique for generating Pareto points in nonlinear multicriteria optimization problems. This technique was developed by Indraneel Das and John E. Dennis, Jr. in July, 1996. This method is described in detail in "Normal-Boundary Intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems" published in SIAM J. Optimization 8(1998), pp 631-657.
Today NBI is more than eight years old, and is the method of choice for generating nonlinear Pareto surfaces in many optimization problems, applied and academic.
NBI has various advantages over existing methods for multicriteria optimization, one of which is illustrated here:
Consider the following bi-objective optimization problem:
| min | f1(x) = || x ||2 | ||
| f2(x) = 3 x1 + 2 x2 - x3/3 + 0.01(x4 - x5)3 | |||
| s.t. | x1 + 2 x2 - x3 - 0.5 x4 + x5 = 2 | ||
| 4 x1 - 2 x2 + 0.8 x3 + 0.6 x4 + 0.5 x52 = 0 | |||
| || x ||2 <= 10 |
Both the techniques required solving 21 nonlinear optimization problems, but the NBI parametrization of the efficient frontier naturally bears the property of even spread (rigorous statements with proofs in the paper). Moreover, this is also extensible for more than two objectives, unlike homotopy techniques which can handle only bi-objective problems.
Other papers by Indraneel Das can be obtained here. In particular you might be interested in extensions of the NBI approach, such as the Recursive Knee Approach.
Software
Good News!
Aimin Zhou, a Ph.D. candidate from the Dept. of Computer Science at the University of Essex has produced a version of Indraneel's old NBI package that runs on the latest Matlab 7. He has tested it under Windows. Please email him at azhou@essex.ac.uk if you want this package. Aimin is also doing some interesting work in extending the method to compute points that the original NBI could not, so watch out for this piece of work.
The old Matlab 4.2 implementation of NBI is also available and you can download [706KB] the .tar file containing all the .m Matlab files along with some example files. Once you download the file, you can install the directory using the Unix level command tar -xvf NBI.tar NBI_Matlab4.2version.
Any of these NBI packages is free and comes as-is with no warranty of any sort whatsoever. They use a slightly modified version of Matlab's NLP solver constr.m (comes with the package), which runs only if you own Matlab's optimization toolbox. And if you do happen to download the package, please send me e-mail and let me know.
Matlab 5.0 version
It has been observed that the above NBI package has problems running on Matlab version 5.0, because, some old syntaxes (e.g. if (x ~= []) , or xout(:) = x, which appeared in the old constr.m out of which constr_mo.m was created) are not supported in Matlab 5.0. So here is a .tar file containing the version modified to run on Matlab 5.0 (download) . This version has only been tested on an AIX platform, please let me know if you find it running anywhere else. Note that this version still gives you some warnings when run in Matlab 5.0, which I didn't have time to fix. They should not affect the way the program runs; however the `as-is' caveat still applies!
This page is occasionally updated by Indraneel Das (nrneds@yahoo.com).