Nonuniform Pattern Search (NUPS) Algorithm

When you set the Algorithm option for the patternsearch function to "nups", the algorithm performs search and poll steps as described in Searching and Polling with the following modifications.

  • The poll ignores the settings of the options MeshContractionFactor, MeshExpansionFactor, PollMethod, PollOrderAlgorithm, UseCompletePoll, and MeshRotate. The mesh expansion factor depends on the iterations (as described in the sufficient decrease bullet later in this list). The mesh contraction factor is always 1/2.

  • The "nups" algorithm works in a cycle of 16 iterations. In each cycle, the algorithm uses GPS (generalized pattern search) for the first part of the cycle and MADS (mesh adaptive direct search) for the remainder. Each poll method can be used up to 14 iterations in a cycle. The number of iterations used for a poll method in a future cycle depends on the improvement of the objective function per function evaluation in the current cycle.

    • When the problem has no linear constraints or the current point is not at a linear constraint boundary, each poll uses N+1 points. Alternately the N coordinate directions and the point [1,1,1,…,1]; the next poll uses the negative of these directions. MADS uses these same poll points with an orthogonal set of directions chosen uniformly at random. (MADS does not apply when the problem has linear equality constraints.)

    • When the problem has linear constraints and the current point is at a constraint boundary, the poll uses the tangent directions from the linear constraints, plus the appropriate directions from the remaining dimensions in the poll. Here, appropriate directions are those that are feasible from the current point.

  • When the problem has linear constraints, the algorithm uses a line search, if necessary, to ensure that all points in a poll are feasible with respect to the constraints and bounds. In contrast, if a potential poll point is infeasible in the "classic" algorithm, that point is simply eliminated from the poll. So, the "nups" algorithm can use more poll points, potentially resulting in a more effective poll.

  • Sufficient decrease means a poll finds a point with an objective function value that is sufficiently lower than the current value. Let Fc be the objective function value at the current point, and Fn be the objective function value at the next proposed point. The value Fn satisfies the sufficient decrease condition when:

    (Fc – Fn) / max(1,abs(Fc)) ≥ ImprovementTolerance.

    The poll continues until a proposed point satisfies the sufficient decrease condition or until all points are examined. Then the algorithm takes the first applicable action in this list:

    • If the poll finds no point that improves the current value, the poll is deemed unsuccessful and the mesh size decreases by a factor of 1/2.

    • If the poll finds a point that satisfies the sufficient decrease condition, the poll is deemed successful and the mesh size increases by a factor of 2.

    • If, for three successive iterations, the poll finds a point that improves the current value, but not enough to satisfy the sufficient decrease condition, the third poll is deemed successful and the mesh size increases by a factor of 3/2.

    • If the poll finds a point that improves the current value and the current mesh size is larger than a threshold, the poll is deemed successful and the mesh size increases by a factor of 2.

    • Otherwise, the poll is deemed successful but the mesh size does not change.

    The effect of the sufficient decrease condition is to keep the mesh size small when a step leads to a very small improvement in the objective function value. This behavior can help to keep the algorithm from overreacting to small changes in the objective function value, potentially resulting in faster convergence.

  • You cannot use a poll method as a search method.

When you set the Algorithm option to "nups-gps", the algorithm is the same as "nups" except it performs all polling using GPS. When you set the Algorithm option to "nups-mads", the algorithm is the same as "nups" except it performs all polling using OrthoMADS.

patternsearch handles nonlinear constraints in the same way for all algorithms, as described in Nonlinear Constraint Solver Algorithm for Pattern Search.

When UseParallel is true, patternsearch performs a complete poll for all algorithms.

See Also

Topics