gemseo_box_subdivision.hierarchy#

Hierarchies of subdivisions: refining a box instead of subdividing it finely.

A box of a subdivision is an ordinary design space, so refining it is running the method again inside its bounds. Which box to refine is the whole question, and these are the rules that answer it and the three shapes of search built on them.

Each shape is a loop around the method rather than a change to it, so it is driven by a callable that solves one level and reports the boxes it solved. The caller keeps the construction of its own scenario, and its own accounting of the budget, and signals exhaustion by returning no solved box.

The trade a hierarchy makes is set out in the documentation: writing \(c\) for the sub-problems a budget affords, a flat run puts all \(c\) cuts into one model, while a hierarchy of \(N\) nodes puts \(c/N\) into each of \(N\) models, and the cuts of a parent have no meaning in the subdivision of a child. Reach for one when the flat method has no answer at all, a basin too broad for any affordable density, rather than to improve a run that works.

Module Attributes

`SolveLevel`	The signature of the callable solving one level.
`RANKINGS`	The rules deciding which boxes to refine, by name.
`SHAPES`	The shapes of hierarchy, by name.

Functions

`compute_cut_model`(solved, subdivision)	Return every box of a subdivision and what the cuts estimate there.
`rank_by_cuts`(solved, subdivision)	Rank every box of the subdivision by the cut model of the master.
`rank_by_value`(solved, subdivision)	Rank the boxes by the value of the sub-problem solved inside them.
`rank_mixed`(solved, subdivision)	Alternate the two rules, taking the first box of each in turn.
`read_solved_boxes`(problem[, objective_name])	Return the boxes a master solved, from the database of its problem.
`refine_deep`(solve, lower_bound, upper_bound)	Refine the most promising box again and again, to a fixed depth.
`refine_frontier`(solve, lower_bound, upper_bound)	Search the boxes of every level best first, so that a run can backtrack.
`refine_two_levels`(solve, lower_bound, ...[, ...])	Solve a coarse level, then refine its most promising boxes.

Classes

SolvedBox(one_hot, value, sensitivity)

A box whose sub-problem was solved, and what the master learned from it.

class gemseo_box_subdivision.hierarchy.SolvedBox(one_hot, value, sensitivity)[source]#

Bases: object

A box whose sub-problem was solved, and what the master learned from it.

Parameters:

one_hot (ndarray)
value (float)
sensitivity (ndarray)

one_hot: ndarray#: The one-hot vector selecting the box.

value: float#: The optimum of the sub-problem inside the box.

sensitivity: ndarray#: The post-optimal sensitivity of that optimum to the one-hot vector.

gemseo_box_subdivision.hierarchy.SolveLevel = 'Callable[[ndarray, ndarray, int], tuple[BoxSubdivision, Sequence[SolvedBox]]]'#

The signature of the callable solving one level.

It receives the lower bounds, the upper bounds and the number of subdivisions per variable of the level, and returns the subdivision it built and the boxes it solved. Returning no solved box ends the search, which is how a caller reports that its budget is spent or that the master became infeasible.

gemseo_box_subdivision.hierarchy.read_solved_boxes(problem, objective_name='')[source]#

Return the boxes a master solved, from the database of its problem.

Parameters:

problem – The optimization problem of the master.
objective_name (str) – The name of the objective. If empty, take the name of the objective of the problem.

Returns:

The solved boxes, in the order the master visited them.

Return type:

list[SolvedBox]

gemseo_box_subdivision.hierarchy.compute_cut_model(solved, subdivision)[source]#

Return every box of a subdivision and what the cuts estimate there.

The cuts gathered by a master define a lower estimate of the value of the problem over the whole subdivision,

\[\hat u(\alpha) = \max_i \, u(\alpha^{(i)}) + s^{(i)\top}(\alpha - \alpha^{(i)}),\]

which is defined at the boxes the master never solved as well as at those it did. That is what makes it usable as a score: it proposes boxes that were never visited, where the value can only rank the few dozen that were.

Parameters:

solved (Sequence[SolvedBox]) – The solved boxes.
subdivision (BoxSubdivision) – The subdivision of the level.

Returns:

The one-hot vector of every box, and the value the cuts estimate there.

Return type:

tuple[ndarray, ndarray]

gemseo_box_subdivision.hierarchy.rank_by_value(solved, subdivision)[source]#

Rank the boxes by the value of the sub-problem solved inside them.

Only the boxes whose sub-problem was solved can be ranked, so this compares measurements rather than extrapolations, over at most a few dozen boxes.

Parameters:

solved (Sequence[SolvedBox]) – The solved boxes.
subdivision (BoxSubdivision) – Unused, the values being attached to the boxes.

Returns:

The one-hot vectors, from the most promising.

Return type:

list[ndarray]

gemseo_box_subdivision.hierarchy.rank_by_cuts(solved, subdivision)[source]#

Rank every box of the subdivision by the cut model of the master.

Parameters:

