The Nonlinear Programming Solver

Frequently, nonlinear optimization problems contain many local minima because the objective or the constraints are nonconvex functions. The quality of different local minima is measured by the objective value achieved at those points. For example, if and are two distinct local minima and , then is said to be of better quality than . The NLP solver provides a mechanism that is able to locate local minima of better quality. This is achieved by starting the local solver multiple times from different initial points. By doing so, the local solver is able to converge to different local minima. The local minimum with the lowest objective value is then reported back to the user.

The multistart feature consists of two phases. In the first phase, the entire feasible region is explored by generating sample points from a uniform distribution. The aim of this phase is to place at least one sample point in the region of attraction of every local minimum. Here the region of attraction of a local minimum is defined as the set of feasible points with the property that when they are used as starting points a local solver converges to that local minimum.

During the second phase, a carefully selected subset of the sample points is chosen and used as starting points to a local solver. Two major criteria are used to select those sample points. The first criterion selects those sample points that are not close enough to a known local minimum. The second criterion selects those sample points that are not close enough to other sample points. The purpose of these two criteria is to increase the probability of finding new and better quality local minima by calling a local solver as few times as possible.

The number of starting points is critical to the time spent by the solver to find a good local minimum. You can specify the exact number of starting points by using the MSNUMSTARTS= option. If this option is not specified, the solver determines the minimum number of starting points that can provide reasonable evidence that a good local minimum will be found.

Many optimization problems contain variables with infinite upper or lower bounds. These variables can cause the sampling procedure to generate points that are not useful for locating different local minima. The efficiency of the sampling procedure can be increased by reducing the range of these variables by using the MSBNDRANGE= option. This option forces the sampling procedure to generate points that are in a smaller interval, thereby increasing the efficiency of the solver to converge to a local optimum.