Expand description
Polynomial Optimization and Sum-of-Squares
Certifiable optimization using SOS (Sum-of-Squares) relaxations.
§Key Capabilities
- SOS Certificates: Prove non-negativity of polynomials
- Moment Relaxations: Lasserre hierarchy for global optimization
- Positivstellensatz: Certificates for polynomial constraints
§Integration with Mincut Governance
SOS provides provable guardrails:
- Certify that permission rules always satisfy bounds
- Prove stability of attention policies
- Verify monotonicity of routing decisions
§Mathematical Background
A polynomial p(x) is SOS if p = Σ q_i² for some polynomials q_i. If p is SOS, then p(x) ≥ 0 for all x.
The SOS condition can be written as a semidefinite program (SDP).
Structs§
- Bounds
Certificate - Certificate for bounds on polynomial
- Monomial
- A monomial: product of variables with powers Represented as sorted list of (variable_index, power)
- Nonnegativity
Certificate - Certificate that a polynomial is non-negative
- Polynomial
- Multivariate polynomial
- SDPProblem
- SDP problem in standard form minimize: trace(C * X) subject to: trace(A_i * X) = b_i, X ≽ 0
- SDPSolution
- SDP solution
- SDPSolver
- Simple projected gradient SDP solver
- SOSConfig
- SOS decomposition configuration
- SOSDecomposition
- SOS decomposition: p = Σ q_i²
- Term
- A term: coefficient times monomial
Enums§
- SOSResult
- Result of SOS decomposition