Source code for mga_surveyor.methods.base
"""The :class:`Method` interface shared by all three worst-point
implementations (bilevel MILP, cdd, beneath-and-beyond), so a driving loop (see
:mod:`mga_surveyor.explore`) can be written once against this interface and
parameterized by which method to use.
Every method owns exactly the state needed to maintain an inner
approximation ``I`` (a set of points, implicitly their convex hull) and an
outer approximation ``O`` (a growing list of supporting halfspaces) of some
region -- and nothing else. In particular, no method ever calls back into
whatever produced a point or a cut: :meth:`Method.add_point` /
:meth:`Method.add_cut` are pure state updates, so the whole package is
independent of any specific test example or system model. Finding new
points/cuts to feed in is the caller's job (see the generic loop in
:mod:`mga_surveyor.explore`, or drive a method directly with your own).
"""
from abc import ABC, abstractmethod
import numpy as np
from ..common import Halfspace, Norm
[docs]
class Method(ABC):
"""Common interface for a worst-point / convergence-metric implementation.
:param k: Dimension of the exploratory variables.
:type k: int
:param norm: Distance metric used by the inner-hull projection that
drives both the convergence metric and the direction of the next
cut. One of ``'l1'``, ``'l2'``, or ``'linf'``.
:type norm: str
"""
def __init__(self, k: int, norm: Norm) -> None:
self.k = k
self.norm = norm
[docs]
@abstractmethod
def bootstrap(self, initial_points: list[np.ndarray], initial_halfspaces: list[Halfspace]) -> None:
"""Seed the inner and outer approximations.
Must be called exactly once, before any :meth:`add_point`,
:meth:`add_cut`, or :meth:`find_trial_point` call.
:param initial_points: Feasible points (e.g. the cost-optimal
design) to seed the inner approximation with.
:param initial_halfspaces: ``(direction, point)`` pairs, each
defining a supporting hyperplane known to hold for the true
region (e.g. from element-wise upper/lower bounds), to seed the
outer approximation with.
"""
[docs]
@abstractmethod
def add_point(self, point: np.ndarray) -> bool:
"""Grow the inner approximation with a newly found feasible point.
:param point: The feasible point to add.
:returns: True if the inner approximation actually changed, False
if ``point`` duplicates an existing inner vertex within
tolerance.
:rtype: bool
"""
[docs]
@abstractmethod
def add_cut(self, direction: np.ndarray, point: np.ndarray):
"""Shrink the outer approximation by adding a new supporting
halfspace ``{x : direction @ (x - point) <= 0}``.
:param direction: Normal vector of the new supporting hyperplane.
:param point: A point on the new supporting hyperplane.
"""
[docs]
@abstractmethod
def find_trial_point(self) -> tuple[np.ndarray | None, float]:
"""Find the point in the outer approximation furthest (in
``self.norm``) from the inner approximation.
:returns: ``(trial_point, gap)``, where ``gap`` is the max-min
distance itself (the convergence metric). ``(None, 0.0)`` if
the outer approximation has no vertices (only possible before
:meth:`bootstrap`).
:rtype: tuple
"""
[docs]
@abstractmethod
def max_gap(self) -> float:
"""The current convergence metric: the largest distance from any
tracked outer-approximation vertex to the inner approximation. An
upper bound on the distance from either approximation to the true
region.
:rtype: float
"""