API REFERENCE/omnibias-convex

omnibias.convex.certify

0.1.0a2AlphaPython >=3.10AGPL / commercial

Differentiable LP and QP solver paths, barrier methods, KKT sensitivities, and scoped optimality evidence.

import omnibias.convex.certify

Module contract & mathematical conventions

Verified (certified) a-posteriori optimality enclosure for convex QPs.

Given a *computed* primal x and dual lambda >= 0 for the strictly convex QP

\min_x \tfrac12 x^\top Q x + c^\top x \quad\text{s.t.}\quad A x \le b,
\qquad Q \succ 0,

this returns a **rigorous interval enclosure of the optimal value** f* using interval arithmetic from omnibias.core.verified -- independent of the (floating-point) solver that produced x and lambda.

• **Upper bound.** If x is (rigorously) primal feasible, f* <= f0(x); f0(x) is evaluated in outward-rounded interval arithmetic.
• **Lower bound.** Weak duality: for any lambda >= 0, f* >= g(lambda) = -1/2 v^T Q^{-1} v - b^T lambda with v = c + A^T lambda. A rigorous upper bound on v^T Q^{-1} v <= ||Q^{-1}||_inf ||v||_1 ||v||_inf uses the Neumann certificate ~omnibias.core.verified.neumann_inverse_norm_bound for ||Q^{-1}||_inf.

The width of the returned interval is a rigorous bound on the suboptimality gap; it shrinks to zero as (x, lambda) approach the true optimum (v -> 0 and the primal/dual objectives meet). This is the certificate that distinguishes the omnibias solver from a plain float solve.

