"""Norm-generic geometric primitives usable by any worst-point method -- not
tied to one method's specific algorithm.
Everything here operates only on point clouds and halfspace lists handed to
it -- nothing in this module knows anything about where those points or
cuts came from (a real system model, a synthetic test polytope, or
anything else), and nothing here is tied to a particular solver backend
either. A halfspace/cut is always represented as a `(direction, point)`
pair meaning `{x : direction @ (x - point) <= 0}`; this is the one
convention used consistently across the whole package.
The one operation this package needs that genuinely requires a solver --
projecting a point onto conv(points) under a given norm -- deliberately
does NOT live here. It lives in `gurobi_projection.py` and `highs_projection.py`
instead, one module per backend, both implementing the same
`(point, points, norm) -> (c, normal)` contract, so this module can stay
backend-agnostic in fact, not just in name.
"""
from typing import Literal
import numpy as np
VALID_NORMS = ("l1", "l2", "linf")
#: One of the three supported distance metrics.
Norm = Literal["l1", "l2", "linf"]
#: A `(direction, point)` pair meaning `{x : direction @ (x - point) <= 0}`.
Halfspace = tuple[np.ndarray, np.ndarray]
[docs]
def check_norm(norm: str) -> None:
"""Validate an untrusted `norm` value at a package boundary.
Deliberately typed as plain ``str``, not :data:`Norm` -- the whole
point of this function is to check a value that isn't yet known to be
one of the three valid options; every other function in the package
that already expects a valid norm uses :data:`Norm` instead.
"""
if norm not in VALID_NORMS:
raise ValueError(f"norm must be one of {VALID_NORMS}, got {norm!r}")
[docs]
def gaps(outer_vertices: np.ndarray, closest_points: np.ndarray, norm: Norm) -> np.ndarray:
"""Distance from each outer vertex to its closest point on the inner
hull, under the SAME norm used for the projection -- so the argmax
selection and the stopping tolerance measure the thing that was
actually optimized."""
check_norm(norm)
diff = np.asarray(outer_vertices) - np.asarray(closest_points)
if norm == "l1":
return np.abs(diff).sum(axis=1)
if norm == "linf":
return np.abs(diff).max(axis=1)
return np.linalg.norm(diff, axis=1)
#: Default `sep_tol` as a fraction of the convergence `tol` (see `separates`),
#: used whenever a caller passes `sep_tol=None`.
SEP_TOL_FACTOR = 1e-3
[docs]
def separates(point: np.ndarray, target: np.ndarray, sep_tol: float, norm: Norm) -> bool:
"""Whether a closest-point solve for `target` returned a `point`
genuinely away from it (distance under `norm` above `sep_tol`) -- i.e.
`target` was infeasible and the solve's halfspaces (geometric and
objective cut) should be added. At or below `sep_tol` the target was
already (numerically) feasible, i.e. within `sep_tol` of the region,
and the reported normal can be a degenerate dual split, so nothing is
added. `sep_tol` is deliberately
separate from (and far below) the convergence `tol`: a target within
`tol` of the feasible set but outside it still yields valid,
tightening cuts."""
dist = float(gaps(np.asarray(point)[None, :], np.asarray(target)[None, :], norm=norm)[0])
return dist > sep_tol
[docs]
def linearized_objective_cut(
x0: np.ndarray, obj_value: float, duals: np.ndarray, obj_optimal: float, slack: float, atol: float = 1e-9,
) -> Halfspace | None:
"""A supporting halfspace of the true near-optimal region, linearized
from a single solved point's own duals -- valid, not a heuristic: the
minimum-cost-achievable-at-x value function is convex in x (a standard
parametric-LP fact), so its tangent at any solved point x0 is a GLOBAL
underestimator, `obj(x) >= obj_value + duals @ (x - x0)` for every x,
not just near x0. Near-optimality (`obj(x) <= (1 + slack) *
obj_optimal`) therefore forces `duals @ (x - x0) <= K` where `K =
(1 + slack) * obj_optimal - obj_value` (>= 0, since x0 -- the point
the duals came from -- is itself near-optimal).
Returned as this package's usual `(direction, point)` halfspace
convention: `direction = duals`, and `point` is `x0` shifted along a
single axis -- whichever one has `duals`' own largest-magnitude
component, `j = argmax(|duals|)` -- by just enough to make `duals @
(point - x0) == K` exactly: `point = x0 + (K / duals[j]) * e_j`.
Collapses to `x0` itself when `K == 0` (x0 has no slack left), same
as any other cut that passes through its own generating point.
Deliberately NOT the Euclidean projection (`x0 + (K / (duals @
duals)) * duals`) despite that also being a valid choice of point on
the same halfspace (`add_cut`'s own halfspace only depends on the
scalar `direction @ point`, identical for every point actually on the
plane -- so this is still just a choice among equally-correct
options, not a different halfspace). `duals` mixes real-world units
that can differ by orders of magnitude (e.g. $/MW vs $/MWh), so
`duals @ duals` can be dominated by whichever dimension happens to
have large values there, sending the Euclidean-projection point to a
numerically extreme value in every OTHER dimension -- which then
makes `direction @ point` (computed downstream by whichever method
processes this halfspace) suffer catastrophic floating-point
cancellation, corrupting that cut's own vertex classification
(confirmed in practice, against this project's incremental edge-walking
construction before `CddMethod` became the production method: exactly
this construction once produced ~187,000 spurious crossing vertices for
a 4-dimensional polytope, an OOM crash, not just an inefficiency).
Dividing by `duals[j]` itself
(the largest-magnitude component, so the least numerically sensitive
denominator available) and moving along a single axis avoids ever
amplifying small numerical noise into a huge coordinate swing.
Returns `None` when `duals` is (numerically) the zero vector: then
`K >= 0` is the whole constraint, true for every x -- a vacuous cut,
not worth adding.
"""
x0 = np.asarray(x0, dtype=float)
duals = np.asarray(duals, dtype=float)
j = int(np.argmax(np.abs(duals)))
if abs(duals[j]) < atol:
return None
k = max(0.0, (1 + slack) * obj_optimal - obj_value)
point = x0.copy()
point[j] += k / duals[j]
return duals, point