recursively structuring a multivariate numerical optimization

Question

Suppose that I want to partition the unit interval [0..1] into four subintervals whose max length is as short as possible. I can ask Mathematica to:

NMinimize[Max[Abs[q1-0], Abs[q2-q1], Abs[q3-q2], Abs[1-q3]], {q1, q2, q3}]

and I get back the right answer:

{0.25, {q1 -> 0.25, q2 -> 0.5, q3 -> 0.75}}

Note that, once we settle on a tentative value for q2, finding the best q1 and finding the best q3 become independent problems. And pointing out such an independence to Mathematica might help a lot in a more complicated optimization, breaking it up into a tree of lower-dimensional optimizations.

Searching for the best q1 as a subsidiary optimization, given a value for q2, works fine; if I define

leftSplit[q2_] := NMinimize[Max[Abs[q1-0], Abs[q2-q1]], {q1}]

then, for example, leftSplit[0.6] returns {0.3, {q1 -> 0.3}}. I similarly define

rightSplit[q2_] := NMinimize[Max[Abs[q3-q2], Abs[1-q3]], {q3}]

I then ask Mathematica to search for the best q2 as follows:

NMinimize[Max[leftSplit[q2][[1]], rightSplit[q2][[1]]], {q2}]

But I get back error messages of the form:

NMinimize::nnum: The function value Max[0.829053,Abs[0.829053 +q2]] is
not a number at {q1} = {-0.829053}. >>

So it seems that Mathematica is trying to optimize the choice of q1 before a tentative value for q2 has been chosen. What can I do to make the optimizations happen in the order that I intend? Should I be specifying a nonstandard evaluation order?

Answer 1

ClearAll[leftSplit, rightSplit]
leftSplit[q2_?NumericQ] := NMinimize[Max[Abs[q1 - 0], Abs[q2 - q1]], {q1}]
rightSplit[q2_?NumericQ] := NMinimize[Max[Abs[q3 - q2], Abs[1 - q3]], {q3}]

NMinimize[Max[leftSplit[q2][[1]], rightSplit[1 - q2][[1]]], {q2}]
(* or NMinimize[Max[leftSplit[1 - q2][[1]], rightSplit[q2][[1]]], {q2}] *)

{0.5, {q2 -> 0.5}}