Does MCS require an analytic gradient?

No. The user supplies function values, while the method constructs its own search information.

Are its levels separate optimization objectives?

No. They organize the processing of search boxes.

Does global optimization guarantee success within my chosen budget?

Not generally. The finite run can miss a better basin even when an asymptotic convergence result applies.

AI Glossary / Mathematics and optimization / Intermediate

MCS algorithm

Definition

The MCS algorithm, in mathematical optimization, is Multilevel Coordinate Search: a method for minimizing a function subject to coordinate bounds using function evaluations rather than supplied derivatives. It balances exploration of the search region with refinement near promising points. This entry refers to Huyer and Neumaier's optimization method, not other algorithms that share the initials MCS.

What it means

An objective function may have several local minima, so improving a single starting point can leave a search in the wrong basin. MCS divides the feasible region into rectangular boxes and uses a hierarchy of processing levels to balance broad coverage with more focused work.
The levels describe how boxes have been processed; they are not business-management levels or a hierarchy of nested decision makers. The method is intended for global optimization, but stopping after a finite evaluation budget does not generally certify that the best possible point has been found. A reported incumbent is the best point discovered so far.

How it works

Associate each box with a base point whose objective value is known and with a level that helps organize the search. The algorithm sweeps through levels, selecting promising boxes while also revisiting relatively unexplored territory. Splitting takes place along a single coordinate, using information from previous samples and safeguards on the subdivision.
The published implementation can launch local searches from selected candidate points. It builds local quadratic models and solves associated bound-constrained subproblems without requiring the user to provide derivatives. Its convergence theory concerns the specified continuing search under assumptions, including continuity near a global minimizer. That theory should not be interpreted as a finite-run optimality certificate for arbitrary noisy evaluations.

Three practical examples

An engineering analyst can tune a small set of bounded simulator parameters when only the simulator's output value is available.
A numerical study can compare several candidate basins of a nonconvex objective before spending more evaluations on local refinement.
A model-calibration workflow can search within physically meaningful parameter bounds while logging the best observed objective and the evaluation budget.

Think of it this way

Think of searching a landscape with a map divided into boxes. Some effort goes to promising valleys and some to areas that have received little attention. The analogy has limits: MCS uses explicit levels, coordinate splits, and numerical models, and it cannot see an unsampled valley merely because a box appears on the map.

Worked example

Consider an original teaching objective on −1≤x≤1 and −1≤y≤1:
f(x,y)=min{(x−0.8)²+(y−0.7)², 0.1+(x+0.6)²+(y+0.5)²}.
It is the lower of two quadratic bowls and is continuous, although it can be nondifferentiable where the bowls meet. Every term inside the minimum is nonnegative, so f cannot be negative. At (0.8,0.7), the first bowl is zero; consequently the global minimum is zero.
The second bowl has a local minimum at (−0.6,−0.5), where its value is 0.1 and the first bowl's value is 3.4. A search concentrating only near this basin could return 0.1 while missing the global minimizer.
Here are illustrative evaluations, not a claim that a particular MCS implementation produces this exact sequence. At (0,0), the two bowl values are 1.13 and 0.71, so f=0.71. Moving to (−0.6,0) gives f=0.35. Moving next to (−0.6,−0.5) improves the incumbent to 0.1.
An exploratory evaluation at (0.8,0) gives f=0.49. It is worse than the incumbent, but the surrounding region still contains the global minimum: evaluating (0.8,0.7) gives zero. This demonstrates why a global method must not dismiss a region merely because one sampled point is worse than the current best.
In this constructed example, the known algebraic lower bound zero certifies the final point. That certificate comes from the special formula we supplied, not automatically from MCS. In a black-box application, the same observed value would require a separate justified lower bound before it could establish global optimality.

Illustrative case study

In a fictional simulation consultancy, an analyst uses a bounded two-parameter model with several basins. The team records each evaluation and compares local refinement with a broader MCS search under the same budget. Its report distinguishes the best observed simulator setting from a certified optimum. This case illustrates experiment design; it does not report an actual simulator result, execution trace, or measured savings.

Common misconceptions and mistakes

Derivative-free does not mean model-free: MCS still uses information from evaluations to guide subdivision and local approximations. It also does not mean every evaluation error is harmless. Random noise can disrupt comparisons and the assumptions behind deterministic search behavior.
Another mistake is describing MCS as conventional branch and bound with rigorous lower bounds for every box. The original paper describes its approach as subdivision without those bounds. Finally, comparisons made on a few low-dimensional test functions do not establish universal superiority. Dimension, evaluation cost, discontinuities, scaling, and available structure all affect which method is practical.

Business use

For a business optimization problem, first make the objective and coordinate limits meaningful. Decide how failed simulator runs, repeated evaluations, and measurement noise will be handled. Report the budget, stopping rule, best feasible point, and evidence for any optimality claim. A good numerical score should also be checked against operational constraints that may not have been included in a simple box-constrained formulation.

Check your understanding

Why does f(0.8,0)=0.49 not justify discarding the entire nearby region?

Answer: A point in that region, (0.8,0.7), has value zero. A sampled value is not a lower bound on every other point in its box.

Related terms

Global optimization
Derivative-free optimization
Coordinate search
Box constraints
Local minimum
DIRECT algorithm
Quadratic model
Evaluation budget

Learn next

Raise the second bowl's constant from 0.1 to 0.4 and recompute the listed evaluations. Then distinguish what changes in the observed search history from what remains true about the known global minimizer.

Sources

Primary sources: Huyer and Neumaier, Global Optimization by Multilevel Coordinate Search, original paper: https://arnold-neumaier.at/ms/mcs.pdf . Authors' implementation notes and finite-search limitation: https://arnold-neumaier.at/software/mcs/ . The two-bowl example is an original conceptual illustration, not an executed MCS run.

Previous: MCA Next: Mean