For a **linear** program (Q = 0, optionally with equalities A_eq x = b_eq) the Neumann Q^{-1} machinery does not apply; lp_dual_lower_bound / certify_lp_optimum instead use the **Neumaier-Shcherbina** verified LP bound: given *any* multipliers lambda >= 0, nu (even the first-order solver's approximate, dual-*infeasible* estimates) and a finite box x_lo <= x <= x_hi containing the feasible set,

f^* \ge \min_{x \in [x_{lo}, x_{hi}]}
    \bigl(c + A^\top\lambda + A_{eq}^\top\nu\bigr)^\top x
    - b^\top\lambda - b_{eq}^\top\nu

is a rigorous lower bound (the separable box-minimum of the dual-residual term corrects for dual infeasibility), enclosed with outward-rounded intervals. Looser multipliers only loosen -- never invalidate -- the bound.

Shared formulas do not imply universal floating-point identity. Verify dtype, shape, derivative-order support, and the stated numerical assumptions for the path you use.

Module source ↗Source revision 9a2d73df0573Running reference examples →

CLASS

Certificate

omnibias.convex.CertificateSource ↗

class Certificate

Dataclass constructor fields; inherited fields, if any, are declared by the base class. A field(...) expression describes a default factory or field options, not a literal argument default.

Result of a verified optimality enclosure.

Attributes

enclosure: Rigorous ~omnibias.core.verified.Interval containing f*. primal_feasible: Whether x was rigorously verified to satisfy A x <= b. dual_residual_inf: Rigorous upper bound on ||c + A^T lambda||_inf (dual-feasibility residual; zero at a KKT point). gap: Certified suboptimality gap enclosure.width (upper - lower).

Parameters

Name	Type & default	Contract
enclosuredataclass field	IntervalRequired	Rigorous ~omnibias.core.verified.Interval containing f*.
primal_feasibledataclass field	boolRequired	Whether x was rigorously verified to satisfy A x <= b.
dual_residual_infdataclass field	floatRequired	Rigorous upper bound on ||c + A^T lambda||_inf (dual-feasibility residual; zero at a KKT point).
gapdataclass field	floatRequired	Certified suboptimality gap enclosure.width (upper - lower).

Regression example · certificate encloses penalty optimum

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_certificate_encloses_penalty_optimum() -> None:
    p = np.array([1.5, -2.0, 0.7, -0.1])
    Q = np.eye(4)
    c = -p
    A = -np.eye(4)
    b = np.zeros(4)
    sol = solve_qp_penalty(_t(Q), _t(c), _t(A), _t(b))
    cert = certify_qp_optimum(Q, c, A, b, sol.x.numpy(), sol.dual.numpy())
    x_star = np.maximum(p, 0.0)
    f_star = 0.5 * float(np.sum(x_star**2)) - float(p @ x_star)
    assert isinstance(cert, Certificate)
    assert cert.primal_feasible
    assert cert.enclosure.lo <= f_star <= cert.enclosure.hi
    assert cert.gap >= 0.0

python -m pytest packages/omnibias-convex/tests/test_penalty_torch.py -k test_certificate_encloses_penalty_optimum -q

Regression example · certificate encloses penalty optimum

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_certificate_encloses_penalty_optimum() -> None:
    # Feed the GD primal + temperature-collapse dual into the verified certificate.
    p = np.array([1.5, -2.0, 0.7, -0.1])
    Q = np.eye(4)
    c = -p
    A = -np.eye(4)
    b = np.zeros(4)
    sol = solve_qp_penalty(_arr(Q), _arr(c), _arr(A), _arr(b))
    cert = certify_qp_optimum(Q, c, A, b, np.asarray(sol.x), np.asarray(sol.dual))
    x_star = np.maximum(p, 0.0)
    f_star = 0.5 * float(np.sum(x_star**2)) - float(p @ x_star)
    assert isinstance(cert, Certificate)
    assert cert.primal_feasible
    assert cert.enclosure.lo <= f_star <= cert.enclosure.hi
    assert cert.gap >= 0.0

python -m pytest packages/omnibias-convex/tests/test_penalty_jax.py -k test_certificate_encloses_penalty_optimum -q

Fields & methods

enclosurefield

enclosure: Interval

Rigorous ~omnibias.core.verified.Interval containing f*.

View source ↗

primal_feasiblefield

primal_feasible: bool

Whether x was rigorously verified to satisfy A x <= b.

View source ↗

dual_residual_inffield

dual_residual_inf: float

Rigorous upper bound on ||c + A^T lambda||_inf (dual-feasibility residual; zero at a KKT point).

View source ↗

gapfield

gap: float

Certified suboptimality gap enclosure.width (upper - lower).

View source ↗

Read the implementation

class Certificate:
    """Result of a verified optimality enclosure.

    Attributes
    ----------
    enclosure:
        Rigorous :class:`~omnibias.core.verified.Interval` containing ``f*``.
    primal_feasible:
        Whether ``x`` was rigorously verified to satisfy ``A x <= b``.
    dual_residual_inf:
        Rigorous upper bound on ``||c + A^T lambda||_inf`` (dual-feasibility
        residual; zero at a KKT point).
    gap:
        Certified suboptimality gap ``enclosure.width`` (upper - lower).
    """

    enclosure: Interval
    primal_feasible: bool
    dual_residual_inf: float
    gap: float

Other public import paths

• omnibias.convex.Certificate
• omnibias.convex.certify.Certificate

CLASS

CertificationError

omnibias.convex.CertificationErrorSource ↗

class CertificationError(RuntimeError)

Raised when a rigorous certificate cannot be produced.

Regression example · certify lp requires finite box

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_certify_lp_requires_finite_box() -> None:
    c, A, b = _lp_2d()
    with pytest.raises(CertificationError):
        lp_dual_lower_bound(c, A, b, np.zeros(4), x_lower=0.0, x_upper=np.inf)

python -m pytest packages/omnibias-convex/tests/test_certify_lp.py -k test_certify_lp_requires_finite_box -q

Regression example · certify lp raises on infeasible x

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_certify_lp_raises_on_infeasible_x() -> None:
    c, A, b = _lp_2d()
    with pytest.raises(CertificationError):
        certify_lp_optimum(
            c, A, b, np.array([5.0, 5.0]), np.zeros(4), x_lower=0.0, x_upper=10.0
        )

python -m pytest packages/omnibias-convex/tests/test_certify_lp.py -k test_certify_lp_raises_on_infeasible_x -q

Read the implementation

class CertificationError(RuntimeError):
    """Raised when a rigorous certificate cannot be produced."""

Other public import paths

• omnibias.convex.CertificationError
• omnibias.convex.certify.CertificationError

FUNCTION

certify_lp_optimum

omnibias.convex.certify_lp_optimumSource ↗

certify_lp_optimum(c: Any, A: Any, b: Any, x: Any, dual: Any, *, A_eq: Any=None, b_eq: Any=None, eq_dual: Any=None, x_lower: Any, x_upper: Any) -> Certificate

Rigorous interval enclosure of an LP optimum f* (complements the QP one).

Lower bound: the verified lp_dual_lower_bound (Neumaier-Shcherbina, valid for the solver's approximate multipliers). Upper bound: c^T x at the supplied primal x, which must be rigorously feasible (A x <= b and, if given, A_eq x = b_eq within rounding). x_lower / x_upper are required finite variable bounds containing the feasible set.

Raises

CertificationError If the box is not finite, or x is not rigorously primal feasible (then c^T x is not a valid upper bound -- use lp_dual_lower_bound for the lower bound alone, e.g. with a separately decoded feasible point).

Parameters

Name	Type & default	Contract
cpositional-or-keyword	AnyRequired	See the operation contract and implementation below.
Apositional-or-keyword	AnyRequired	See the operation contract and implementation below.
bpositional-or-keyword	AnyRequired	See the operation contract and implementation below.
xpositional-or-keyword	AnyRequired	See the operation contract and implementation below.
dualpositional-or-keyword	AnyRequired	See the operation contract and implementation below.
A_eqkeyword-only	AnyDefault: None	See the operation contract and implementation below.
b_eqkeyword-only	AnyDefault: None	See the operation contract and implementation below.
eq_dualkeyword-only	AnyDefault: None	See the operation contract and implementation below.
x_lowerkeyword-only	AnyRequired	See the operation contract and implementation below.
x_upperkeyword-only	AnyRequired	See the operation contract and implementation below.

ReturnsCertificate

Explicit validation & failure cases

• When not primal_feasible, raises CertificationError('x is not rigorously primal feasible (A x <= b / A_eq x = b_eq violated within rounding); c^T x is then not a valid upper bound').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · certify lp raises on infeasible x

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_certify_lp_raises_on_infeasible_x() -> None:
    c, A, b = _lp_2d()
    with pytest.raises(CertificationError):
        certify_lp_optimum(
            c, A, b, np.array([5.0, 5.0]), np.zeros(4), x_lower=0.0, x_upper=10.0
        )

python -m pytest "packages/omnibias-convex/tests/test_certify_lp.py::test_certify_lp_raises_on_infeasible_x" -q

Regression example · lp certificate with equalities simplex

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_lp_certificate_with_equalities_simplex() -> None:
    # min c^T x  s.t. 1^T x = 1, x >= 0 ; optimum vertex (1, 0, 0), f* = -3.
    c = np.array([-3.0, -1.0, -2.0])
    A = -np.eye(3)
    b = np.zeros(3)
    A_eq = np.ones((1, 3))
    b_eq = np.array([1.0])
    sol = solve_lp_penalty(
        _arr(c), _arr(A), _arr(b), A_eq=_arr(A_eq), b_eq=_arr(b_eq),
    )
    x_feas = np.array([0.5, 0.25, 0.25])  # interior of the simplex (rigorously feasible)
    cert = certify_lp_optimum(
        c, A, b, x_feas, np.asarray(sol.dual),
        A_eq=A_eq, b_eq=b_eq, eq_dual=np.asarray(sol.eq_dual),
        x_lower=0.0, x_upper=1.0,
    )
    assert cert.enclosure.lo <= -3.0 <= cert.enclosure.hi
    assert cert.gap >= 0.0

python -m pytest packages/omnibias-convex/tests/test_certify_lp.py -k test_lp_certificate_with_equalities_simplex -q

Read the implementation

def certify_lp_optimum(
    c: Any,
    A: Any,
    b: Any,
    x: Any,
    dual: Any,
    *,
    A_eq: Any = None,
    b_eq: Any = None,
    eq_dual: Any = None,
    x_lower: Any,
    x_upper: Any,
) -> Certificate:
    r"""Rigorous interval enclosure of an LP optimum ``f*`` (complements the QP one).

    Lower bound: the verified :func:`lp_dual_lower_bound` (Neumaier-Shcherbina, valid
    for the solver's approximate multipliers). Upper bound: ``c^T x`` at the supplied
    primal ``x``, which must be rigorously feasible (``A x <= b`` and, if given,
    ``A_eq x = b_eq`` within rounding). ``x_lower`` / ``x_upper`` are required finite
    variable bounds containing the feasible set.

    Raises
    ------
    CertificationError
        If the box is not finite, or ``x`` is not rigorously primal feasible (then
        ``c^T x`` is not a valid upper bound -- use :func:`lp_dual_lower_bound` for
        the lower bound alone, e.g. with a separately decoded feasible point).
    """
    cn = np.asarray(c, dtype=float)
    An = np.asarray(A, dtype=float)
    bn = np.asarray(b, dtype=float)
    xn = np.asarray(x, dtype=float)
    n = cn.shape[0]
    m = bn.shape[0]

    lower = lp_dual_lower_bound(
        c, A, b, dual, A_eq=A_eq, b_eq=b_eq, eq_dual=eq_dual,
        x_lower=x_lower, x_upper=x_upper,
    )

    A_iv = to_interval_matrix(An.tolist())
    x_iv = _ivec(xn)
    b_iv = _ivec(bn)
    Ax = matvec(A_iv, x_iv)
    primal_feasible = all((b_iv[i] - Ax[i]).lo >= 0.0 for i in range(m))
    has_eq = A_eq is not None and b_eq is not None
    if has_eq:
        Aeqn = np.asarray(A_eq, dtype=float)
        beqn = np.asarray(b_eq, dtype=float)
        Aeq_iv = to_interval_matrix(Aeqn.tolist())
        beq_iv = _ivec(beqn)
        Aeqx = matvec(Aeq_iv, x_iv)
        eq_ok = all(
            (beq_iv[k] - Aeqx[k]).lo <= 0.0 <= (beq_iv[k] - Aeqx[k]).hi
            for k in range(beqn.shape[0])
        )
        primal_feasible = primal_feasible and eq_ok
    if not primal_feasible:
        raise CertificationError(
            "x is not rigorously primal feasible (A x <= b / A_eq x = b_eq violated "
            "within rounding); c^T x is then not a valid upper bound"
        )

    resid = cn + An.T @ np.maximum(np.asarray(dual, dtype=float), 0.0)
    if has_eq:
        nu = (
            np.zeros(np.asarray(b_eq).shape[0])
            if eq_dual is None
            else np.asarray(eq_dual, dtype=float)
        )
        resid = resid + np.asarray(A_eq, dtype=float).T @ nu
    dual_residual_inf = float(np.max(np.abs(resid)))

    cTx = sum_intervals([Interval.point(float(cn[j])) * x_iv[j] for j in range(n)])
    enclosure = Interval(lower.lo, cTx.hi)
    return Certificate(
        enclosure=enclosure,
        primal_feasible=True,
        dual_residual_inf=dual_residual_inf,
        gap=enclosure.width,
    )

Related APIsomnibias.convex.Certificate↗omnibias.convex.CertificationError↗omnibias.convex.lp_dual_lower_bound↗omnibias.core.verified.Interval↗omnibias.core.verified.sum_intervals↗omnibias.core.verified.matvec↗omnibias.core.verified.to_interval_matrix↗

Other public import paths

• omnibias.convex.certify_lp_optimum
• omnibias.convex.certify.certify_lp_optimum

FUNCTION

certify_qp_optimum

omnibias.convex.certify_qp_optimumSource ↗

certify_qp_optimum(Q: Any, c: Any, A: Any, b: Any, x: Any, dual: Any) -> Certificate

Rigorous interval enclosure of the optimal value of a strictly convex QP.

Parameters

Q, c, A, b: Problem data (Q symmetric positive definite). Any array-like. x: Computed primal point. dual: Computed dual multipliers; clamped to max(dual, 0) so the enclosure is valid for the nearest sign-feasible dual.

Returns

Certificate whose enclosure provably contains f*.

Raises

CertificationError If x is not rigorously primal feasible, or ||Q^{-1}|| cannot be certified (Neumann kappa >= 1; supply a better-conditioned Q).

Parameters

Name	Type & default	Contract
Qpositional-or-keyword	AnyRequired	Problem data (Q symmetric positive definite). Any array-like.
cpositional-or-keyword	AnyRequired	See the operation contract and implementation below.
Apositional-or-keyword	AnyRequired	See the operation contract and implementation below.
bpositional-or-keyword	AnyRequired	See the operation contract and implementation below.
xpositional-or-keyword	AnyRequired	Computed primal point.
dualpositional-or-keyword	AnyRequired	Computed dual multipliers; clamped to max(dual, 0) so the enclosure is valid for the nearest sign-feasible dual.

ReturnsCertificate

Explicit validation & failure cases

• When not primal_feasible, raises CertificationError('x is not rigorously primal feasible (A x <= b violated within rounding); certify at a strictly interior point (e.g. a looser barrier gap)').
• When not neumann['certified'], raises CertificationError(f"could not certify ||Q^-1|| (Neumann kappa = {neumann['kappa']:.3e} >= 1)").

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · certify raises when x infeasible

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_certify_raises_when_x_infeasible() -> None:
    n = 2
    Q = np.eye(n)
    c = np.zeros(n)
    A = np.eye(n)
    b = np.ones(n)
    x_bad = np.array([2.0, 2.0])  # violates x <= 1
    with pytest.raises(CertificationError):
        certify_qp_optimum(Q, c, A, b, x_bad, np.zeros(n))

python -m pytest "packages/omnibias-convex/tests/test_certify.py::test_certify_raises_when_x_infeasible" -q

Regression example · certificate encloses penalty optimum

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_certificate_encloses_penalty_optimum() -> None:
    p = np.array([1.5, -2.0, 0.7, -0.1])
    Q = np.eye(4)
    c = -p
    A = -np.eye(4)
    b = np.zeros(4)
    sol = solve_qp_penalty(_t(Q), _t(c), _t(A), _t(b))
    cert = certify_qp_optimum(Q, c, A, b, sol.x.numpy(), sol.dual.numpy())
    x_star = np.maximum(p, 0.0)
    f_star = 0.5 * float(np.sum(x_star**2)) - float(p @ x_star)
    assert isinstance(cert, Certificate)
    assert cert.primal_feasible
    assert cert.enclosure.lo <= f_star <= cert.enclosure.hi
    assert cert.gap >= 0.0

python -m pytest packages/omnibias-convex/tests/test_penalty_torch.py -k test_certificate_encloses_penalty_optimum -q

Read the implementation

def certify_qp_optimum(
    Q: Any, c: Any, A: Any, b: Any, x: Any, dual: Any
) -> Certificate:
    r"""Rigorous interval enclosure of the optimal value of a strictly convex QP.

    Parameters
    ----------
    Q, c, A, b:
        Problem data (``Q`` symmetric positive definite). Any array-like.
    x:
        Computed primal point.
    dual:
        Computed dual multipliers; clamped to ``max(dual, 0)`` so the enclosure is
        valid for the nearest sign-feasible dual.

    Returns
    -------
    :class:`Certificate` whose ``enclosure`` provably contains ``f*``.

    Raises
    ------
    CertificationError
        If ``x`` is not rigorously primal feasible, or ``||Q^{-1}||`` cannot be
        certified (Neumann ``kappa >= 1``; supply a better-conditioned ``Q``).
    """
    Qn = np.asarray(Q, dtype=float)
    cn = np.asarray(c, dtype=float)
    An = np.asarray(A, dtype=float)
    bn = np.asarray(b, dtype=float)
    xn = np.asarray(x, dtype=float)
    lam = np.maximum(np.asarray(dual, dtype=float), 0.0)
    n = cn.shape[0]
    m = bn.shape[0]

    A_iv = to_interval_matrix(An.tolist())
    Q_iv = to_interval_matrix(Qn.tolist())
    x_iv = _ivec(xn)
    b_iv = _ivec(bn)
    lam_iv = _ivec(lam)

    # --- primal feasibility: s = b - A x >= 0 (rigorous) ------------------- #
    Ax = matvec(A_iv, x_iv)
    slack = [b_iv[i] - Ax[i] for i in range(m)]
    primal_feasible = all(s.lo >= 0.0 for s in slack)
    if not primal_feasible:
        raise CertificationError(
            "x is not rigorously primal feasible (A x <= b violated within rounding); "
            "certify at a strictly interior point (e.g. a looser barrier gap)"
        )

    # --- dual residual v = c + A^T lambda --------------------------------- #
    v = [
        Interval.point(float(cn[j])) + sum_intervals([A_iv[i][j] * lam_iv[i] for i in range(m)])
        for j in range(n)
    ]
    v_l1 = sum_intervals([vi.abs() for vi in v])
    v_linf = inf_norm_vector(v)

    # --- ||Q^{-1}||_inf via the Neumann certificate ----------------------- #
    try:
        b_approx = np.linalg.inv(Qn)
    except np.linalg.LinAlgError as exc:  # pragma: no cover - singular Q
        raise CertificationError("Q is singular; a positive-definite Q is required") from exc
    neumann = neumann_inverse_norm_bound(Qn.tolist(), b_approx.tolist())
    if not neumann["certified"]:
        raise CertificationError(
            f"could not certify ||Q^-1|| (Neumann kappa = {neumann['kappa']:.3e} >= 1)"
        )
    inv_norm = float(neumann["inverse_norm_bound"])

    # v^T Q^{-1} v in [0, ||Q^-1||_inf * ||v||_1 * ||v||_inf] (rigorous).
    vqv = Interval(0.0, (Interval.point(inv_norm) * v_l1 * Interval.point(v_linf)).hi)
    b_dot_lam = sum_intervals([b_iv[i] * lam_iv[i] for i in range(m)])
    g_lower = Interval.point(-0.5) * vqv - b_dot_lam  # encloses g(lambda) <= f*

    # f0(x) = 1/2 x^T Q x + c^T x  (upper bound, x feasible).
    Qx = matvec(Q_iv, x_iv)
    xQx = sum_intervals([x_iv[j] * Qx[j] for j in range(n)])
    cTx = sum_intervals([Interval.point(float(cn[j])) * x_iv[j] for j in range(n)])
    f0 = Interval.point(0.5) * xQx + cTx

    enclosure = Interval(g_lower.lo, f0.hi)
    return Certificate(
        enclosure=enclosure,
        primal_feasible=primal_feasible,
        dual_residual_inf=v_linf,
        gap=enclosure.width,
    )

Related APIsomnibias.convex.Certificate↗omnibias.convex.CertificationError↗omnibias.core.verified.Interval↗omnibias.core.verified.sum_intervals↗omnibias.core.verified.inf_norm_vector↗omnibias.core.verified.matvec↗omnibias.core.verified.neumann_inverse_norm_bound↗omnibias.core.verified.to_interval_matrix↗

Other public import paths

• omnibias.convex.certify_qp_optimum
• omnibias.convex.certify.certify_qp_optimum

FUNCTION

lp_dual_lower_bound

omnibias.convex.lp_dual_lower_boundSource ↗

lp_dual_lower_bound(c: Any, A: Any, b: Any, dual: Any, *, A_eq: Any=None, b_eq: Any=None, eq_dual: Any=None, x_lower: Any, x_upper: Any) -> Interval

Rigorous Neumaier-Shcherbina lower bound on the LP optimum f*.

Encloses the Lagrangian dual value min_{x in box} (c + A^T lambda + A_eq^T nu)^T x - b^T lambda - b_eq^T nu in outward-rounded interval arithmetic. The returned interval's lo is a **guaranteed** lower bound on f* for *any* lambda >= 0 (clamped) and nu (sign-free), provided the box [x_lower, x_upper] contains the feasible set -- so the first-order penalty solver's approximate dual / eq_dual estimates are admissible.

Parameters

Name	Type & default	Contract
cpositional-or-keyword	AnyRequired	See the operation contract and implementation below.
Apositional-or-keyword	AnyRequired	See the operation contract and implementation below.
bpositional-or-keyword	AnyRequired	See the operation contract and implementation below.
dualpositional-or-keyword	AnyRequired	See the operation contract and implementation below.
A_eqkeyword-only	AnyDefault: None	See the operation contract and implementation below.
b_eqkeyword-only	AnyDefault: None	See the operation contract and implementation below.
eq_dualkeyword-only	AnyDefault: None	See the operation contract and implementation below.
x_lowerkeyword-only	AnyRequired	See the operation contract and implementation below.
x_upperkeyword-only	AnyRequired	See the operation contract and implementation below.

ReturnsInterval

Executed regression · certify lp requires finite box

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_certify_lp_requires_finite_box() -> None:
    c, A, b = _lp_2d()
    with pytest.raises(CertificationError):
        lp_dual_lower_bound(c, A, b, np.zeros(4), x_lower=0.0, x_upper=np.inf)

python -m pytest "packages/omnibias-convex/tests/test_certify_lp.py::test_certify_lp_requires_finite_box" -q

Regression example · lower bound is sound for arbitrary dual

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_lower_bound_is_sound_for_arbitrary_dual() -> None:
    # lambda = 0 is admissible: bound = min_{x in box} c^T x <= f* (very loose).
    c, A, b = _lp_2d()
    ref = scipy_linprog(c, A_ub=A, b_ub=b, bounds=(None, None)).fun
    lo0 = lp_dual_lower_bound(c, A, b, np.zeros(4), x_lower=0.0, x_upper=10.0)
    assert lo0.lo <= ref + 1e-9

python -m pytest packages/omnibias-convex/tests/test_certify_lp.py -k test_lower_bound_is_sound_for_arbitrary_dual -q

Read the implementation

def lp_dual_lower_bound(
    c: Any,
    A: Any,
    b: Any,
    dual: Any,
    *,
    A_eq: Any = None,
    b_eq: Any = None,
    eq_dual: Any = None,
    x_lower: Any,
    x_upper: Any,
) -> Interval:
    r"""Rigorous Neumaier-Shcherbina lower bound on the LP optimum ``f*``.

    Encloses the Lagrangian dual value ``min_{x in box} (c + A^T lambda +
    A_eq^T nu)^T x - b^T lambda - b_eq^T nu`` in outward-rounded interval
    arithmetic. The returned interval's ``lo`` is a **guaranteed** lower bound on
    ``f*`` for *any* ``lambda >= 0`` (clamped) and ``nu`` (sign-free), provided the
    box ``[x_lower, x_upper]`` contains the feasible set -- so the first-order
    penalty solver's approximate ``dual`` / ``eq_dual`` estimates are admissible.
    """
    cn = np.asarray(c, dtype=float)
    An = np.asarray(A, dtype=float)
    bn = np.asarray(b, dtype=float)
    lam = np.maximum(np.asarray(dual, dtype=float), 0.0)
    n = cn.shape[0]
    m = bn.shape[0]
    xl, xu = _broadcast_box(x_lower, x_upper, n)

    A_iv = to_interval_matrix(An.tolist())
    lam_iv = _ivec(lam)
    b_iv = _ivec(bn)
    has_eq = A_eq is not None and b_eq is not None
    Aeq_iv: list[list[Interval]] = []
    nu_iv: list[Interval] = []
    beq_iv: list[Interval] = []
    m_eq = 0
    if has_eq:
        Aeqn = np.asarray(A_eq, dtype=float)
        beqn = np.asarray(b_eq, dtype=float)
        m_eq = beqn.shape[0]
        nu = np.zeros(m_eq) if eq_dual is None else np.asarray(eq_dual, dtype=float)
        Aeq_iv = to_interval_matrix(Aeqn.tolist())
        nu_iv = _ivec(nu)
        beq_iv = _ivec(beqn)

    # dual-residual r_j = c_j + sum_i A[i,j] lambda_i + sum_k A_eq[k,j] nu_k.
    box = [Interval(float(xl[j]), float(xu[j])) for j in range(n)]
    terms: list[Interval] = []
    for j in range(n):
        r_j = Interval.point(float(cn[j])) + sum_intervals(
            [A_iv[i][j] * lam_iv[i] for i in range(m)]
        )
        if has_eq:
            r_j = r_j + sum_intervals([Aeq_iv[k][j] * nu_iv[k] for k in range(m_eq)])
        terms.append(r_j * box[j])  # min over the box is (r_j * box_j).lo

    base = -sum_intervals([b_iv[i] * lam_iv[i] for i in range(m)])
    if has_eq:
        base = base - sum_intervals([beq_iv[k] * nu_iv[k] for k in range(m_eq)])
    return base + sum_intervals(terms)

Related APIsomnibias.core.verified.Interval↗omnibias.core.verified.sum_intervals↗omnibias.core.verified.to_interval_matrix↗

Other public import paths

• omnibias.convex.lp_dual_lower_bound
• omnibias.convex.certify.lp_dual_lower_bound

← Package overviewRunnable learning examples →