solved (Sequence[SolvedBox]) – The solved boxes.
subdivision (BoxSubdivision) – The subdivision of the level.

Returns:

The one-hot vectors, from the most promising.

Return type:

list[ndarray]

gemseo_box_subdivision.hierarchy.rank_mixed(solved, subdivision)[source]#

Alternate the two rules, taking the first box of each in turn.

The two fail on opposite landscapes: the value is noise where a coarse box holds many basins, and the cut model, being optimistic, extrapolates towards boxes far from anything solved, which is exploration where the value ranking already points at the right region.

Parameters:

solved (Sequence[SolvedBox]) – The solved boxes.
subdivision (BoxSubdivision) – The subdivision of the level.

Returns:

The one-hot vectors, from the most promising.

Return type:

list[ndarray]

gemseo_box_subdivision.hierarchy.RANKINGS: dict[str, Callable[..., list[ndarray]]] = {'cuts': <function rank_by_cuts>, 'mixed': <function rank_mixed>, 'value': <function rank_by_value>}#: The rules deciding which boxes to refine, by name.

gemseo_box_subdivision.hierarchy.refine_deep(solve, lower_bound, upper_bound, variable_name='x', branching=2, depth=4, ranking='value')[source]#

Refine the most promising box again and again, to a fixed depth.

Every level splits each variable in \(m\) and descends into one box, so a level carries \(n m\) coefficients against the boxes it can afford to solve, and the resolution reached is \(m^{\text{depth}}\) per variable without any level ever being large. This is the shape that answers a basin too broad for any affordable density.

It cannot undo a choice: the box refined at one level is the only space the next level sees. Use refine_frontier() when that matters.

Parameters:

solve (Callable) – The callable solving one level, see SolveLevel.
lower_bound (ndarray) – The lower bounds of the design space.
upper_bound (ndarray) – The upper bounds of the design space.
variable_name (str) – The name of the subdivided variable.
branching (int) – The number of subdivisions per variable at every level.
depth (int) – The number of levels.
ranking (str) – The rule deciding which box to refine, a key of RANKINGS.

Returns:

The bounds of every region visited, coarsest first.

Return type:

list[tuple[ndarray, ndarray]]

gemseo_box_subdivision.hierarchy.refine_two_levels(solve, lower_bound, upper_bound, variable_name='x', coarse=2, fine=5, n_refined=1, ranking='value')[source]#

Solve a coarse level, then refine its most promising boxes.

Parameters:

solve (Callable) – The callable solving one level, see SolveLevel.
lower_bound (ndarray) – The lower bounds of the design space.
upper_bound (ndarray) – The upper bounds of the design space.
variable_name (str) – The name of the subdivided variable.
coarse (int) – The number of subdivisions per variable of the coarse level.
fine (int) – The number of subdivisions per variable inside a refined box.
n_refined (int) – The number of boxes refined, the most promising first.
ranking (str) – The rule deciding which boxes to refine, a key of RANKINGS.

Returns:

The bounds of every region visited, the coarse one first.

Return type:

list[tuple[ndarray, ndarray]]

gemseo_box_subdivision.hierarchy.refine_frontier(solve, lower_bound, upper_bound, variable_name='x', branching=2, expansions=10, score='optimistic', max_depth=8, n_children=4)[source]#

Search the boxes of every level best first, so that a run can backtrack.

The descending shapes above never revisit a box they passed over. This one keeps a frontier of open boxes from every level at once, repeatedly taking the most promising, subdividing it, and putting its children back with their own scores, which makes it a spatial branch-and-bound over the subdivision.

A box is scored by one of:

"optimistic": what the cuts of its parent estimate there, as a branch-and-bound would, the lowest bound being the box that may still hold the optimum.
"greedy": the value where the sub-problem was solved, and the estimate otherwise.
"solved": the value, only the solved boxes going on the frontier, so that the frontier compares measurements rather than extrapolations.

Note

Every node restarts a master and discards its parent’s cuts, and this shape creates the most nodes of the three, so it spreads a budget thinnest. It was the worst of the family wherever it was measured.

Parameters:

solve (Callable) – The callable solving one level, see SolveLevel.
lower_bound (ndarray) – The lower bounds of the design space.
upper_bound (ndarray) – The upper bounds of the design space.
variable_name (str) – The name of the subdivided variable.
branching (int) – The number of subdivisions per variable of an expansion.
expansions (int) – The number of boxes expanded.
score (str) – The rule scoring a box.
max_depth (int) – The number of levels below which a box is not subdivided.
n_children (int) – The number of children of an expansion put on the frontier, the most promising first.

Returns:

The bounds of every region expanded, in the order they were expanded.

Return type:

list[tuple[ndarray, ndarray]]

gemseo_box_subdivision.hierarchy.SHAPES: dict[str, Callable[..., list[tuple[ndarray, ndarray]]]] = {'deep': <function refine_deep>, 'frontier': <function refine_frontier>, 'two_levels': <function refine_two_levels>}#: The shapes of hierarchy, by name.